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

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

Имитация отжига (simulated annealing) — стохастический метод глобальной оптимизации, принимающий ухудшающие шаги с вероятностью $\exp(-\Delta/T)$, где $T$ — медленно убывающая «температура».

Зачем нужны метаэвристики

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

Физическая метафора

При отжиге металла его медленно охлаждают: при высокой температуре атомы свободно перескакивают (даже в менее выгодные позиции), а по мере остывания «застывают» в низкоэнергетической, почти идеальной кристаллической решётке. Алгоритм копирует это: «энергия» — значение цели $f$, «температура» $T$ управляет готовностью принимать ухудшения.

Правило приёма (критерий Метрополиса)

Сгенерировали соседнее решение с изменением цели $\Delta=f_{\text{new}}-f_{\text{cur}}$. Принимаем его так:

$$P(\text{принять})=\begin{cases}1,& \Delta\le0\ (\text{лучше — всегда берём}),\\[1mm]\exp(-\Delta/T),& \Delta>0\ (\text{хуже — иногда берём}).\end{cases}$$

При высоком $T$ даже сильные ухудшения вероятны — метод свободно бродит и убегает из впадин. При $T\to0$ ухудшения почти запрещены — метод превращается в обычный жадный спуск и фиксирует найденное. Ключ — медленное охлаждение (cooling schedule), обычно $T\leftarrow\gamma T$ с $\gamma\approx 0.99$.

Отжиг на коммивояжёре

Задача коммивояжёра: объехать все города по кратчайшему замкнутому маршруту. Соседнее решение — перестановка двух городов в маршруте. Запустим отжиг на 6 городах (seed фиксирован для воспроизводимости).

import random, math

cities = [(0,0),(1,5),(5,2),(6,6),(8,3),(2,8)]
def dist(a, b):
    return math.hypot(cities[a][0]-cities[b][0], cities[a][1]-cities[b][1])
def tour_len(t):
    return sum(dist(t[i], t[(i+1) % len(t)]) for i in range(len(t)))

random.seed(42)
tour = list(range(len(cities)))
random.shuffle(tour)
cur = tour_len(tour)
best, best_len = tour[:], cur
T = 10.0
for step in range(1, 2001):
    i, j = random.sample(range(len(cities)), 2)
    new = tour[:]
    new[i], new[j] = new[j], new[i]
    nl = tour_len(new)
    if nl < cur or random.random() < math.exp((cur - nl) / T):
        tour, cur = new, nl
        if cur < best_len:
            best, best_len = tour[:], cur
    T *= 0.997
    if step in (1, 500, 1000, 2000):
        print(f"шаг {step:4d}: T={T:.3f} текущая={cur:.3f} лучшая={best_len:.3f}")
print("Лучший маршрут:", best)
print("Длина:", round(best_len, 3))

Вывод:

шаг    1: T=9.970 текущая=33.085 лучшая=33.085
шаг  500: T=2.226 текущая=31.920 лучшая=24.886
шаг 1000: T=0.496 текущая=24.886 лучшая=24.886
шаг 2000: T=0.025 текущая=24.886 лучшая=24.886
приведённое сокращено

На шаге 500 текущая длина ($31.9$) хуже лучшей ($24.9$) — метод осознанно «гуляет» по плохим решениям, пока тепло. По мере остывания он застывает в найденном хорошем маршруте длиной $\approx24.9$. Чистый жадный спуск с того же старта застрял бы в первом же локальном минимуме.

Как работает под капотом

Магия — в члене $\exp(-\Delta/T)$. Это распределение Больцмана из статистической физики. Доказано: при достаточно медленном (логарифмическом) охлаждении отжиг сходится к глобальному оптимуму с вероятностью 1. На практике такое расписание непозволительно медленно, поэтому берут геометрическое ($T\leftarrow\gamma T$) и довольствуются «очень хорошим» решением. Баланс прост: остужать быстро — застрянешь рано (как жадный спуск); остужать медленно — найдёшь лучше, но дольше.

Частые ошибки

• Слишком быстрое охлаждение. $T$ падает раньше, чем метод успел исследовать — застреваем в локальном минимуме.
• Не хранить лучшее найденное. Текущее решение из-за приёма ухудшений может быть хуже исторического лучшего — всегда запоминайте best.
• Старт с $T$, не связанной с масштабом $\Delta$. $T$ должна быть соизмерима с типичными изменениями цели, иначе приём всегда $\approx0$ или $\approx1$.

Итоги

• Отжиг принимает ухудшения с вероятностью $\exp(-\Delta/T)$, что позволяет убегать из локальных минимумов.
• Высокая $T$ — свободное блуждание, $T\to0$ — жадная фиксация; ключ в медленном охлаждении.
• Работает и для невыпуклых, и для дискретных задач (коммивояжёр); всегда храните лучшее решение.