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

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

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

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

Алгоритм поиска минимума методом имитации отжига предполагает свободное задание:

• ${\displaystyle {x_{0}}\in X}$ — начального состояния системы;
• оператора ${\displaystyle A({x},i):X\times \mathbb {N} \to X}$ , случайно генерирующего новое состояние системы после i-ого шага с учётом текущего состояния ${\displaystyle {x}}$ (этот оператор, с одной стороны, должен обеспечивать достаточно свободное случайное блуждание по пространству ${\displaystyle X}$ , а с другой — работать в некоторой степени целенаправленно, обеспечивая быстроту поиска);
• ${\displaystyle T_{i}>0}$ — убывающей к нулю положительной последовательности, которая задаёт аналог понижающейся температуры в кристалле. Скорость остывания (закон убывания) также может задаваться (и варьироваться) произвольно, что придаёт алгоритму значительной гибкости.

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

Последовательность этих точек (состояний) получается следующим образом. К точке ${\displaystyle {x_{i}}}$ применяется оператор ${\displaystyle A}$ , в результате чего получается точка-кандидат ${\displaystyle {x_{i}^{*}}=A(x_{i},i)}$ , для которой вычисляется соответствующее изменение "энергии" ${\displaystyle \Delta F_{i}=F({x_{i}^{*}})-F({x_{i}})}$ . Если энергия понижается ( ${\displaystyle \Delta F_{i}\leq 0}$ ), осуществляется переход системы в новое состояние: ${\displaystyle {x_{i+1}}={x_{i}^{*}}}$ . Если энергия повышается ( ${\displaystyle \Delta F_{i}>0}$ ), переход в новое состояние может осуществиться лишь с некоторой вероятностью, зависящей от величины повышения энергии и текущей температуры, в соответствии с законом распределения Гиббса :

${\displaystyle P({x_{i}^{*}}\to {x_{i+1}}\mid {x_{i}})=\exp(-\Delta F_{i}/{T_{i}})}$

Если переход не произошёл, состояние системы остаётся прежним: ${\displaystyle {x_{i+1}}={x_{i}}}$ . Алгоритм останавливается по достижении точки, которая оказывается при температуре ноль.

Алгоритм имитации отжига похож на градиентный спуск , но за счёт случайности выбора промежуточной точки и возможности выбираться из локальных минимумов должен реже застревать в локальных, но не глобальных минимумах, чем градиентный спуск. Алгоритм имитации отжига не гарантирует нахождения минимума функции, однако при правильной настройке генерации случайной точки в пространстве ${\displaystyle 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.

Ссылки