Имитация отжига

Ни одна из крайних температур — ни очень низкая, ни очень высокая — не является эффективным методом решения задач минимизации в целом.

Этот принцип также проявляется в физических системах: если взять твердое тело и нагреть его до очень высокой температуры, трудно ожидать сохранения стройной кристаллической структуры, даже если она предпочтительна с энергетической точки зрения; и это можно объяснить большим значением kT в выражении e–E(S)/(kT), с которым огромное количество менее выгодных состояний становится слишком вероятным.

С другой стороны, если взять расплав и очень быстро заморозить его, не стоит также рассчитывать на формирование идеальной кристаллической структуры, скорее вы получите деформированную структуру с множеством дефектов.

Дело в том, что при очень малых T мы слишком близко подходим к области градиентного спуска, и система захватывается в одном из многочисленных провалов своей гребенчатой энергетической поверхности.

Интересно заметить, что при очень малых T утверждение показывает, что в пределе большая часть времени случайных блужданий проводится в низшем энергетическом состоянии. Проблема в том, что случайное блуждание тратит слишком много времени, чтобы хотя бы отдаленно приблизиться к этому пределу.

В начале 1980-х годов ученые изучали связи между минимизацией энергии  и комбинаторной оптимизацией. Киркпатрик, Гелатт и Веччи размышляли над обсуждаемой темой и задали следующий вопрос: как решить эту задачу для физических систем и какой тип алгоритма предполагает такое решение?

В физических системах для перевода материала в кристаллическое состояние используется процесс, называемый отжигом: материал постепенно охлаждается с очень высокой температуры, что дает ему достаточно времени для достижения равновесия на промежуточных убывающих температурах.

Таким образом удается избежать энергетических минимумов, с которыми материал сталкивается на всем протяжении процесса охлаждения, и в конечном итоге достичь глобального оптимума.

Этот процесс можно попытаться смоделировать на алгоритмическом уровне; так появился алгоритмический метод, известный как имитация отжига. Метод имитации отжига основан на выполнении алгоритма Метрополиса с постепенным снижением значения T в ходе выполнения.

Конкретный способ обновления T называется по естественным причинам планом охлаждения; при его планировании учитывается целый ряд факторов. Формально план охлаждения представляет собой функцию τ, отображающую {1, 2, 3, …} на положительные вещественные числа; на итерации i алгоритма Метрополиса в определении вероятности используется температура T = τ(i).