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

---

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

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

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

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

---