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

Вокруг Алматы на карте 174 города и села. Подпись каждого можно поставить в один из четырёх углов от точки — справа сверху, слева сверху, справа снизу, слева снизу — или спрятать, если места нет. Вариантов расстановки 5¹⁷⁴, это число из 122 цифр. Перебрать их нельзя, а жадно ставить подписи по одной — значит упереться в тесноту пригородов, где каждой новой подписи мешают уже поставленные. Ниже два способа решать такую задачу. Спуск двигает одну подпись за раз, только если это улучшает карту, и начинает заново, когда улучшать нечего. Отжиг иногда соглашается и на ухудшение. Запустите оба и сравните, сколько подписей каждому пришлось спрятать.

Посмотрите на отжиг в первые секунды: подписи прыгают из угла в угол почти без разбора, наложений много, энергия скачет. Это «горячая» фаза. Потом прыжки становятся реже и осторожнее, и сначала успокаиваются тесные места — Алматы с пригородами, цепочка сёл вдоль гор, — а в конце переставляются только отдельные подписи на краях. Спуск ведёт себя иначе: за долю секунды он находит расстановку, где ни одна подпись не может сдвинуться с выгодой, и застревает в ней. Перезапуск даёт новую такую расстановку, но обычно не лучше прежней. В листинге ниже при одинаковом бюджете в 60 000 проверок спуск с перезапусками прячет 35 и 36 подписей, а отжиг — 28 и 28.

Идея

Спуск застревает в первой же ямке: из неё нет хода вниз. Отжиг разрешает ходы вверх, но с вероятностью, которая падает с высотой подъёма: ухудшение на Δ принимается с вероятностью e^−Δ/T. Число T называют температурой. Пока она высокая, поиск свободно переходит из долины в долину; потом её понемногу снижают, и поиск всё реже соглашается подниматься, пока не превратится в обычный спуск — но уже в глубокой долине, куда его привели горячие шаги.

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

Как это работает

Нужно четыре вещи. Состояние — текущее решение: здесь это угол каждой из 174 подписей или пометка «спрятана». Энергия — число, которое мы хотим сделать как можно меньше: каждое наложение (на другую подпись, на чужую точку, за край карты) стоит 40, спрятанная подпись — 15, угол — от 0 за правый верхний до 3 за левый нижний: картографы считают правый верхний самым привычным. Ход — маленькое изменение: одна случайная подпись переезжает в другой угол или прячется. И расписание — как температура меняется со временем.

1. Начинаем со случайной расстановки и высокой температуры T₀.
2. Выбираем случайный ход и считаем, на сколько он изменит энергию: Δ = E(новое) − E(текущее).
3. Если Δ ≤ 0, делаем ход. Если Δ > 0, делаем его с вероятностью e^−Δ/T: берём случайное u из [0, 1) и принимаем ход, когда u < e^−Δ/T. Это правило Метрополиса.
4. Понемногу снижаем температуру и повторяем, пока не кончится бюджет шагов. Запоминаем лучшее состояние за всё время: отжиг может уйти от него и не вернуться.

Температура измеряется в тех же единицах, что энергия, и смысл у неё простой: это подъём, на который поиск соглашается с вероятностью 1/e ≈ 0,37. На карте отжиг начинает с T = 20. Ход, который добавляет одно наложение (+40), принимается тогда с вероятностью e⁻² ≈ 0,14, а ход, прячущий подпись (+15), — почти в половине случаев. К концу температура падает до 0,5: наложение теперь принимается с вероятностью e⁻⁸⁰, то есть никогда, и лишь смена угла (+1) ещё проходит в каждом седьмом случае. Между ними температура убывает геометрически: на шаге k из K

Такое расписание остывания предложили ещё Киркпатрик и соавторы: в их опыте с разбиением схемы температура после каждой ступени умножалась на 0,9. Как выбрать T₀ и T₁, видно по счётчику «принято ходов в гору» в сцене: в начале должна приниматься заметная доля ухудшений — треть или половина, — а в конце почти ни одного. Переключите сцену на «свою температуру» и поищите сами: при T = 100 карта кипит, при 10 подписи ещё перебегают через соседей, при 2 наложения уже не появляются, но подписи по-прежнему перескакивают между свободными углами.

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

Второй опыт: раскладка клавиатуры

Тот же алгоритм на другой задаче — и, как увидим, с другим исходом. В раскладке ЙЦУКЕН 33 буквы; ё стоит отдельно, далеко слева, и мы считаем её за е — остаются 32 буквы на 32 клавишах. Насколько она удобна для русского текста, зависит от того, что считать удобством. Возьмём простую модель в духе оптимизатора раскладок Carpalx. У каждой клавиши своя цена нажатия: 10 под указательным и средним пальцами в домашнем ряду, дороже у безымянного и мизинца, в верхнем и нижнем рядах. Если две соседние буквы слова набираются одним пальцем на разных клавишах, добавим 20 (через ряд — 30): палец должен перескочить. Если одной рукой — 3: при чередовании рук печатать легче. Цену раскладки посчитаем на всём тексте «Войны и мира»: 2,24 миллиона букв и 1,8 миллиона пар соседних букв внутри слов.

ЙЦУКЕН стоит в этой модели 18,80 на букву. Отжиг из случайной раскладки приходит к 14,08–14,12: на четверть дешевле. Домашний ряд набирает уже не 43 % букв, а 66 %; один палец дважды подряд — не 19,9 % пар, а 1,1 %; руки чередуются в 78 % пар вместо 56. Главная беда ЙЦУКЕН в этой модели — правый указательный палец: на нём о, т, н, р, г и ь, и он сам с собой набирает «то» — самое частое сочетание букв в романе, — а ещё «го», «но», «от», «он», «ро».

Присмотритесь к раскладке, которую нашёл листинг ниже: все гласные — а, е, и, о, у, ы, э, ю, я — оказались под левой рукой. В сцене они иногда собираются под правой — модели почти всё равно, какой руке что достанется, — но в наших прогонах всегда под одной. Отжиг ничего не знает о гласных; он просто «заметил», что гласные и согласные в словах чередуются, и развёл их по разным рукам. В 1936 году Август Дворак и Уильям Дили запатентовали английскую раскладку по тому же принципу: гласные в домашнем ряду левой руки, ради чередования рук. И ещё одно видно, если смотреть на сцену с самого начала. Сначала, при высокой температуре, решается грубое — какие частые буквы уходят в домашний ряд, какие руки им достаются, — а редкие ъ, щ, ж бродят по клавиатуре до самого конца. Киркпатрик и соавторы описали это ещё в первой статье: крупные черты решения появляются при высоких температурах, детали — при низких; они называли это разновидностью «разделяй и властвуй», которая подстраивается сама.

Почему медленное остывание работает

Отжиг кажется ремеслом: начни горячо, остужай медленно. Но за ним стоит точная математика, и начинается она с вопроса: где проводит время поиск, если температуру не менять вовсе?

Из любого ли начала блуждание придёт к π? Да, если из каждого состояния можно добраться до каждого (у подписей — переставляя их по одной, у клавиатуры — обменами) и блуждание не ходит строго по кругу (оно иногда стоит на месте: в глобальном минимуме ход вверх отклоняется с положительной вероятностью). Это теорема о сходимости цепей Маркова; в «Царице наук» она доказана для матриц переходов со всеми положительными элементами, а к нашим цепям применяется через степень матрицы: за несколько шагов из любого состояния можно попасть в любое.

Выходит, при очень низкой температуре равновесное блуждание почти всё время проводит в лучшем состоянии. Подвох — в слове «равновесное». Возьмём кусок клавиатуры, который можно перебрать целиком: шесть самых частых букв — о, е, а, и, н, т — меняются местами на своих же шести клавишах, а остальные 26 стоят как в ЙЦУКЕН. Раскладок всего 6! = 720, и для каждой распределение Больцмана можно посчитать точно.

У этих 720 раскладок два локальных минимума: лучшая (18,049 на букву) и ловушка (18,334), из которой никакой обмен не ведёт вниз. Чтобы выбраться из ловушки к лучшей, нужно сначала подняться до перевала на 18,788: глубина ловушки — 0,454 на букву. Блуждание стартует в ловушке. При T = 0,3 и 0,1 за 40 000 шагов оно приходит к Больцману: в лучшей раскладке 2,8 % и 19,3 % времени при точных 3,0 % и 19,9 %. При T = 0,05 Больцман отдаёт лучшей раскладке 27 % времени, а ловушке — 0,1 %, но блуждание за те же 40 000 шагов ни разу не дошло до лучшей и половину времени просидело в ловушке.

Почему — видно, если измерить, сколько шагов уходит на побег из ловушки. При T = 0,2 — в среднем 209 шагов, при 0,1 — 764, при 0,07 — 6196. Время растёт примерно как e^d/T, где d — глубина ловушки: этот множитель равен 10, 93 и 651. Физики знают такую зависимость по скорости химических реакций — это закон Аррениуса. Холодное равновесие хорошо, но ждать его приходится экспоненциально долго. Отжиг обходит это так: начинает горячо, когда равновесие наступает быстро, и остывает настолько медленно, чтобы блуждание успевало следовать за ним.

Насколько медленно? Точный ответ нашёл Брюс Хайек в 1988 году для логарифмического расписания T_k = c / ln(k + 1): вероятность оказаться в глобальном минимуме стремится к единице тогда и только тогда, когда c не меньше глубины самой глубокой ловушки — локального минимума, который не глобальный. Доказательство длинное, и мы его не приводим; достаточное условие такого вида четырьмя годами раньше доказали Стюарт и Дональд Геманы. Но логарифм растёт так медленно, что гарантия почти бесполезна: чтобы вдвое понизить температуру, число шагов нужно возвести в квадрат. Замер ниже — 150 отжигов тех же 720 раскладок из случайного начала для каждого числа шагов: геометрическое остывание от 1 до 0,001 против гарантированного c / ln(k + 2) с c = 0,454.

За 10⁵ шагов геометрическое остывание заканчивает в долине лучшей раскладки в 97,3 % запусков, а гарантированное логарифмическое — в 81,3 %, и в ловушке у него остаётся 13,3 % запусков против 2,7 % у быстрого. Логарифмическое расписание к этому времени остыло лишь до 0,039: теорема обещает успех, но в бесконечности. На практике берут геометрическое или ступенчатое остывание и проверяют его опытом, как здесь.

Код

Главное в программе — четыре функции: энергия расстановки, изменение энергии от хода, отжиг и спуск с перезапусками для сравнения. Списки столкновений строятся один раз: подписи сортируются по x, и пары проверяются, только пока соседи по x ближе двух самых длинных подписей. Случайные числа — общий генератор splitmix64, чтобы Python и Go печатали одно и то же. Данные — те же 174 места, что в сцене.

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

Клавиатура устроена так же, только ход — обмен двух букв клавишами. Изменение цены от обмена считается за 32 операции, а не за 32²: меняются только пары, где участвует одна из двух букв, и пары «a, потом b» и «b, потом a» можно сложить заранее, потому что надбавка за них одинакова.

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

Сколько это стоит

Отжиг сам по себе не имеет «сложности» в обычном смысле: число шагов S выбираете вы, и время работы — S, умноженное на цену одного шага. Цена шага — это пересчёт Δ, и от его устройства зависит всё.

Сколько шагов брать? Ориентир — несколько сотен попыток хода на каждый элемент решения: на карте 60 000 шагов — это примерно 340 на подпись, и уже этого хватает, чтобы обогнать перезапуски. Больше шагов дают лучше, но всё медленнее: в замере ниже от 10⁴ до 10⁵ шагов отжиг на карте выигрывает шесть-семь подписей, а от 10⁵ до 10⁶ — полподписи в медиане. Запустить несколько независимых отжигов и взять лучший — обычная практика: прогоны не зависят друг от друга, и их легко раздать по ядрам.

Честное сравнение: отжиг против перезапусков

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

Исходы противоположные. На карте отжиг выигрывает при любом бюджете, и разрыв растёт: при миллионе проверок перезапуски прячут 33 подписи, отжиг — 25. На клавиатуре перезапуски почти при любом бюджете не хуже отжига (при 10⁵ проверок — вровень), а при 300 тысячах заметно лучше: в медиане их раскладка на 0,11 % дороже лучшей найденной, у отжига — на 0,25 %.

Разница в устройстве задач. Клавиатура маленькая: 32 буквы, один спуск от случайной раскладки стоит в среднем 2500 проверок, и 300 тысяч проверок — это больше сотни независимых спусков. Ловушек в ней немного и они неглубокие (в куске из 720 раскладок ловушка одна), так что лучший из сотен спусков почти наверняка попадает в лучшую долину. На карте 174 подписи, и выбор каждой зависит от соседей, а те — от своих соседей. Таких расстановок, где никакой одиночный ход не помогает, необозримо много, и почти все они примерно одинаково плохи. Один спуск стоит около трёх тысяч проверок, и при бюджете в 3000 перезапуски прячут 38,5 подписи, а при миллионе — сотни спусков — лишь 33: лучший из сотен ненамного лучше первого попавшегося. Отжиг же строит решение сверху вниз — сначала разводит тесные скопления, потом шлифует края — и до этих «типичных» ям не опускается. Похожую картину в 1989 году получили Дэвид Джонсон и соавторы на разбиении графов пополам: на больших разреженных случайных графах отжиг обгонял алгоритм Кернигана — Лина даже с поправкой на своё долгое время работы, а на графах с геометрической структурой проигрывал.

Несколько привычек, без которых отжиг редко работает хорошо. Делайте ходы маленькими и обратимыми и считайте Δ за время, пропорциональное размеру хода, а не задачи. Начальную температуру подбирайте по доле принятых ухудшений — в начале не меньше трети, — а конечную так, чтобы ухудшений почти не принималось. Храните лучшее решение отдельно. И следите, чтобы у разных состояний было одинаковое число соседей, а ход выбирался равновероятно: иначе теорема о распределении Больцмана перестаёт работать, и блуждание предпочитает состояния, где соседей больше. Как это исправить, показывает первая задача ниже.

Где работает

• Микросхемы. Первые применения отжига Киркпатрик и соавторы нашли в проектировании вычислительных машин: разбить схему на блоки так, чтобы между ними шло поменьше проводов, расставить элементы на кристалле, проложить провода. В 1985 году Карл Сечен и Альберто Сангиованни-Винчентелли описали пакет TimberWolf, где отжигом решались и расстановка, и разводка; на промышленных схемах он экономил от 15 до 62 % площади по сравнению с тогдашними программами. Его ядро потом вошло в набор тестов производительности процессоров SPEC CPU2000 под именем twolf.
• Подписи на картах. Расставить подписи без наложений — NP-трудная задача уже для четырёх углов: это доказали независимо три группы (Като и Имаи в 1988 году, Маркс и Шибер, Форман и Вагнер в 1991-м). Для двух мест на подпись задача сводится к 2-выполнимости и решается точно, через компоненты сильной связности — так устроена задача о подписях сёл. В первом сравнительном исследовании алгоритмов для этой задачи Джон Кристенсен, Джо Маркс и Стюарт Шибер (1995) советовали отжиг, когда важнее всего качество расстановки.
• Раскладки клавиатуры. Оптимизатор Carpalx Мартина Кшивинского ищет раскладку с наименьшим усилием по модели, похожей на нашу, — отжигом; на его подходе построены и другие оптимизаторы раскладок.
• Всё, что похоже на эти задачи: расписания, раскрой, размещение, где решение собирается из многих зависимых выборов и есть быстрый пересчёт цены после маленького изменения. Отжиг пишется за час и часто служит первым приближением, с которым потом сравнивают специальные методы.

История

Правило Метрополиса появилось в 1953 году, в статье «Equation of State Calculations by Fast Computing Machines» пяти авторов: Николаса Метрополиса, Арианны и Маршалла Розенблютов, Огасты и Эдварда Теллеров. Они хотели посчитать свойства вещества при заданной температуре и придумали, как получать типичные расположения частиц, не перебирая все: сдвинуть случайную частицу и принять сдвиг, если энергия уменьшилась, а если выросла на Δ — с вероятностью e^−Δ/kT. Блуждание по состояниям само собой распределялось по Больцману, и средние по нему давали нужные величины. Кто из пятерых что придумал, спорят до сих пор. В 1970 году Уилфред Хастингс обобщил правило на несимметричные ходы.

Тридцать лет спустя Скотт Киркпатрик, Чарльз Гелатт и Марио Векки заметили, что то же блуждание можно не держать при одной температуре, а остужать, и тогда оно ищет минимум энергии — то есть решает задачу оптимизации. Их статья «Optimization by Simulated Annealing» вышла в журнале Science 13 мая 1983 года; в ней были разбиение схем, расстановка элементов, разводка проводов и задача коммивояжёра на несколько тысяч городов. Независимо от них к той же идее пришёл физик Владимир Черни: его отчёт ходил по рукам с 1982 года, а статья о коммивояжёре вышла в 1985-м. В 1984 году Стюарт и Дональд Геманы применили отжиг к восстановлению изображений и доказали сходимость при логарифмическом остывании, а в 1988 году Хайек нашёл точное условие для логарифмического расписания.

Отжиг на задаче коммивояжёра, против 2-opt, жадности и эволюции, разобран в главе курса «Трудные задачи»; там же задача о рассадке гостей, где отжиг дописывают к заготовке спуска. Сам коммивояжёр со своими приёмами — в статье о задаче коммивояжёра, а соседний метод, который держит целую популяцию решений, — генетический алгоритм.

Задачи

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