Алгоритм имитации отжига

Метод имитации отжига отражает поведение расплавленного материала при отвердевании с применением процедуры отжига (управляемого охлаждения) при температуре, последовательно понижаемой до нуля.

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

(1.1)

где P (Е) - вероятность нахождения системы в состоянии с уровнем энергии Е, k - постоянная Больцмана; T - температура по Кельвину.

При высоких температурах вероятность любого энергетического состояния близка к 1, а при уменьшении T вероятность высоких энергий падает.

Алгоритм глобальной оптимизации с помощью имитации отжига представляет собой аналог физического процесса. Классический алгоритм имитации отжига можно описать следующим образом:

1. Искусственная температура получает максимальное значение T=T _max. Модельное время обнуляется: t = 0.

2. Выбирается начальная точка (аргумент функции) x = x ₀.

3. Рассчитывается целевая функция F (x).

4. Аргумент получает приращение

x’ = x + D x.

5. Рассчитывается целевая функция F (x’).

6. Рассчитывается изменение целевой функции

D F = F (x’) - F (x).

7. Если D F < 0, то x=x’ (значение аргумента сохраняется).

8. Если D F > 0, то вероятность сохранения D F (и, соответственно - x’) вычисляется по формуле, подобной (1.1):

где T – искусственная температура; k - константа, выбираемая из эвристических соображений.

Затем P (D F) сравнивается со случайным числом n Î [0,1].

Если P (D F) > n, то x=x’, иначе x не изменяется.

9. Искусственная температура уменьшается, модельное время увеличивается: t=t+ D t, происходит возврат к п.п. 4, и так до тех пор, пока T не уменьшится до заданного порогового значения.

Таким образом, пока искусственная температура T большая, алгоритм отжига может делать большие шаги даже в направлениях, увеличивающих значение минимизируемой функции. За счет этой особенности оказывается возможным попасть в окрестность глобального минимума. При этом, конечно, важно правильно определить начальное значение T _max и задать закон ее изменения температуры. Считается, что эта величина должна быть обратно пропорциональна логарифму t:

Эта формула показывает, что искусственная температура должна меняться медленно.