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

Алгори́тм имита́ции о́тжига () — общий алгоритмический метод решения задачи глобальной оптимизации, особенно дискретной и комбинаторной оптимизации. Один из примеров методов Монте-Карло.

Общее описание 

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

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

Алгоритм поиска минимума методом имитации отжига предполагает свободное задание:
  — начального состояния системы;
 оператора , случайно генерирующего новое состояние системы после i-ого шага с учётом текущего состояния  (этот оператор, с одной стороны, должен обеспечивать достаточно свободное случайное блуждание по пространству , а с другой — работать в некоторой степени целенаправленно, обеспечивая быстроту поиска);
  — убывающей к нулю положительной последовательности, которая задаёт аналог понижающейся температуры в кристалле. Скорость остывания (закон убывания) также может задаваться (и варьироваться) произвольно, что придаёт алгоритму значительной гибкости.

Алгоритм генерирует процесс случайного блуждания по пространству состояний .
Решение ищется последовательным вычислением точек  пространства ; каждая точка, начиная с , «претендует» на то, чтобы лучше предыдущих приближать решение. На каждом шаге алгоритм (который описан ниже) вычисляет новую точку и понижает значение величины (изначально положительной), понимаемой как «температура». 

Последовательность этих точек (состояний) получается следующим образом. К точке  применяется оператор , в результате чего получается точка-кандидат , для которой вычисляется соответствующее изменение "энергии" . Если энергия понижается (), осуществляется переход системы в новое состояние: . Если энергия повышается (), переход в новое состояние может осуществиться лишь с некоторой вероятностью, зависящей от величины повышения энергии и текущей температуры, в соответствии с законом распределения Гиббса:
 
Если переход не произошёл, состояние системы остаётся прежним: .
Алгоритм останавливается по достижении точки, которая оказывается при температуре ноль.

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

Применение 
 Обучение нейронных сетей
 Решение комбинаторных задач, например, задачи о расстановке ферзей
 Решение задачи коммивояжера

См. также 
 Метод квантового отжига

Примечания

Литература 
  — С. 146—148.
  — С. 151—154.
  — С. 25—42.

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

Эвристические алгоритмы
Алгоритмы оптимизации
Комбинаторная оптимизация
Метод Монте-Карло