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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Общее описание[править | править вики-текст]

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

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

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

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

P(\overline{x^*}\to\overline{x_{i+1}}\mid\overline{x_i})=\left\{
\begin{matrix}
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{matrix}\right\}.

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

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

Применение[править | править вики-текст]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • Каллан Роберт.  Основные концепции нейронных сетей. — М.: Издательский дом Вильямс, 2003. — 288 с. — ISBN 5-8459-0219-X. — С. 146—148.
  • Кирсанов М. Н.  Графы в Maple. — М.: Физматлит, 2007. — 168 с. — ISBN 978-5-9221-0745-7. — С. 151—154.
  • Джонс М. Т.  Программирование искусственного интеллета в приложениях. — М.: ДМК Пресс, 2004. — 312 с. — ISBN 5-94074-275-0. — С. 25—42.


Ссылки[править | править вики-текст]