1. Введение
В этом руководстве мы узнаем об алгоритме имитации отжига и покажем пример реализации, основанный на задаче коммивояжера (TSP).
2. Имитация отжига
Алгоритм имитации отжига — это эвристика для решения задач с большим пространством поиска.
Вдохновение и название пришли из отжига в металлургии; это метод, который включает нагрев и контролируемое охлаждение материала.
В общем, имитация отжига снижает вероятность принятия худших решений, поскольку исследует пространство решений и снижает температуру системы. Следующая анимация показывает механизм поиска наилучшего решения с помощью алгоритма имитации отжига:
Как видим, алгоритм использует более широкий диапазон решений при высокой температуре системы, ища глобальный оптимум. При понижении температуры диапазон поиска становится меньше, пока не будет найден глобальный оптимум.
Алгоритм имеет несколько параметров для работы:
- количество итераций - условие остановки для моделирования
- начальная температура – начальная энергия системы
- параметр скорости охлаждения — процент, на который мы снижаем температуру системы
- минимальная температура – опциональное условие остановки
- время симуляции – необязательное условие остановки
Значения этих параметров должны быть тщательно выбраны, так как они могут иметь существенное влияние на производительность процесса.
3. Задача коммивояжера
Задача коммивояжера (TSP) — самая известная в современном мире задача оптимизации информатики.
Проще говоря, это задача поиска оптимального маршрута между узлами в графе. Общее расстояние перемещения может быть одним из критериев оптимизации. Для получения более подробной информации о TSP, пожалуйста, посмотрите здесь .
4. Java-модель
Чтобы решить задачу TSP, нам понадобятся два класса моделей, а именно City и Travel . В первом мы будем хранить координаты узлов графа:
@Data
public class City {
private int x;
private int y;
public City() {
this.x = (int) (Math.random() * 500);
this.y = (int) (Math.random() * 500);
}
public double distanceToCity(City city) {
int x = Math.abs(getX() - city.getX());
int y = Math.abs(getY() - city.getY());
return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
}
}
Конструктор класса City позволяет нам создавать случайные расположения городов. Логика DistanceToCity(..) отвечает за расчеты расстояния между городами.
Следующий код отвечает за моделирование тура коммивояжера. Начнем с генерации начального порядка городов в путешествии:
public void generateInitialTravel() {
if (travel.isEmpty()) {
new Travel(10);
}
Collections.shuffle(travel);
}
В дополнение к генерации начального порядка нам нужны методы для замены двух случайных городов в порядке следования. Мы будем использовать его для поиска лучших решений внутри алгоритма имитации отжига:
public void swapCities() {
int a = generateRandomIndex();
int b = generateRandomIndex();
previousTravel = new ArrayList<>(travel);
City x = travel.get(a);
City y = travel.get(b);
travel.set(a, y);
travel.set(b, x);
}
Кроме того, нам нужен метод для отмены генерации свопа на предыдущем шаге, если новое решение не будет принято нашим алгоритмом:
public void revertSwap() {
travel = previousTravel;
}
Последний метод, который мы хотим охватить, — это расчет общего расстояния перемещения, которое будет использоваться в качестве критерия оптимизации:
public int getDistance() {
int distance = 0;
for (int index = 0; index < travel.size(); index++) {
City starting = getCity(index);
City destination;
if (index + 1 < travel.size()) {
destination = getCity(index + 1);
} else {
destination = getCity(0);
}
distance += starting.distanceToCity(destination);
}
return distance;
}
Теперь давайте сосредоточимся на основной части, реализации алгоритма имитации отжига.
5. Имитационная реализация отжига
В следующей реализации имитации отжига мы собираемся решить проблему TSP. Напомню, что цель состоит в том, чтобы найти кратчайшее расстояние для путешествия по всем городам.
Чтобы запустить процесс, нам нужно указать три основных параметра, а именно : startTemperature , numberOfIterations и coolRate :
public double simulateAnnealing(double startingTemperature,
int numberOfIterations, double coolingRate) {
double t = startingTemperature;
travel.generateInitialTravel();
double bestDistance = travel.getDistance();
Travel currentSolution = travel;
// ...
}
Перед началом моделирования мы генерируем начальный (случайный) порядок городов и вычисляем общее расстояние для проезда. Поскольку это первое рассчитанное расстояние, мы сохраняем его в переменной bestDistance вместе с currentSolution.
На следующем шаге мы запускаем основной цикл моделирования:
for (int i = 0; i < numberOfIterations; i++) {
if (t > 0.1) {
//...
} else {
continue;
}
}
Цикл будет длиться указанное нами количество итераций. Более того, мы добавили условие остановки симуляции, если температура будет ниже или равна 0,1. Это позволит нам сэкономить время моделирования, так как при низких температурах различия в оптимизации почти не видны.
Давайте посмотрим на основную логику алгоритма имитации отжига:
currentSolution.swapCities();
double currentDistance = currentSolution.getDistance();
if (currentDistance < bestDistance) {
bestDistance = currentDistance;
} else if (Math.exp((bestDistance - currentDistance) / t) < Math.random()) {
currentSolution.revertSwap();
}
На каждом шаге моделирования мы случайным образом меняем местами два города в порядке следования.
Кроме того, мы вычисляем currentDistance . Если вновь вычисленное значение currentDistance меньше значения bestDistance , мы сохраняем его как лучшее.
В противном случае мы проверяем, не меньше ли функция распределения вероятностей Больцмана, чем случайно выбранное значение в диапазоне от 0 до 1. Если да, то отменяем обмен городами. Если нет, сохраняем новый порядок городов, так как это может помочь нам избежать локальных минимумов.
Наконец, на каждом этапе симуляции мы уменьшаем температуру на заданную скорость охлаждения:
t *= coolingRate;
После симуляции мы возвращаем лучшее решение, найденное с помощью Simulated Annealing.
Обратите внимание на несколько советов о том, как выбрать наилучшие параметры моделирования:
- для небольших пространств решения лучше понизить начальную температуру и увеличить скорость охлаждения, так как это сократит время моделирования без потери качества
- для больших объемов решения выберите более высокую начальную температуру и меньшую скорость охлаждения, так как будет больше локальных минимумов
- всегда предоставляйте достаточно времени для имитации перехода от высокой к низкой температуре системы
Не забудьте потратить некоторое время на настройку алгоритма с меньшим экземпляром задачи, прежде чем приступить к основному моделированию, так как это улучшит окончательные результаты. На примере алгоритма Simulated Annealing была показана настройка в этой статье .
6. Заключение
В этом кратком руководстве мы смогли узнать об алгоритме имитации отжига и решили задачу коммивояжера . Мы надеемся, что это показывает, насколько удобен этот простой алгоритм применительно к определенным типам задач оптимизации.
Полную реализацию этой статьи можно найти на GitHub .