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

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

Общее описаниеПравить

 

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

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

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

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

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

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

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

$P(x_i^{\ast <!--\; \ast \; -->}\to <!--\; \to \; -->x_{i+1}\mid <!--\; \mid \; -->x_i)=\exp <!--\; \; -->(-<!--\; -\; -->\mathrm{\Delta <!--\; \Delta \; -->}{F}_i/T_i)$$P({x_{i}^{*}}\to {x_{i+1}}\mid {x_{i}})=\exp(-\Delta F_{i}/{T_{i}})$ 

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

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

СсылкиПравить

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