Искусственный интеллект. Алгоритм имитации отжига

Алгоритм имитации отжига (Simulated annealing) — это общий алгоритмический метод решения задачи глобальной оптимизации, особенно дискретной и комбинаторной оптимизации. Один из примеров методов Монте-Карло.

Алгоритм метода показан на следующем рисунке:


График этой функции показан на следующем рисунке:


Сначала создается начальное решение. Для большинства задач, это может быть случайным образом выбранное решение. Затем созданное решение оценивается - в результате, получаем число, выражающее оценку данного решения. Также проставляем температуру в начальное значение. В ходе поиска оптимального решения мы будем все время уменьшать температуру. Есть разные способы уменьшения температуры: экспоненциальный (T[i+1] = k*T[i], k<1), линейный (T[i+1] = T[i] - dT) и др. Эти способы называются расписаниями охлаждения (cooling schedules).

Затем решение случайным образом модифицируется. Для этого создается еще одна копия текущего решения (current solution), которое называется рабочим решением (working solution). Эта копия и модифицируется случайным образом.

Теперь мы имеем два экземпляра решения - текущее и рабочее. Производится оценка рабочего решения. В результате, получаем еще одно число. Оценка рабочего решения сравнивается с оценкой текущего решения. Если оценка рабочего решения лучше, то мы копируем рабочее решение в текущее решения, затем уменьшаем температуру и переходит к следующей итерации цикла.

Если же оценка рабочего решения хуже, то мы обращаемся к критерию приемки данного решения (acceptance criteria). Вероятность того, что мы примем данное (рабочее) решение зависит от разницы в оценках между рабочим и текущим решениями, а также от текущей температуры. Данная вероятность выражается следующей формулой:


График этой функции показан на следующем рисунке:


Чем выше температура, тем больше вероятность принятия рабочего решения. И наоборот - чем меньше температура, тем меньше вероятность принятия текущего рабочего решения. Это связано с попыткой "скопировать" процессы, происходящие в металле при отжиге: при высоких температурах кристаллическая решетка металла меняется легче, чем при низких. Так и здесь: при высоких температурах текущее решение легче меняется на рабочее.

Приведем псевдокод алгоритма:

s ← s0; e ← E(s)                                // Initial state, energy.
sbest ← s; ebest ← e                            // Initial "best" solution
k ← 0                                           // Energy evaluation count.
while k < kmax and e < emax                     // While time left & not good enough:
  snew ← neighbour(s)                           // Pick some neighbour.
  enew ← E(snew)                                // Compute its energy.
  if P(e, enew, temp(k/kmax)) > random() then   // Should we move to it?
    s ← snew; e ← enew                          // Yes, change state.
  if enew < ebest then                          // Is this a new best?
    sbest ← snew; ebest ← enew                  // Save 'new neighbour' to 'best found'.
  k ← k + 1                                     // One more evaluation done
return sbest                                    // Return the best solution found.