Лекция №1. Метод отжига

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


При этом нам необходимо найти не только значение минимума, но сам элемент на котором этот минимум достигается.

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

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

К минусам метода отжига можно отнести то, что этот алгоритм не всегда сходится к решению, а также может приводить к поиску только локальных минимумов. Впрочем, эти недостатки часто являются следствием "плохих" свойств оптимизируемых функций. Но тем не менее метод отжига - это действенное средство для решения многих сложных оптимизационных задач.

Мы рассмотрим применение метода отжига для решения известной проблемы о расстановки N ферзей на шахматной доске NxN таким образом, чтобы ни один ферзь не угрожал другим. В классической постановке N=8 и эту задачу решают на реальной шахматной доске.

Посмотрите наше видео, на котором показано, как работает этот алгоритм в данной задаче:

Опишем схему применения метода отжига:

  1. Положить k = 0, Tk = 100
  2. Выбрать случайный элемент s(0) из области допустимых решений (из множества S).
  3. Снизить температуру по правилу:


  4. Построить новый элемент s(k+1) = g(s(k)) по некоторому случайному алгоритму. Обычно предполагается, что этот алгоритм работает так, что каждое последующее приближение должно отличаться не очень сильно.
  5. Вычисляем dh = h(s(k+1)) - h(s(k)).
  6. Если dh < 0, т.е. найденное приближение лучше чем было, то принять s(k+1).
  7. Если dh >= 0, тогда принять решение s(k+1) с вероятностью:


    Если решение не принимается, то положить s(k+1) = s(k).
  8. Положить k = k + 1. Перейти к шагу 3.

В описанном алгоритме мы не указали момент его остановки. Окончание процесса вычислений может быть осуществлено по различным критериям, например, достижения оптимального состояния или снижения температуры ниже заданного уровня.

Рассмотрим программную реализацию метода отжига для решения задачи о размещении ферзей. Полные тексты программ на языке Python Вы можете скачать: AI-Queen.

В этой программе в файле TQueen.py реализован класс TPole, который реализует логику ферзей на шахматной доске. В частности, это класс подсчитывает количество ударов ферзей и реализует случайную функцию для изменения позиции (аналог функции g в алгоритме).

Сам метод отжига реализован в классе TRun:

Copy Source | Copy HTML
  1. def Run(self):
  2.     Pos = self.Pole.Mix()
  3.     ds = self.Pole.Calc(Pos) - self.Pole.CalcSelf()
  4.     if ds <  0:
  5.         self.Pole.Change(Pos)
  6.     else:
  7.         p = np.exp(- ds / self.T)
  8.         if p > rnd.random():
  9.             self.Pole.Change(Pos)
  10.         self.T = self.alpha * self.T
  11.     return self.Pole.CalcSelf()
Видно, что этот довольно простой.

Запустим программу на обычной шахматной доске (N = 8). Приведем график, где показано количество ударов ферзей на каждом шаге:

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

В нашем примере за 90 шагов была найдена оптимальное размещение ферзей:

[5, 2, 0, 7, 4, 1, 3, 6]

Заметим, что в нашей программе нумерация от нуля. Расставим наших ферзей, как нашла программа:



Видим, что, да, решение найдено!

Home | Лекции | Python | Видео | Скачать | Ссылки
Copyright (c) 2017, Roman Shamin
62
6686
31