Алгоритмы имитации отжига
Метод имитации отжига основан на идее, заимствованной из статистической механики. Он отражает поведение расплавленного материала при отвердевании с применением процедуры отжига (управляемого охлаждения) при температуре, последовательно понижаемой до нуля.
В процессе медленного управляемого охлаждения, называемого отжигом, кристаллизация расплава сопровождается глобальным уменьшением его энергии, однако допускаются ситуации, в которых она может на какое-то время возрастать (в частности, при подогреве расплава для предотвращения слишком быстрого его остывания). Благодаря допустимости кратковременного повышения энергетического уровня, возможен выход из ловушек локальных минимумов энергии, которые возникают при реализации процесса. Только понижение температуры до абсолютного нуля делает невозможным какое-либо самостоятельное повышение энергетического уровня расплава.
Метод имитации отжига представляет собой алгоритмический аналог физического процесса управляемого охлаждения. Классический алгоритм имитации отжига можно описать следующим образом:
- Запустить процесс из начальной точки при заданной начальной температуре
.
- Пока , повторить
раз следующие действия:
- выбрать новое решение из окрестности
; - рассчитать изменение целевой функции ;
- если , принять
; в противном случае (при
) принять, что
с вероятностью
путем генерации случайного числа
из интервала
с последующим сравнением его со значением
. Если, принять новое решение
; в противном случае проигнорировать его.
- выбрать новое решение
- Уменьшить температуру с использованием коэффициента
, выбираемого из интервала
, и вернуться к п. 2. - После снижения температуры до нуля провести обучение сети любым из детерминированных методов локальной оптимизации вплоть до достижения минимума целевой функции.
Наибольшего ускорения имитации отжига можно достичь путем замены случайных начальных значений весов
Метод имитации отжига оказывается особенно удачным для полимодальных комбинаторных проблем с очень большим количеством возможных решений, например, для машины Больцмана, в которой каждое состояние системы считается допустимым. При решении наиболее распространенных задач обучения многослойных нейронных сетей наилучшие результаты в общем случае достигаются применением стохастически управляемого метода повторных рестартов совместно с детерминированными алгоритмами локальной оптимизации.
