Вступление

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

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

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

При этом Simulated Annealing - это вероятностная метаэвристика, используемая для поиска приблизительно хорошего решения и обычно используется с дискретными пространствами поиска.

В этой статье мы будем использовать его в дискретном пространстве поиска

• в задаче коммивояжера .

Имитация отжига

Математическая модель

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

Для данного материала мы можем определить два энергетических состояния, E ~1~ (текущее состояние) и E ~2~ (следующее состояние), и их различие:

$$
\ Delta E = E_2-E_1
$

Как правило, процесс отжига приводит к переходам из состояний с более высокой энергией в состояние с более низкой энергией, т.е. когда Î “E <0 . Такие переходы всегда происходят с вероятностью 1 поскольку они в наших интересах для поиска наилучших возможных решений.

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

Если “E> 0 , уровень энергии следующего состояния выше, чем уровень энергии текущего состояния. В этом случае вероятность перехода из состояния E ~1~ в состояние E ~2~ с более высокой энергией определяется вероятностью:

$$
P (\ Delta E) = exp ({\ frac {- \ Delta E} {k \ cdot T}})
$

Где k представляет постоянную Больцмана, а T - текущая температура материала. Изменяя температуру материала, мы видим, что уровень энергии материала также изменяется.

Моделирование модели отжига

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

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

Давайте посмотрим на очень простой пример задачи оптимизации. В случае, если наша проблема заключается в нахождении минимума квадратичной функции, сама функция представляет пространство поиска, а каждая из точек (например, (x=1;y=-2) ) представляет одно из состояний:

{.ezlazyload}
[Кредит: Википедия.]{.small}

Чтобы сделать возможным поиск новых решений, мы должны принять их в соответствии с некоторыми предопределенными правилами. В приведенном выше примере мы бы предпочли $ x = 1 $, а не $ x = 2 $, поскольку это приведет нас к минимуму.

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

Чтобы позволить алгоритму принимать новые решения, которые либо лучше, либо кажутся хуже, но помогут нам избежать локальных оптимумов, мы можем использовать ранее определенные вероятности алгоритма моделирования отжига: в случае, если наше новое решение лучше, чем наше текущее решение, мы всегда приму это.

В случае, если новое решение будет хуже, мы с некоторой вероятностью примем его:

$$
P = exp ({- \ frac {f (s_2) -f (s_1)} {T_k}})
$

где s - некоторое решение, а Tk - температура на k -м шаге алгоритма.

Обратите внимание, что это выражение аналогично предыдущему, описывающему процесс отжига с уровнями энергии. Разница в том, что здесь вместо уровней энергии у нас есть значения функций.

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

Уменьшая температуру (и, следовательно, вероятность принятия худших решений), мы позволяем алгоритму медленно фокусироваться на определенной области, которая в идеале содержит оптимальное решение. Этот медленный процесс охлаждения делает алгоритм достаточно эффективным при работе с локальными оптимумами.

Вот отличная визуализация того, как анализируется пространство поиска:

{.ezlazyload}
[Кредит: Википедия.]{.small}

Мотивация

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

Одна из самых известных задач оптимизации - задача коммивояжера . Здесь у нас есть набор точек (городов), которые мы хотим пересечь таким образом, чтобы минимизировать общее расстояние перемещения.

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

{.ezlazyload}
[Кредит: TutorialsPoint]{.small}

Два разных тура по одной и той же планировке городов. Функция в этом случае представляет собой общее пройденное расстояние.

Теперь, если мы сделаем простую математику, мы сделаем вывод, что общее количество комбинаций для обхода всех городов равно N! , где N - количество городов. Например, если у нас есть три города, будет шесть возможных комбинаций:

1 -> 2 -> 3
1 -> 3 -> 2
2 -> 1 -> 3
2 -> 3 -> 1
3 -> 1 -> 2
3 -> 2 -> 1

Одна из этих комбинаций категорически будет иметь самое короткое расстояние, а одна из них - самое длинное.

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

{.ezlazyload}

Выполнение

Чтобы начать решение задачи коммивояжера (TSP), нам сначала нужно создать некоторые исходные структуры данных. Для TSP это означает создание вспомогательных классов City , Tour и Util .

Вспомогательные классы

Класс City довольно прост. Он представляет город в двухмерном пространстве с x и y он получает через конструктор.

 public class City { 
 
 private int x; 
 private int y; 
 
 public City(int x, int y) { 
 this.x = x; 
 this.y = y; 
 } 
 
 // Getters and toString() 
 } 

Класс Tour немного сложнее, но единственная «настоящая» логика здесь происходит в getTourLength() . Мы начинаем с первого города в нашем туре и начинаем перемещаться по списку. Мы вычисляем расстояние между каждой парой соседних городов и добавляем его к общему расстоянию.

В конце метода мы вычислили общее расстояние нашего тура:

 public class Tour { 
 private List<City> cities; 
 private int distance; 
 
 public Tour(List<City> cities) { 
 this.cities = new ArrayList<>(cities); 
 Collections.shuffle(this.cities); 
 } 
 public City getCity(int index) { 
 return cities.get(index); 
 } 
 
 public int getTourLength() { 
 if (distance != 0) return distance; 
 
 int totalDistance = 0; 
 
 for (int i = 0; i < noCities(); i++) { 
 City start = getCity(i); 
 City end = getCity(i + 1 < noCities() ? i + 1 : 0); 
 totalDistance += Util.distance(start, end); 
 } 
 
 distance = totalDistance; 
 return totalDistance; 
 } 
 
 public Tour duplicate() { 
 return new Tour(new ArrayList<>(cities)); 
 } 
 
 public int noCities() { 
 return cities.size(); 
 } 
 
 // Getters and toString() 
 } 

Последний вспомогательный класс, о котором следует упомянуть, - это Util который содержит методы probability() и distance()

 public class Util { 
 public static double probability(double f1, double f2, double temp) { 
 if (f2 < f1) return 1; 
 return Math.exp((f1 - f2) / temp); 
 } 
 
 public static double distance(City city1, City city2) { 
 int xDist = Math.abs(city1.getX() - city2.getX()); 
 int yDist = Math.abs(city1.getY() - city2.getY()); 
 return Math.sqrt(xDist * xDist + yDist * yDist); 
 } 
 } 

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

Метод distance() вычисляет и возвращает евклидово расстояние между двумя заданными городами.

Реализация имитации отжига

Разобравшись с нашими помощниками, давайте продолжим и реализуем сам алгоритм:

 public class SimulatedAnnealing { 
 private static double temperature = 1000; 
 private static double coolingFactor = 0.995; 
 
 public static void main(String[] args) { 
 List<City> cities = new ArrayList<>(); 
 
 City city1 = new City(100, 100); 
 cities.add(city1); 
 
 City city2 = new City(200, 200); 
 cities.add(city2); 
 
 City city3 = new City(100, 200); 
 cities.add(city3); 
 
 City city4 = new City(200, 100); 
 cities.add(city4); 
 
 Tour current = new Tour(cities); 
 Tour best = current.duplicate(); 
 
 for (double t = temperature; t > 1; t *= coolingFactor) { 
 Tour neighbor = current.duplicate(); 
 
 int index1 = (int) (neighbor.noCities() * Math.random()); 
 int index2 = (int) (neighbor.noCities() * Math.random()); 
 
 Collections.swap(next.getCities(), index1, index2); 
 
 int currentLength = current.getTourLength(); 
 int neighborLength = neighbor.getTourLength(); 
 
 if (Math.random() < Util.probability(currentLength, neighborLength, t)) { 
 current = neighbor.duplicate(); 
 } 
 
 if (current.getTourLength() < best.getTourLength()) { 
 best = current.duplicate(); 
 } 
 } 
 
 System.out.println("Final tour length: " + best.getTourLength()); 
 System.out.println("Tour: " + best); 
 } 
 } 

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

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

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

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

Окончательный результат программы показан ниже:

 Final tour length: 400 
 Tour: [(100, 100), (200, 100), (200, 200), (100, 200)] 

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

Заключение

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

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