Публикация Школы траблшутеров

Имитация отжига: как выбраться из тупика мелких улучшений

Время чтения: 6 мин 30 сек
19 ноября 2026 Просмотров: 30

Двадцать объектов бригада «Кедра» объезжала за 66 километров, и ни один разворот маршрута уже не помогал. Основатель «Школы траблшутеров», экс-директор Альфа-Банка по процессам, Олег Брагинский рисует имитацию отжига – способ на время ухудшить решение, чтобы найти лучшее, – в трёх нотациях и объясняет, когда встряска приносит пользу.

Имитация отжига: как выбраться из тупика мелких улучшений

Рис. 1. Схема по ГОСТ 19.701: иногда принимаем более длинный путь

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

Короткий ответ: из тупика выходят, разрешая иногда ухудшение – сначала часто, потом всё реже, пока решение не «остынет» в лучшей найденной точке.

Рисовать такой поиск руководителю удобнее всего диаграммой состояний: видно, как смелые шаги сменяются осторожными.

Как устроен отжиг?

Имитация отжига – способ искать решение случайными шагами: улучшение принимают всегда, ухудшение – с шансом, который падает вместе с «температурой». По ГОСТ 19.701 – цикл «Пока температура выше 0,01 км» с двумя развилками.

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

К задачам выбора метод применили Киркпатрик, Гелатт и Векки из IBM в 1983-м, а двумя годами позже, независимо от них, – Черни из Братиславы на задаче коммивояжёра.

Чем опасна бесконечная встряска?

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

Встряска без остывания – просто беспорядок. Если в модели «Кедра» не снижать температуру, маршрут к концу расчёта в среднем длиннее 85 километров – хуже даже первого черновика.

Как это выглядит на деле?

Сервисная компания «Кедр» взяла на обслуживание ещё двенадцать объектов, и маршрут бригады вырос до двадцати точек. Ближайший сосед даёт 76 километров, развороты сокращают путь до 66, и дальше ни один разворот не помогает.

image html

Рис. 2. Пример: на жаре путь удлиняется, при остывании садится ниже тупика

Отжиг начинает с температуры 2 км и каждые сто попыток остужает на 5%. Сначала маршрут вырастает почти до 80 км, на 3’600-й попытке находит 62, а полный расчёт подтверждает: короче не бывает. Четыре километра в день – около тысячи за год.

Почему случайность помогает?

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

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

Когда нужен решительный шаг?

Кредитный процесс начал сползать к худшим значениям. Запустили шринк всех баз посреди рабочего дня, клиентам стали одобрять 100% кредита, начался ажиотаж. Перезапуск систем, годами копивших мусор, встряхнул инфраструктуру, и ещё три года замедлений не было.

Такой ход оправдан, если дела идут всё хуже, а мелкие доводки бессильны. Рискованные варианты пробуют на модели, а живую среду обновляют по плану, с возможностью отката.

Когда обойтись без отжига?

Для восьми объектов из предыдущего примера хватило двух разворотов.

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

В следующей статье сборника – генетический алгоритм: как скрещивать удачные решения, а не доводить одно-единственное.

Сколько стоит расчёт?

Модель: один прогон отжига для двадцати объектов – около 10’400 попыток и сотая доля секунды. Лучший маршрут находится в 54 прогонах из ста, поэтому считают пять раз и берут лучший ответ – промах в двух случаях из ста.

Вдвое более быстрое остывание экономит время, но успех падает до 29 из ста. Перезапуски разворотов с произвольных путей добираются до 62 км лишь трижды на сотню.

Вручную, по 10 с на каждую пробу, ушло бы больше суток.

Какими нотациями рисовать отжиг?

ГОСТ 19.701 показывает обе развилки и цикл остывания, его ценят разработчики, тестировщики и аудиторы расчётов.

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

image html

Рис. 3. Тот же отжиг в виде строгой вертикальной схемы

Диаграмму состояний любят руководители и аналитики: три фазы – горячо, тепло, холодно – и переходы видны сразу.

Стрелка «запустить снова» напомнит: один прогон – не приговор.

image html

Рис. 4. Три фазы поиска и условия перехода между ними

Какая нотация лучше?

Лучшая нотация для имитации отжига – диаграмма состояний: 21 балл против 20 у языка ДРАКОН и 16 у ГОСТ. Руководитель за минуту видит главное: смелость поиска падает вместе с температурой. Вес вопроса о руководителе удвоен: сборник написан для него.

image html

Рис. 5. Оценка трёх нотаций: 16, 21 и 20 баллов

ДРАКОН отстал на балл и пригодится разработчикам, когда схему переводят в программу, а ГОСТ – тем, кто проверяет расчёт построчно.

Что сделать руководителю?

Хватит четырёх шагов:

  1. Убедитесь, что мелкие улучшения исчерпаны: последние доводки почти ничего не дают, а результат всё ещё хуже цели.
  2. Разрешите ухудшения только на модели и заранее задайте план остывания: с какой температуры начать и как быстро снижать.
  3. Запустите расчёт несколько раз с разными случайными числами и сравните лучшие ответы: совпадение – хороший знак.
  4. Встряску живой системы планируйте как проект: срок, план отката и люди, которые ответят встревоженным клиентам.

Что запомнить?

  • мелкие доводки упираются в потолок
  • шаг назад открывает дорогу к лучшему решению
  • встряска без остывания – просто хаос
  • несколько запусков надёжнее одного
  • имитацию отжига лучше всего рисовать диаграммой состояний.