Реферат: Алгоритм имитации отжига

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

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

(1.1)

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

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

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

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

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

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

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

x’ = x + Dx.

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

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

DF = F(x’) — F(x).

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

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

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

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

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

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

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

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