Алгоритмы: Метод имитации отжига

  

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

Описание

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

При помощи моделирования такого процесса ищется такая точка или множество точек, на котором достигается минимум некоторой числовой функции ${\displaystyle F({\overline {x}})}$, где ${\displaystyle {\overline {x}}=(x_{1},\;\ldots ,\;x_{m})\in X}$. Решение ищется последовательным вычислением точек ${\displaystyle {\overline {x_{0}}},\;{\overline {x_{1}}},\;\ldots ,\;}$ пространства ${\displaystyle X}$; каждая точка, начиная с ${\displaystyle {\overline {x_{1}}}}$, «претендует» на то, чтобы лучше предыдущих приближать решение. Алгоритм принимает точку ${\displaystyle {\overline {x_{0}}}}$ как исходные данные. На каждом шаге алгоритм (который описан ниже) вычисляет новую точку и понижает значение величины (изначально положительной), понимаемой как «температура». Алгоритм останавливается по достижении точки, которая оказывается при температуре ноль.

Точка ${\displaystyle {\overline {x_{i+1}}}}$ по алгоритму получается на основе текущей точки ${\displaystyle {\overline {x_{i}}}}$ следующим образом. К точке ${\displaystyle {\overline {x_{i}}}}$ применяется оператор ${\displaystyle \mathrm {A} }$, который случайным образом модифицирует соответствующую точку, в результате чего получается новая точка ${\displaystyle {\overline {x^{*}}}}$. Точка ${\displaystyle {\overline {x^{*}}}}$ становится точкой ${\displaystyle {\overline {x_{i+1}}}}$ с вероятностью ${\displaystyle P({\overline {x^{*}}},\;{\overline {x_{i+1}}})}$, которая вычисляется в соответствии с распределением Гиббса:

${\displaystyle P({\overline {x^{*}}}\to {\overline {x_{i+1}}}\mid {\overline {x_{i}}})={\begin{cases}1,&F({\overline {x^{*}}})-F({\overline {x_{i}}})<0\\\exp \left(-{\dfrac {F({\overline {x^{*}}})-F({\overline {x_{i}}})}{Q_{i}}}\right),&{F({\overline {x^{*}}})-F({\overline {x_{i}}})\geqslant 0}\end{cases}}}$

Здесь ${\displaystyle Q_{i}>0}$ — элементы произвольной убывающей, сходящейся к нулю положительной последовательности, которая задаёт аналог падающей температуры в кристалле. Скорость убывания и закон убывания могут быть заданы по желанию создателя алгоритма.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P — вероятность принять измененное решение,

δE — модуль разности между энергией оптимального решения и энергий измененного решения,

T — текущая температура.

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

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

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