Алгоритм Simulated Annealing 🔥

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

def func4opt(I): global X assert len(set(I)) == 100 z = X[:, I[0]] * len(I) for i in I[1:]: z += np.sin(10 * X[:, i] + z) return np.sum(z ** 2)

Так как вариантов перестановки непомерно много, то простым перебором данную задачу было не решить. Приходилось использовать генетический алгоритм, 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.

Алгоритм Simulated Annealing 🔥

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

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

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

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