Метод имитации отжига: Оптимизация сложных задач

1.

Метод имитации отжига: Оптимизация сложных
задач
Сегодня мы погрузимся в мир вероятностных методов оптимизации, сосредоточившись на методе имитации отжига
(Simulated Annealing). Этот мощный инструмент часто применяется для решения сложных комбинаторных задач,
которые встречаются повсюду в реальной жизни: от маршрутизации и распределения ресурсов до планирования.
Классический пример — задача коммивояжера, известная своей NP-трудностью и отсутствием быстрого точного
решения.
by gtadvs ee s imon

2.

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

3.

Имитация отжига: Идея и
аналогия
Физический отжиг
Метод имитации отжига вдохновлен процессом физического
отжига металлов. Нагретый металл медленно охлаждают,
чтобы достичь наилучшей кристаллической структуры,
минимизируя дефекты.
Аналогия в оптимизации
В задачах оптимизации мы позволяем алгоритму сначала
делать более "свободные" шаги (высокая "температура"), а
затем постепенно "остывать", всё реже принимая
ухудшающие шаги. Это помогает избежать застревания в
локальных минимумах.

4.

Как работает метод
Инициализация
Алгоритм стартует с произвольного начального решения и генерирует случайное соседнее решение.
Принятие улучшений
Если новое сгенерированное решение лучше текущего, алгоритм всегда принимает его и переходит к нему.
Вероятностное принятие ухудшений
Если новое решение хуже текущего, оно может быть принято с определённой вероятностью. Эта вероятность
уменьшается по мере снижения «температуры» и увеличения степени ухудшения.
Охлаждение и сходимость
В начале "температура" высока, позволяя алгоритму активно исследовать пространство решений. Постепенно она
снижается, что приводит к стабилизации и сходимости к оптимальному или близкому к нему решению.

5.

Шаги алгоритма имитации отжига
Начальное решение
Выбрать случайное начальное решение для оптимизации.
Соседнее решение
Сгенерировать соседнее решение, внося небольшие изменения в текущее.
Изменение стоимости
Посчитать изменение стоимости (или "энергии") нового решения по сравнению с текущим.
Принятие решения
Если новое решение лучше, принять его. Если хуже, принять с вероятностью, зависящей от текущей "температуры".
Понижение температуры
Понижать "температуру" по определённому закону (например, умножать на коэффициент меньше 1).
Повторение
Повторять шаги, пока температура не станет очень маленькой, сигнализируя о сходимости.

6.

Пример задачи: Коммивояжер
Задача
Параметры
Цель
В качестве примера мы выбрали
Мы работаем с 12 случайно
Цель — продемонстрировать, как
классическую задачу
расположенными городами на
метод имитации отжига
коммивояжера: найти
карте, что представляет собой
справляется с поиском
кратчайший маршрут,
достаточно сложную
оптимального или близкого к
проходящий через все N городов
комбинаторную задачу.
оптимальному маршрута в таких
по одному разу.
условиях.

7.

Реализация метода имитации отжига
Язык и представление
Генерация соседей
Принятие шага
Алгоритм был реализован на языке
На каждом шаге для генерации
Если длина нового маршрута
Python. Решение представляется в
"соседнего" решения меняются
становится меньше, шаг
виде перестановки номеров
местами два случайных города в
принимается. Если больше, он
городов, определяющей порядок
текущем маршруте.
принимается с вероятностью,
их посещения.
которая уменьшается по мере
снижения "температуры",
имитируя процесс отжига.

8.

Детерминированный алгоритм для сравнения
Жадный подход
Для сравнения мы реализовали жадный алгоритм. Из текущего города всегда выбирается ближайший ещё не
посещённый город.
Преимущества
Такой подход часто даёт приличные, быстро находимые решения, что делает его хорошей базой для
сравнения.
Ограничения
Однако жадный алгоритм не гарантирует оптимальности, так как он не способен выйти из локальных
минимумов.

9.

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

10.

Выводы: Преимущества имитации отжига
Глобальное решение
Способность выйти из локальных минимумов и найти глобальное или близкое к нему
решение.
Значительное улучшение
Находит решения значительно лучше жадных алгоритмов, особенно в
сложных задачах.
Простота
Несмотря на свою простоту, метод очень эффективен.
Метод имитации отжига, несмотря на свою простоту, способен находить решения значительно лучше жадных алгоритмов, особенно
в сложных задачах с множеством локальных минимумов. Главное его преимущество — возможность выйти из локальных минимумов
и найти глобальное решение, что делает его незаменимым инструментом в арсенале оптимизационных методов.