Введение

Алгоритм имитации отжига (или алгоритм Метрополиса) - это один из методов численной оптимизации, в рамках которого мы ищем минимум или максимум какой-то функции. Я буду описывать метод на примере минимума.

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

Основная идея алгоритма

Идея метода пришла из отжига металлов - процесса, при котором металл сначала нагревают, а потом постепенно охлаждают.

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

Примерная реализация алгоритма на Python:

s = s0
k = 0
while k <= k_max:
    T = temperature(k / k_max)
    s_new = neighbour(s)
    e_old = E(s)
    e_new = E(s_new)
    if P(E_old, e_new, T) >= random(0, 1):
        s = s_new
    k += 1

return s

Параметры алгоритма:

  • E - функция, минимум которой мы ищем.
  • s - значение, которое мы ищем (при котором функция E имеет минимальное значение).
  • s0 - значение, с которого мы начинаем искать минимум (обычно какое-то случайное).
  • k_max - общее количество итераций, в рамках которых повторяем основной шаг алгоритма.
  • T - значение температуры.
  • temperature - функция, изменяющая температуру. Значение температуры должно постепенно снижаться.
  • neighbour - функция, выбирающая следующее значение s.
  • P - функция, определяющая вероятность перехода из старого состояния в новое. Эта вероятность должна снижаться при снижении температуры.

Метод регулируется выбором количества итерации k_max и функций P, temperature и neighbour.

Для функции перехода P обычно используют одну из следующих:

  • 1 / (1 + math.exp((e_new - e_old) / T))
  • math.exp(-1 * (e_new - e_old) / T)

Больцмановский отжиг:

T(k) = T0 / ln(1 + k)

Больцмановская схема изначально использовалась Метрополисом и для неё доказано, что при большом начальном T и большом количестве шагов она гарантирует нахождение глобального минимума.

Отжиг Коши (быстрый отжиг):

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

T(k) = T0 / k

Алгоритм имитации отжига в библиотеке SciPy

В библиотеке SciPy этот алгоритм реализован методом scipy.optimize.anneal, но в версии 0.14 этот метод был объявлен устаревшим с рекомендацией использовать вместо него scipy.optimize.basinhopping.

Смотри также