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

Алгоритм оптимизации имитации отжига в Java

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

Автор оригинала: Luka Čupić.

Вступление

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

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

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

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

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

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

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

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

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

$$ \Дельта-E_1 $$

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

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

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

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

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

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

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

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

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

Кредит: Википедия

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

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

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

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

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

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

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

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

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

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

Кредит: Википедия

Мотивация

Git Essentials

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

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

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

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

Кредит: Учебная точка

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

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

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

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

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

Реализация

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

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

Класс Город довольно прост. Он представляет город в двумерном пространстве с координатами 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 cities;
    private int distance;

    public Tour(List 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()
}

Последним вспомогательным классом, который необходимо упомянуть, является класс Утилита , содержащий методы вероятность() и расстояние() :

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 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 .

Вывод

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

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