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

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

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

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

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

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

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

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

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

1. 
   Если решение не принимается, то положить s(k+1) = s(k).
   
2. 
   Положить 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]