Алгоритм имитации отжига

Материал из MachineLearning.

Алгоритм имитации отжига (Simulated annealing) — алгоритм решения различных оптимизационных задач. Он основан на моделировании реального физического процесса, который происходит при кристаллизации вещества из жидкого состояния в твёрдое, в том числе при отжиге металлов.

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

Содержание 1 Основные шаги алгоритма 1.1 Выбор начального решения 1.2 Оценка решения 1.3 Основной шаг алгоритма 1.4 Случайное изменение решения 1.5 Критерий допуска 1.6 Уменьшение температуры 1.7 Выбор начальной и пороговой температуры 2 Области применения 3 Пример работы алгоритма. Задача о расстановке ферзей 4 Литература

Основные шаги алгоритма

1. Выбор начального решения и начальной температуры
2. Оценка начального решения
3. Основной шаг алгоритма
   1. Случайное изменение текущего решения
   2. Оценка измененного решения
   3. Критерий допуска
4. Уменьшение температуры и, если температура больше некоторого порога, то переход к основному шагу

Выбор начального решения

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

Оценка решения

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

Основной шаг алгоритма

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

Случайное изменение решения

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

Критерий допуска

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

Если измененное решение имеет меньшую энергию, то оно принимается за текущее. Если же измененное решение имеет большую энергию, то оно принимается с вероятностью P = exp(-δE/T), где:

• P — вероятность принять измененное решение,
• δE — модуль разности между энергией оптимального решения и энергий измененного решения,
• T — текущая температура.

Уменьшение температуры

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

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

Выбор начальной и пороговой температуры

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

Области применения

1. Создание пути
2. Реконструкция изображения
3. Назначение задач и планирование
4. Размещение сети
5. Глобальная маршрутизация
6. Обнаружение и распознавание визуальных объектов
7. Разработка специальных цифровых фильтров

^[1]

Пример работы алгоритма. Задача о расстановке ферзей

Покажем работу алгоритма на примере классической задачи. Пусть у нас есть шахматная доска NxN. На ней требуется расставить N ферзей так, чтобы они не били друг друга. Прочесть решение данной задачи алгоритмом имитации отжига можно по следующей ссылке ^[1].

Литература

Данная статья является непроверенным учебным заданием. Студент: Участник:VovaMind Преподаватель: Участник:Константин Воронцов Срок: 1 января 2010 До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.