Алгоритм Simulated Annealing 🔥

Недавно участвовал в соревновании на Kaggle, где нужно было подобрать перестановку столбцов матрицы X (50x100), которая минимизировала бы функцию:

Прошу прощения за фото, но код тут форматировать не удаётся.

Так как вариантов перестановки непомерно много, то простым перебором данную задачу было не решить. Приходилось использовать генетический алгоритм, beam search и прочее. На удивление себя очень хорошо показал алгоритм Simulated Annealing, механизм которого я бы и хотел разобрать.

Принцип работы довольно прост:

1. Генерируем начальное решение,
2. Случайно делаем шаг к соседнему решению.
   Если новое решение лучше, то мы его принимаем и дальнейшие шаги будем делать от него.
   Иначе с вероятностью exp(-Δ/T) принимаем даже более слабое решение.
   
   Здесь:
   Δ — насколько выросла целевая функция (разница между новым и старым решениями),
   T — температура (гиперпараметр).

Роль температуры:

• Чем выше T, тем выше вероятность принять решение похуже.
• Обычно температуру постепенно уменьшают («охлаждают систему»).
• Но в задачах с глубокими локальными минимумами полезно либо снижать T очень медленно, либо вообще оставлять её фиксированной.

Как это работает на практике?

Пример работы

Представим схему:

• Сначала мы находим некоторое начальное решение.
• Далее быстро скатываемся в локальный минимум (точка a).
• С некоторой вероятностью можем принять более слабое решение (b) и «выпрыгнуть» из локального минимума.
• Благодаря этому открывается возможность найти более качественное глобальное решение (c)

Пример влияния температуры и Δ на вероятность.

Δ = 5 (Найденное решение оказалось хуже на 5 единиц)
T = 10 => Вероятность принять это решение ≈0.61
T = 1 => Вероятность принять это решение ≈0.007

Если остались вопросы, то хорошая статья на хабре тут.
Или можете заглянуть ко мне в Telegram.
Всем спасибо и удачи :)