Русская Википедия:Алгоритм имитации отжига
Алгори́тм имита́ции о́тжига (Шаблон:Lang-en) — общий алгоритмический метод решения задачи глобальной оптимизации, особенно дискретной и комбинаторной оптимизации. Один из примеров методов Монте-Карло.
Общее описание
Алгоритм основывается на имитации физического процесса, который происходит при кристаллизации вещества, в том числе при отжиге металлов. Предполагается, что атомы вещества уже почти выстроены в кристаллическую решётку, но ещё допустимы переходы отдельных атомов из одной ячейки в другую. Активность атомов тем больше, чем выше температура, которую постепенно понижают, что приводит к тому, что вероятность переходов в состояния с большей энергией уменьшается. Устойчивая кристаллическая решётка соответствует минимуму энергии атомов, поэтому атом либо переходит в состояние с меньшим уровнем энергии, либо остаётся на месте. (Этот алгоритм также называется алгоритмом Н. Метрополиса, по имени его автора).
Моделирование похожего процесса используется для решения задачи глобальной оптимизации, состоящей в нахождении такой точки или множества точек, на которых достигается минимум некоторой целевой функции <math>F(x)</math> ("энергия системы"), где <math>{x}\in X</math> (<math>{x}</math> — "состояние системы", <math>X</math> — множество всех состояний).
Алгоритм поиска минимума методом имитации отжига предполагает свободное задание:
- <math>{x_0}\in X</math> — начального состояния системы;
- оператора <math>A({x},i):X\times \mathbb{N}\to X</math>, случайно генерирующего новое состояние системы после i-ого шага с учётом текущего состояния <math>{x}</math> (этот оператор, с одной стороны, должен обеспечивать достаточно свободное случайное блуждание по пространству <math>X</math>, а с другой — работать в некоторой степени целенаправленно, обеспечивая быстроту поиска);
- <math>T_i>0</math> — убывающей к нулю положительной последовательности, которая задаёт аналог понижающейся температуры в кристалле. Скорость остывания (закон убывания) также может задаваться (и варьироваться) произвольно, что придаёт алгоритму значительной гибкости.
Алгоритм генерирует процесс случайного блуждания по пространству состояний <math>X</math>. Решение ищется последовательным вычислением точек <math>{x_0},\;{x_1},\;{x_2},\;\ldots,\;</math> пространства <math>X</math>; каждая точка, начиная с <math>{x_1}</math>, «претендует» на то, чтобы лучше предыдущих приближать решение. На каждом шаге алгоритм (который описан ниже) вычисляет новую точку и понижает значение величины (изначально положительной), понимаемой как «температура».
Последовательность этих точек (состояний) получается следующим образом. К точке <math>{x_i}</math> применяется оператор <math>A</math>, в результате чего получается точка-кандидат <math>{x^*_i}=A(x_i,i)</math>, для которой вычисляется соответствующее изменение "энергии" <math>\Delta F_i=F({x^*_i})-F({x_i})</math>. Если энергия понижается (<math>\Delta F_i\leq 0</math>), осуществляется переход системы в новое состояние: <math>{x_{i+1}}={x^*_i}</math>. Если энергия повышается (<math>\Delta F_i>0</math>), переход в новое состояние может осуществиться лишь с некоторой вероятностью, зависящей от величины повышения энергии и текущей температуры, в соответствии с законом распределения Гиббса:
- <math>P({x^*_i}\to{x_{i+1}}\mid{x_i})=\exp(-\Delta F_i/{T_i})</math>
Если переход не произошёл, состояние системы остаётся прежним: <math>{x_{i+1}}={x_i}</math>. Алгоритм останавливается по достижении точки, которая оказывается при температуре ноль.
Алгоритм имитации отжига похож на градиентный спуск, но за счёт случайности выбора промежуточной точки и возможности выбираться из локальных минимумов должен реже застревать в локальных, но не глобальных минимумах, чем градиентный спуск. Алгоритм имитации отжига не гарантирует нахождения минимума функции, однако при правильной настройке генерации случайной точки в пространстве <math>X</math>, как правило, происходит улучшение начального приближения.
Применение
- Обучение нейронных сетей
- Решение комбинаторных задач, например, задачи о расстановке ферзей
- Решение задачи коммивояжера[1]
См. также
Примечания
Литература
- Шаблон:Книга — С. 146—148.
- Шаблон:Книга — С. 151—154.
- Шаблон:Книга — С. 25—42.
Ссылки
- Визуализатор применения метода отжига в задаче о расстановке ферзей.
- Метод глобальной минимизации (последовательный спуск по точкам локальных минимумов).
- Лекция по методу отжига
Шаблон:Методы оптимизации Шаблон:Rq
