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

Алгоритмы глобальной оптимизации

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

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

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

Классический алгоритм имитации отжига:

1. Запустить процесс из начальной точки w при заданной начальной температуре .

2. Пока T>0 повторить L раз следующие действия:

2.1. Выбрать новое решение из окрестности .

2.2. Рассчитать значение целевой функции .

2.3. Если , принять = , в противном случае принять, что = с вероятностью путем генерации случайного числа R из интервала (0,1) с последующим его сравнением со значением ; если >R, принять новое решение = ; в противном случае проигнорировать новое решение.

3. Уменьшить температуру (T← rT) с использованием коэффициента уменьшения r, выбираемого из интервала (0,1), и вернуться к п.2.

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