Програмная имитация отжига для начинающих

16 апреля, 2015 rius

Данная заметка является переводом этой статьи: источник

Поиск лучшего решения для определенных задач оптимизации может быть необычайно тяжелым, часто даже практически невозможным. Это происходит из-за того, что при усложнении задачи возрастает число возможных решений из которых нужно выбрать оптимальное. Даже при использовании возможностей современных компьютеров перебор всех вариантов представляется тяжелой задачей. В этом случае мы не можем надеяться на нахождение оптимального решения за приемлемое время, поэтому мы можем удовлетвориться решением, которое близко к оптимальному.

Примером задачи оптимизации с большим числом возможных решений является задача коммивояжера (ЗК). Для решения задач вроде ЗК нам нужно найти удовлетворительное решение за приемлемое время. В предыдущей заметке ссылка мы применили генетический алгоритм, и, хотя эти алгоритмы являются одним из методов нахождения достаточно хороших решений для ЗК, есть еще и более простые. В этой заметке мы рассмотрим метод имитации отжига.

Если вы не знакомы с задачей коммивояжера, посмотрите ВИКИ и предыдущую заметку.

Что такое имитация отжига?

Для начала давайте разберемся как работает симуляция восстановления (отжиг) и почему она подходит к конкретной задаче коммивояжера. Первоначально программная имитация отжига была заимствована из металлургии. (При отжиге металл нагревают и охлаждают для изменения физических свойств. К примеру, вы решили сделать нож из старого напильника. Если обрабатывать заготовку для придания нужной формы на наждачном станке, то вы израсходуете несколько камней. Вместо этого можно снизить твердость напильника термической обработкой. Заготовку нагревают и медленно охлаждают, она становится гораздо податливее (лирическое металлургическое отступление). В нашей программе мы введем переменную для имитации температурной обработки. Первоначально в ней будет большая величина, которая постепенно будет «остывать». При выском значении алгоритму разрешено с большей частотой принимать к рассмотрению решения, которые хуже текущего решения. Это позволяет алгоритму отказываться от найденных локальных максимумов. По мере охлаждения снижается вероятность принятия худших решений, поэтому постепенно алгоритм сосредотачивается на области пространства решений, в которой мы надеемся найти решение, близкое к оптимальному. Процесс «остывания» — это и есть та особенность, которая делает имитацию отжига значительно эффективнее при поиске близкого к оптимальному решения при большом числе локальных максимумов.

Преимущества имитации отжига

Вы наверно спросите: есть ли у имитации отжига преимущества перед простым алгоритмом восхождения на гору? Восхождение на гору может быть неожиданно эффективным, но есть тенденция застревания на локальных максимумах. Как мы уже констатировали, имитация отжига — это отличный способ найти в среднем примерный глобальный максимум.

Для лучшего понимания давайте рассмотрим почему алгоритм восхождения предрасположен к застреванию на локальных максимумах.

Алгоритм восхождения просто принимает к рассмотрению те соседние решения, которые лучше текущего решения. Если лучших решений нет, он останавливается.


hc_1
hc_2

В примере на картинке мы запускаем скалолаза с места, помеченного красной стрелкой и он лезет в гору, пока не окажется в такой точке, что для дальнейшего восхождения надо сначала опуститься. Как легко заметить, он застрянет в локальном максимуме. Если бы это была реальная задача поиска решения, то мы не знали бы как выглядит пространство решений. Поэтому невозможно было бы сказать, близок ли найденный максимум к глобальному.

Имитация отжига работает немного иначе и при случае примет к рассмотрению решения хуже текущего. Это качество алгоритма позволяет спрыгнуть с локального максимума, в котором застрял бы другой алгоритм.

Функция принятия решения к рассмотрению

Давайте посмотрим как алгоритм принимает решения задачи для того, чтоб лучше понять как он избегает локальных максимумов.

Сначала мы проверяем, является ли соседнее решение лучше текущего. Если так, принимаем его безо всяких условий. Однако, если соседнее решение не лучше, то надо рассмотреть несколько факторов. Первое — насколько хуже соседнее решение? Второе — какова сейчас «температура» системы. При высокой температуре вероятность принятия худших по отношению к текущему решений выше.

Формула такая:

exp( (solutionEnergy - neighbourEnergy) / temperature )

Таким образом, чем меньше изменение энергии (качества решения), и чем выше температура, тем вероятнее принятие к рассмотрению нового решения.

Обзор алгоритма

Базовые особенности алгоритма:

— Задаем начальную температуру и случайное начальное решение
— Попадаем в цикл, который активен до удовлетворения условия. Обычно услоие таково: система остыла или найдено удовлетворительное решение.
— Теперь выбираем соседа делая небольшие изменения в текущем решении
— Потом решаем, стоит ли принимать к рассмотрению новое решение
— Уменьшаем температуру и делаем новую итерацию цикла.

Инициализация температуры

Для лучшей оптимизации мы берем такую стартовую температуру, которая позволит в начале любое изменение по отношению к стартовому решению. Это позволит алгоритму лучше исследовать пространство решений и сосредоточиться на более перспективной для поиска области.

Код на java немного доработан — расстояния считаются как double и добавлен простенький GUI.

Карта городов для обхода такая:


map1

Сначала нам нужно определить класс города.

package ru.outofrange.annealing;
 
public class City {
    int x;
    int y;
 
    // Constructs a randomly placed city
    public City(){
        this.x = (int)(Math.random()*200);
        this.y = (int)(Math.random()*200);
    }
 
    // Constructs a city at chosen x, y location
    public City(int x, int y){
        this.x = x;
        this.y = y;
    }
 
    // Gets city's x coordinate
    public int getX(){
        return this.x;
    }
 
    // Gets city's y coordinate
    public int getY(){
        return this.y;
    }
 
    // Gets the distance to given city
    public double distanceTo(City city){
        int xDistance = /*Math.abs*/(getX() - city.getX());
        int yDistance = /*Math.abs*/(getY() - city.getY());
        double distance = Math.sqrt( (xDistance*xDistance) + (yDistance*yDistance) );
 
        return distance;
    }
 
    @Override
    public String toString(){
        return getX()+", "+getY();
    }
}

Теперь определим класс, который отслеживает маршруты:

package ru.outofrange.annealing;
 
import java.util.ArrayList;
 
public class TourManager {
 
    // Holds our cities
    private static ArrayList<City> destinationCities = new ArrayList<City>();
 
    // Adds a destination city
    public static void addCity(City city) {
        destinationCities.add(city);
    }
 
    // Get a city
    public static City getCity(int index){
        return (City)destinationCities.get(index);
    }
 
    // Get the number of destination cities
    public static int numberOfCities(){
        return destinationCities.size();
    }
 
}

Теперь зададим класс, который моделирует маршрут:

package ru.outofrange.annealing;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class Tour{
 
    // Holds our tour of cities
    private ArrayList<City> tour = new ArrayList<City>();
    // Cache
    private double distance = 0.0d;
 
    // Constructs a blank tour
    public Tour(){
        for (int i = 0; i < TourManager.numberOfCities(); i++) {
            tour.add(null);
        }
    }
 
    // Constructs a tour from another tour
    @SuppressWarnings("unchecked")
	public Tour(ArrayList<City> tour){
        this.tour = (ArrayList<City>) tour.clone();
    }
 
    // Returns tour information
    public ArrayList<City> getTour(){
        return tour;
    }
 
    // Creates a random individual
    public void generateIndividual() {
        // Loop through all our destination cities and add them to our tour
        for (int cityIndex = 0; cityIndex < TourManager.numberOfCities(); cityIndex++) {
          setCity(cityIndex, TourManager.getCity(cityIndex));
        }
        // Randomly reorder the tour
        Collections.shuffle(tour);
    }
 
    // Gets a city from the tour
    public City getCity(int tourPosition) {
        return (City)tour.get(tourPosition);
    }
 
    // Sets a city in a certain position within a tour
    public void setCity(int tourPosition, City city) {
        tour.set(tourPosition, city);
        // If the tours been altered we need to reset the fitness and distance
        distance = 0;
    }
 
    // Gets the total distance of the tour
    public double getDistance(){
        if ( Double.compare(distance, 0.0d) == 0) {
            double tourDistance = 0.0d;
            // Loop through our tour's cities
            for (int cityIndex=0; cityIndex < tourSize(); cityIndex++) {
                // Get city we're traveling from
                City fromCity = getCity(cityIndex);
                // City we're traveling to
                City destinationCity;
                // Check we're not on our tour's last city, if we are set our
                // tour's final destination city to our starting city
                if(cityIndex+1 < tourSize()){
                    destinationCity = getCity(cityIndex+1);
                }
                else{
                    destinationCity = getCity(0);
                }
                // Get the distance between the two cities
                tourDistance += fromCity.distanceTo(destinationCity);
            }
            distance = tourDistance;
        }
        return distance;
    }
 
    // Get number of cities on our tour
    public int tourSize() {
        return tour.size();
    }
 
    @Override
    public String toString() {
        String geneString = "|";
        for (int i = 0; i < tourSize(); i++) {
            geneString += getCity(i)+"|";
        }
        return geneString;
    }
}

Наконец, имитация отжига:

package ru.outofrange.annealing;
 
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
 
import javax.swing.BorderFactory;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;
 
import ru.outofrange.annealing.City;
import ru.outofrange.annealing.Tour;
import ru.outofrange.annealing.MyPanel;
 
public class SimulatedAnnealing {
 
    // Calculate the acceptance probability
    public static double acceptanceProbability(double energy, double newEnergy, double temperature) {
        // If the new solution is better, accept it
        if (newEnergy < energy) {
            return 1.0;
        }
        // If the new solution is worse, calculate an acceptance probability
        return Math.exp((energy - newEnergy) / temperature);
    }
 
    public static void main(String[] args) {
        // Create and add our cities
        City city = new City(60, 200);
        TourManager.addCity(city);
        City city2 = new City(180, 200);
        TourManager.addCity(city2);
        City city3 = new City(80, 180);
        TourManager.addCity(city3);
        City city4 = new City(140, 180);
        TourManager.addCity(city4);
        City city5 = new City(20, 160);
        TourManager.addCity(city5);
        City city6 = new City(100, 160);
        TourManager.addCity(city6);
        City city7 = new City(200, 160);
        TourManager.addCity(city7);
        City city8 = new City(140, 140);
        TourManager.addCity(city8);
        City city9 = new City(40, 120);
        TourManager.addCity(city9);
        City city10 = new City(100, 120);
        TourManager.addCity(city10);
        City city11 = new City(180, 100);
        TourManager.addCity(city11);
        City city12 = new City(60, 80);
        TourManager.addCity(city12);
        City city13 = new City(120, 80);
        TourManager.addCity(city13);
        City city14 = new City(180, 60);
        TourManager.addCity(city14);
        City city15 = new City(20, 40);
        TourManager.addCity(city15);
        City city16 = new City(100, 40);
        TourManager.addCity(city16);
        City city17 = new City(200, 40);
        TourManager.addCity(city17);
        City city18 = new City(20, 20);
        TourManager.addCity(city18);
        City city19 = new City(60, 20);
        TourManager.addCity(city19);
        City city20 = new City(160, 20);
        TourManager.addCity(city20);
 
        // Set initial temp
        double temp = 10000;
 
        // Cooling rate
        double coolingRate = 0.003;
 
        // Initialize intial solution
        Tour currentSolution = new Tour();
        currentSolution.generateIndividual();
 
        System.out.println("Initial solution distance: " + currentSolution.getDistance());
 
        // Set as current best
        Tour best = new Tour(currentSolution.getTour());
 
        // Loop until system has cooled
        while (temp > 1) {
            // Create new neighbour tour
            Tour newSolution = new Tour(currentSolution.getTour());
 
            // Get a random positions in the tour
            int tourPos1 = (int) (newSolution.tourSize() * Math.random());
            int tourPos2 = (int) (newSolution.tourSize() * Math.random());
 
            // Get the cities at selected positions in the tour
            City citySwap1 = newSolution.getCity(tourPos1);
            City citySwap2 = newSolution.getCity(tourPos2);
 
            // Swap them
            newSolution.setCity(tourPos2, citySwap1);
            newSolution.setCity(tourPos1, citySwap2);
 
            // Get energy of solutions
            double currentEnergy = currentSolution.getDistance();
            double neighbourEnergy = newSolution.getDistance();
 
            // Decide if we should accept the neighbour
            if (acceptanceProbability(currentEnergy, neighbourEnergy, temp) > Math.random()) {
                currentSolution = new Tour(newSolution.getTour());
            }
 
            // Keep track of the best solution found
            if (currentSolution.getDistance() < best.getDistance()) {
                best = new Tour(currentSolution.getTour());
            }
 
            // Cool system
            temp *= 1-coolingRate;
        }
 
        System.out.println("Final solution distance: " + best.getDistance());
        System.out.println("Tour: " + best);
 
        final Tour tour = best;
 
        SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                createAndShowGUI(tour);
            }
        });
    }
 
    private static void createAndShowGUI(Tour tour) {
 
        JFrame f = new JFrame("Annealing simulation for TSP");
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
 
        JPanel myPanel = new MyPanel(tour);
 
        f.add(myPanel);
        f.pack();
        f.setVisible(true);
    }
}
 
//http://docs.oracle.com/javase/tutorial/uiswing/painting/step3.html
 
class MyPanel extends JPanel {
 
	private static final long serialVersionUID = 7615629084996272465L;
 
	// if you want to increase the picture of the route, increase the koef
	float koef = 1.8f;
 
	// pagging/margin of the route image
	int offset = 50;
 
	// default area size, our coordinates are within range 0-200
	int areaSize = 200;
 
	private Tour tour;
 
	public MyPanel(Tour tour) {
 
       setBorder(BorderFactory.createLineBorder(Color.black));
       this.tour = tour;
 
	}
 
	private void showTour(Graphics g){
 
  	    // number of the current city in the route, starts at 1
		// for the first city we don't draw a line to the prev city
		int number = 1;
 
		int prevX = 0, prevY = 0;
 
		int max = (int)(offset + areaSize*koef);
 
		for (City city: tour.getTour()) {
 
			g.setColor(Color.BLUE);
 
			g.drawString(
      			String.valueOf(number), 
      			offset + (int)((city.getX() - 5)*koef), 
      			max - (int)((city.getY()+ 5 )*koef));
 
			g.setColor(Color.RED);
 
			if (number == 1) {
				prevX = city.getX();
				prevY = city.getY();
 
			} else {
 
				g.drawLine((int)(prevX*koef + offset), (int)(max - prevY*koef), 
  					(int)(city.getX()*koef) + offset, max - (int)(city.getY()*koef));
				prevX = city.getX();
				prevY = city.getY();
			}
			number++;
		}
	}
 
	public Dimension getPreferredSize() {
		// we define the size of the window dynamically
		return new Dimension((int)(offset*2 + areaSize*koef), (int)(offset*2 + areaSize*koef));
	}
 
	protected void paintComponent(Graphics g) {
		super.paintComponent(g);       
		g.drawString("Resulting route, length = " + String.valueOf(tour.getDistance()),10,20);
 
		g.setColor(Color.BLACK);
 
		g.drawRect(offset, offset , (int)(areaSize*koef), (int)(areaSize*koef));
 
		int step = (int)(areaSize*koef/20);
 
		// creating grid
		for (int i = 1; i < 20 ; i++){
			g.drawLine(offset - 5, i*step + offset, offset + 5 + (int)(areaSize*koef), i*step + offset);
			g.drawLine(offset + i*step, offset - 5, offset + i*step, offset + 5 + (int)(areaSize*koef));
		}
 
		showTour(g);
	} 
 
}

Найденные решения имеют разброс, но именно с помощью отжига я нашел лучшее (как мне кажется решение), причем оно выпадало несколько раз:


annealing1

Posted in Программирование Tags:
«
»
You can leave a response, or trackback from your own site.

Leave a Reply