Отжиг: иногда соглашаться на худшее

Если ты запишешь правило принятия хода в отжиге, объяснишь, зачем температуру понижают постепенно, и знаешь, что ломается при слишком высокой и слишком низкой температуре, листай до «Теперь сам».

Как думаешь, зачем шагать к худшему

Функция на числах от 0 до 59: в целом она убывает к точке 50, но в каждой точке, не кратной шести, стоит «забор» высотой 10. Старт в нуле. Спуск смотрит на соседей: в единице забор, значение больше - шагать некуда. Поиск закончился, не начавшись, со значением 150 при минимуме 6.

Ответь себе до чтения: что нужно разрешить поиску, чтобы он перелез через забор? Очевидно - иногда соглашаться на ухудшение. Но как часто? Всегда соглашаться - это случайное блуждание, оно никуда не стремится. Никогда - это спуск, он застревает. Ответ отжига: соглашаться тем реже, чем больше ухудшение, и тем реже, чем дольше идёт поиск.

На что это похоже

Металл, который медленно остывает после нагрева. Пока он горячий, атомы прыгают с места на место, в том числе в неудобные положения. По мере остывания прыжки затихают, и атомы успевают выстроиться в правильную решётку с наименьшей энергией. Если металл закалить - резко охладить, - атомы замрут там, где их застал холод, и решётка выйдет с дефектами.

Резкое охлаждение - это спуск: он фиксирует первое попавшееся положение. Медленное - отжиг: сначала дать системе побродить, потом постепенно успокоить. Название метода (Киркпатрик, Гелатт, Векки, 1983) взято из металлургии буквально.

Механизм: правило Метрополиса с убывающей температурой

x = стартовое решение;  T = T0
повторять:
    y = случайный сосед x
    рост = f(y) − f(x)
    если рост <= 0:                     принять: y лучше или не хуже
    иначе с вероятностью e^(−рост / T): принять ухудшение
    T = T · a                           a чуть меньше 1, например 0.998

Почему именно e^(−рост / T). В разделе о случайности правило Метрополиса строило цепь, которая посещает состояния с заранее заданными весами: переход принимается с вероятностью «вес нового, делённый на вес старого, но не больше единицы». Возьмём вес решения e^(−f(x) / T). Тогда отношение весов равно e^(−(f(y) − f(x)) / T) - ровно правило отжига. Значит, при постоянной температуре поиск проводит в каждом решении время, пропорциональное e^(−f / T) (если сосед выбирается симметрично, как в разделе о Метрополисе): хорошие решения посещаются чаще плохих.

Насколько чаще, решает T. Два решения с разницей 10: при T = 100 их веса отличаются в e^0,1 ≈ 1,1 раза - почти поровну; при T = 1 - в e^10 ≈ 22 000 раз. При высокой температуре цепь бродит почти без предпочтений, при низкой почти всё время сидит в хороших решениях той области, где оказалась. Понижение температуры переводит поиск из первого режима во второй.

Что гарантирует теория. Если понижать температуру очень медленно - как c / ln k на шаге k ≥ 2, где c не меньше глубины самой глубокой ловушки (Хайек, 1988), - отжиг с вероятностью, стремящейся к единице, приходит в глобальный оптимум. Но такое охлаждение настолько медленное, что на практике его не дожидаются. На практике понижают геометрически, умножением на a, и гарантию теряют: остаётся эвристика с хорошей репутацией.

Правило

Отжиг принимает улучшение всегда, а ухудшение на рост - с вероятностью e^(−рост / T); температура T понижается от шага к шагу. Высокая температура - поиск бродит и перелезает через ловушки, низкая - спускается. Параметры подбирают так, чтобы в начале принималась заметная доля ухудшений, а в конце почти ни одного.

Разбор: забор высотой десять

f - функция с забором: в точках, кратных шести, значение 3 · |x − 50|, в остальных на 10 больше. Минимум 6 в точке 48. Сосед - число на единицу больше или меньше. «Холодно» - температура 0,01, при ней ухудшение на 7 принимается с вероятностью e^(−700), то есть никогда: это спуск. Отжиг стартует с T = 10 и умножает её на 0,998 каждый шаг - за 2000 шагов до 0,18. Шаг за край отрезка просто пропускается, но температура падает и на нём.

import math
import random

def f(x):
    if x % 6 == 0:
        return 3 * abs(x - 50)
    return 3 * abs(x - 50) + 10

def otzhig(t, ohlazhdenie, shagov):
    x = 0
    for k in range(shagov):
        y = x + random.choice([-1, 1])
        if 0 <= y <= 59:
            rost = f(y) - f(x)
            if rost <= 0 or random.random() < math.exp(-rost / t):
                x = y
        t = t * ohlazhdenie
    return [x, f(x)]

random.seed(1)
print("холодно", otzhig(0.01, 1, 2000))
for zerno in [1, 2, 3]:
    random.seed(zerno)
    print("отжиг", zerno, otzhig(10, 0.998, 2000))

холодно [0, 150]
отжиг 1 [48, 6]
отжиг 2 [48, 6]
отжиг 3 [48, 6]

Спуск не сдвинулся с нуля: слева ничего нет, справа забор. Отжиг с тремя разными зёрнами генератора все три раза пришёл в минимум.

Посчитаем, почему забор проходим. Шаг из 6 в 7 - рост −3 + 10 = 7, при T = 10 он принимается с вероятностью e^(−0,7) ≈ 0,5. Шаг из 7 в 8 - снова за забором, рост −3, принимается всегда. Из 8 до 12 дорога вниз. Пока температура высокая, заборы перелезаются через раз. Ближе к концу T ≈ 0,2, и ухудшение на 7 принимается с вероятностью e^(−35) - поиск заперт в той ямке, где оказался, и это уже ямка у минимума.

Разбор: три температуры на маршруте

20 случайных точек, соседство 2-opt: кусок маршрута между двумя случайными позициями разворачивается. Три режима по 2500 шагов из одного и того же старта: почти нулевая температура (спуск со случайным выбором хода), отжиг от 20 с множителем 0,9983 (к концу около 0,3) и постоянная температура 2000. prinyato_huzhe считает принятые ухудшения.

import math
import random

def matrica(tochki):
    d = []
    for a in tochki:
        stroka = []
        for b in tochki:
            dx = a[0] - b[0]
            dy = a[1] - b[1]
            stroka.append(math.sqrt(dx * dx + dy * dy))
        d.append(stroka)
    return d

def dlina(d, m):
    s = 0
    for i in range(len(m)):
        s = s + d[m[i - 1]][m[i]]
    return s

def otzhig(d, t, ohlazhdenie, shagov):
    n = len(d)
    m = list(range(n))
    tek = dlina(d, m)
    luchshee = tek
    prinyato_huzhe = 0
    for k in range(shagov):
        i = random.randrange(1, n - 1)
        j = random.randrange(i + 1, n)
        a = m[i - 1]
        b = m[i]
        c = m[j]
        e = m[(j + 1) % n]
        rost = d[a][c] + d[b][e] - d[a][b] - d[c][e]
        if rost <= 0 or random.random() < math.exp(-rost / t):
            m = m[:i] + m[i:j + 1][::-1] + m[j + 1:]
            tek = tek + rost
            luchshee = min(luchshee, tek)
            if rost > 0:
                prinyato_huzhe = prinyato_huzhe + 1
        t = t * ohlazhdenie
    return [round(tek, 1), round(luchshee, 1), prinyato_huzhe]

random.seed(5)
tochki = []
for i in range(20):
    tochki.append([random.randint(0, 100), random.randint(0, 100)])
d = matrica(tochki)
for rezhim in [[0.001, 1], [20, 0.9983], [2000, 1]]:
    random.seed(9)
    print(rezhim, otzhig(d, rezhim[0], rezhim[1], 2500))

[0.001, 1] [440.7, 440.7, 0]
[20, 0.9983] [426.3, 426.3, 77]
[2000, 1] [1266.2, 813.3, 1265]

Столбцы: последний маршрут, лучший найденный, число принятых ухудшений. Спуск: ни одного ухудшения, финиш 440,7 - дальше этого спуск со случайным выбором ходов за 2500 шагов не продвинулся. Отжиг принял 77 ухудшений и пришёл к 426,3. Постоянный жар: 1265 ухудшений из 2500 шагов - каждый второй ход хуже предыдущего, - последний маршрут 1266,2 мало отличается от случайного, а лучший, что попадался по дороге, - 813,3. Без запоминания лучшего жаркий поиск теряет даже его. При T = 2000 разница в длине 100 даёт множитель e^(−0,05) ≈ 0,95: поиск почти не различает хорошее и плохое.

Одна пара прогонов ничего не доказывает: на другом зерне спуск может прийти туда же, куда отжиг. Сравнивать методы надо на многих стартах и при равном бюджете - это следующий урок, и он покажет, что против перезапусков спуска отжиг выигрывает не всегда.

Что ломается без этого

Начальная температура не по масштабу. Температура измеряется в единицах цели. Для маршрута в километрах T = 20 - разумно, в метрах - уже лёд: ухудшение на 1000 метров почти никогда не пройдёт. Практичный способ: сделать сотню пробных ходов и подобрать T0 так, чтобы принималась примерно половина ухудшений.

Охлаждение слишком быстрое. Множитель 0,9 за шаг замораживает поиск за пару десятков шагов - это спуск с лишними расходами.

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

Ждут гарантии. При геометрическом охлаждении её нет. Отжиг - эвристика: его проверяют замером, а не доказательством.

Зачем это в работе

Отжиг хорош там, где есть цель и понятное соседство, а структуры для точного метода нет: размещение элементов на кристалле (с этого он и начинался), раскладка экзаменов по аудиториям, подбор параметров расписания, разбиение графа. Его любят за то, что он пишется за полчаса поверх любого локального поиска: меняется одна строка - условие принятия хода. И за то, что у него есть ручка, понятная заказчику: «дадите больше времени - охладим медленнее, ответ обычно станет лучше».

Теперь сам

1. Ухудшение на 5 при T = 10. С какой вероятностью оно будет принято? А при T = 1?
2. Через 1000 шагов с множителем 0,998 во сколько раз упадёт температура?
3. Что получится, если в отжиге принимать ухудшения с постоянной вероятностью 0,1, независимо от их размера?