Алгоритм имитации отжига (Simulated Annealing, SA)

Алгоритм имитации отжига (Simulated Annealing, SA) — это вероятностный метаэвристический алгоритм для нахождения глобального минимума (или максимума) функции, особенно в больших, сложных и многоэкстремальных пространствах поиска.

Название и основная идея пришли из металлургии, из процесса отжига металлов.

Аналогия с металлургией (Отжиг)

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

Ключевой момент: Если охлаждать металл слишком быстро (закалка), атомы “застывают” в неупорядоченном состоянии с высокой энергией (локальный минимум). Медленное охлаждение дает им шанс “выбраться” из локальных энергетических ям и найти глобальный минимум энергии.

Как это переносится на алгоритмическую задачу?

Представьте, что у вас есть сложная задача (например, коммивояжер, размещение элементов на микросхеме, настройка параметров). У нее есть:

Состояние (State): Любое возможное решение (например, конкретный маршрут).
Энергия (Energy): Значение целевой функции, которую мы хотим минимизировать (например, длина маршрута). Чем короче маршрут, тем “ниже энергия”.
Цель: Найти состояние с минимальной “энергией” (глобальный минимум).

Алгоритм по шагам:

Инициализация:
- Задаем начальное состояние S (может быть случайным).
- Задаем начальную высокую “температуру” T (это параметр алгоритма, а не реальная температура).
- Задаем график охлаждения (schedule) — правило, по которому T будет уменьшаться.
Основной цикл (пока не выполнен критерий остановки: температура не упала до минимума или не сделано много шагов):
- Генерация соседа: Создаем новое состояние S_new, слегка изменяя текущее S (например, поменяв местами два города в маршруте).
- Оценка изменения: Вычисляем разницу энергий ΔE = E(S_new) - E(S).
- Принятие решения:
  - Если ΔE < 0 (новое состояние лучше), мы всегда переходим в него: S = S_new.
  - Если ΔE >= 0 (новое состояние хуже), мы переходим в него с вероятностью P = exp(-ΔE / T).
    - Вот сердце алгоритма! На высоких T вероятность P близка к 1 — алгоритм часто принимает плохие решения, активно исследуя пространство (аналог хаотичного движения атомов).
    - С падением T вероятность P уменьшается. На низких T алгоритм почти всегда отвергает ухудшения, концентрируясь на локальном улучшении (эксплуатации найденной области).
Понижение температуры: Согласно графику охлаждения, уменьшаем T (например, T = T * α, где α = 0.95 ... 0.99).
Завершение: Возвращаем лучшее найденное состояние.

Псевдокод (очень упрощенно)

S = S_initial           // Начальное решение
T = T_initial           // Начальная "температура"
best = S

while (T > T_min) {
    for (i = 0; i < num_iterations_per_T; i++) {
        S_new = generate_neighbor(S)   // Создать соседа
        ΔE = cost(S_new) - cost(S)

        if (ΔE < 0 || random() < exp(-ΔE / T)) {
            S = S_new                   // Принять новое состояние
        }

        if (cost(S) < cost(best)) {
            best = S                    // Запомнить лучшее
        }
    }
    T = cool(T)                         // Охладить систему
}

return best

Ключевые преимущества:

Умение избегать локальных минимумов: За счет вероятностного принятия плохих решений на ранних этапах.
Универсальность: Применим к огромному классу задач оптимизации, где есть способ сгенерировать “соседа”.
Простота реализации.

Недостатки:

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

Пример задачи: Коммивояжер (TSP)

Состояние: Маршрут, проходящий через все города.
Энергия: Общая длина маршрута.
Генерация соседа: Поменять местами два случайных города в маршруте.
Алгоритм: Начинает с случайного длинного маршрута, пробует перестановки, иногда соглашается на удлинение маршрута (чтобы “перепрыгнуть” через гору), и постепенно “охлаждается”, оттачивая короткий маршрут.

LDS