Рубрики
Без рубрики

Проблема коммивояжера на Java

Краткое введение в имитацию отжига для задачи коммивояжера на Java.

Автор оригинала: baeldung.

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 позволяет создавать случайные местоположения городов. Логика расстояние до города(..) отвечает за вычисления расстояния между городами.

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

public void generateInitialTravel() {
    if (travel.isEmpty())
        new Travel(10);
    Collections.shuffle(travel);
}

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

public void swapCities() {
    int a = generateRandomIndex();
    int b = generateRandomIndex();
    previousTravel = 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. Просто небольшое напоминание, цель состоит в том, чтобы найти кратчайшее расстояние для путешествия по всем городам.

Для того, чтобы запустить процесс, нам нужно предоставить три основных параметра, а именно начальная Температура , количество итераций и Скорость охлаждения :

public double simulateAnnealing(double startingTemperature,
  int numberOfIterations, double coolingRate) {
    double t = startingTemperature;
    travel.generateInitialTravel();
    double bestDistance = travel.getDistance();

    Travel currentSolution = travel;
    // ...
}

Перед началом моделирования мы генерируем начальный (случайный) порядок городов и вычисляем общее расстояние для путешествия. Поскольку это первое вычисленное расстояние, мы сохраняем его в переменной best Distance вместе с 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();
}

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

Кроме того, мы вычисляем текущее расстояние . Если вновь рассчитанное текущее расстояние меньше , чем лучшее расстояние , мы сохраняем его как лучшее.

В противном случае мы проверяем, является ли функция распределения вероятностей Больцмана ниже случайно выбранного значения в диапазоне от 0 до 1. Если да, мы отменяем обмен городами. Если нет, мы сохраняем новый порядок городов, так как это может помочь нам избежать локальных минимумов.

Наконец, на каждом этапе моделирования мы снижаем температуру на скорость охлаждения:

t *= coolingRate;

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

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

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

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

6. Заключение

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

Полную реализацию этой статьи можно найти на GitHub .