Перезапуски, табу и честный замер эвристик

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

Как думаешь, кто выиграет

Шестнадцать задач надо поделить между двумя серверами так, чтобы суммы длительностей были как можно ближе - задача о разбиении из прошлой главы. Бюджет - 600 оценок цели. Три участника: один спуск на все 600 оценок; десять спусков по 60 оценок из разных стартов; отжиг на 600 оценок. Оптимум известен точно: разница сумм 0, его даёт таблица достижимых сумм.

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

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

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

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

Механизм: три способа не стоять на холме

Перезапуски. Спуск из случайного старта находит оптимум с вероятностью p. Десять независимых спусков промахнутся все сразу с вероятностью (1 − p)¹⁰, то есть найдут оптимум с вероятностью 1 − (1 − p)¹⁰. При p = 0,2 это 0,89. Главное условие: каждый спуск должен успевать дойти до своего локального оптимума. Если спуск застревает за 40 оценок, а ему выдали 600, - 560 потрачены на стояние на месте.

Поиск с запретами (табу, Гловер, 1986). На каждом шаге - к лучшему соседу, даже если он хуже текущего. Без запретов это ломается сразу: из локального оптимума шаг вверх, а оттуда лучший сосед - тот же оптимум, и поиск качается между двумя решениями. Поэтому ход, только что сделанный, запрещают отменять на srok шагов. Исключение: запрещённый ход разрешён, если даёт решение лучше всех найденных.

повторять:
    из соседей, которых не запрещено трогать
    (или которые дают новый рекорд), выбрать лучший -
    даже если он хуже текущего
    сделать ход; запретить отменять его следующие srok шагов
    запомнить рекорд

Честный замер. Сравнивать можно только при равном бюджете, и мерить бюджет надо в оценках цели, а не в «прогонах» и не в секундах на разных машинах. Зёрен - десятки, и печатается разброс: сколько раз найден оптимум, среднее, худшее. Эталон - точный ответ (если он есть) или нижняя граница, иначе «на 3% лучше конкурента» может значить «на 40% хуже оптимума у обоих».

Правило

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

Разбор: спуск, перезапуски и отжиг при равном бюджете

tochno - таблица достижимых сумм: точный оптимум. poisk - спуск или отжиг (при температуре 0,001 ухудшения не принимаются никогда); сосед - перенести одно число на другой сервер, разница пересчитывается за одно действие. perezapuski делит бюджет на десять спусков.

import math
import random

def tochno(chisla):
    vsego = sum(chisla)
    dost = [False] * (vsego // 2 + 1)
    dost[0] = True
    for x in chisla:
        for s in range(vsego // 2, x - 1, -1):
            if dost[s - x]:
                dost[s] = True
    s = vsego // 2
    while not dost[s]:
        s = s - 1
    return vsego - 2 * s

def poisk(chisla, t, ohlazhdenie, ocenok):
    n = len(chisla)
    storona = []
    raznica = 0
    for x in chisla:
        storona.append(random.choice([-1, 1]))
        raznica = raznica + storona[-1] * x
    luchshee = abs(raznica)
    for k in range(ocenok):
        i = random.randrange(n)
        nova = raznica - 2 * storona[i] * chisla[i]
        rost = abs(nova) - abs(raznica)
        if rost <= 0 or random.random() < math.exp(-rost / t):
            storona[i] = -storona[i]
            raznica = nova
            luchshee = min(luchshee, abs(raznica))
        t = t * ohlazhdenie
    return luchshee

def perezapuski(chisla, raz, ocenok):
    luchshee = sum(chisla)
    for r in range(raz):
        luchshee = min(luchshee, poisk(chisla, 0.001, 1, ocenok // raz))
    return luchshee

random.seed(4)
chisla = []
for i in range(16):
    chisla.append(random.randint(1, 100))
print(chisla, tochno(chisla))
itogi = [[], [], []]
for zerno in range(1, 21):
    random.seed(zerno)
    itogi[0].append(poisk(chisla, 0.001, 1, 600))
    random.seed(zerno)
    itogi[1].append(perezapuski(chisla, 10, 600))
    random.seed(zerno)
    itogi[2].append(poisk(chisla, 30, 0.99, 600))
for i in range(3):
    print(["спуск", "перезапуски", "отжиг"][i], itogi[i].count(0),
          sum(itogi[i]) / 20, max(itogi[i]))

[31, 39, 14, 93, 51, 62, 20, 12, 9, 3, 52, 71, 38, 98, 8, 29] 0
спуск 2 4.9 18
перезапуски 17 0.3 2
отжиг 12 1.2 4

Столбцы: метод, сколько раз из 20 найден точный оптимум 0, средняя разница, худшая разница. Один спуск нашёл оптимум дважды, в среднем промахивался на 4,9 и однажды на 18. Перезапуски - 17 из 20, худший промах 2. Отжиг посередине: 12 из 20, худший промах 4.

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

Разбор: поиск с запретами - срок решает

tabu на каждом шаге проверяет все шестнадцать переносов (16 оценок), так что 37 шагов - почти тот же бюджет 600. Срок запрета 0 означает «запретов нет», срок 4 - перенесённое число нельзя возвращать четыре шага. Восемь зёрен, лучший результат каждого прогона; последняя строка - след одного прогона.

import random

def tabu(chisla, srok, shagov):
    n = len(chisla)
    storona = []
    raznica = 0
    for x in chisla:
        storona.append(random.choice([-1, 1]))
        raznica = raznica + storona[-1] * x
    zapret = [-1] * n
    luchshee = abs(raznica)
    sled = []
    for k in range(shagov):
        hod = -1
        luchshaya = 0
        for i in range(n):
            nova = raznica - 2 * storona[i] * chisla[i]
            if zapret[i] < k or abs(nova) < luchshee:
                if hod == -1 or abs(nova) < abs(luchshaya):
                    hod = i
                    luchshaya = nova
        raznica = luchshaya
        storona[hod] = -storona[hod]
        zapret[hod] = k + srok
        luchshee = min(luchshee, abs(raznica))
        sled.append(abs(raznica))
    return [luchshee, sled]

random.seed(4)
chisla = []
for i in range(16):
    chisla.append(random.randint(1, 100))
for srok in [0, 4]:
    itogi = []
    for zerno in [1, 2, 3, 4, 5, 6, 7, 8]:
        random.seed(zerno)
        itogi.append(tabu(chisla, srok, 37)[0])
    print(srok, itogi)
random.seed(2)
print(tabu(chisla, 4, 37)[1][:14])

0 [2, 2, 4, 2, 2, 0, 2, 4]
4 [2, 0, 0, 0, 2, 0, 0, 0]
[58, 18, 2, 8, 26, 50, 26, 2, 4, 12, 6, 0, 24, 16]

Без запретов оптимум найден один раз из восьми: поиск доходит до разницы 2 и переносит одно и то же число туда-обратно. Со сроком 4 - шесть раз из восьми.

След показывает механику. От 58 поиск спускается до 2 за два шага - это локальный оптимум. Дальше обычный спуск остановился бы, а табу делает лучший разрешённый ход: 8, потом 26, 50 - разница растёт, потому что отменять последние переносы запрещено. Потом поиск снова спускается - 26, 2, - но уже в другом разбиении, и через 4, 12, 6 на двенадцатом шаге находит 0. Шаги вверх - не ошибка, а плата за выход из ямы.

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

Сравнивают при разном бюджете. Новый метод с 10 000 оценок против старого с 1000 - выигрыш покупается бюджетом, а не идеей. Бюджет выравнивают в оценках цели: секунды на разных машинах и разных языках несравнимы.

Показывают лучший прогон. Лучший из двадцати прогонов отжига - 0, лучший из двадцати спусков - тоже 0. По лучшему случаю методы неразличимы, по разбросу - средний промах 4,9 против 0,3.

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

Нет эталона. «Наш метод на 3% лучше» ничего не значит, если оба на 40% хуже оптимума. Где точного ответа нет, эталоном служит нижняя граница - вроде остовного дерева у коммивояжёра.

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

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

Теперь сам

1. Спуск из случайного старта находит оптимум с вероятностью 0,1. Сколько перезапусков нужно, чтобы найти его с вероятностью хотя бы 0,9?
2. Почему поиск с запретами со сроком 0 качается между двумя решениями?
3. Метод А на десяти зёрнах дал лучший результат 100, метод Б - 102. Можно ли сказать, что А лучше?