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

В течение работы алгоритма роль случайности постепенно уменьшается. А эвристика, наоборот, становится всё важнее и важнее.

Мера продвижения поиска к результату обозначается числом, которое имеет условное название «температура». Вначале температура максимальна. С каждым шагом алгоритма она снижается. Температура достигает низшей точки при завершении поиска.

Алгоритм:

• Работа алгоритма начинается со случайно выбранного состояния.
• Для текущего состояния находятся соседние доступные состояния.
• Из доступных состояний случайным образом выбирается следующее. Близость состояния к цели оценивается эвристической функцией.
• Если следующее состояние ближе к цели, чем текущее, то оно делается текущим.
• Если нет, то решение следовать худшему выбору или взять какое-нибудь другое состояние принимается с некоторой вероятностью. Эта вероятность зависит от температуры. Чем температура выше, тем больше вероятность согласиться на менее выгодное направление.

Из-за понижения температуры к концу поиска невыгодные состояния исследуются реже.

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

Реализация поиска симуляцией отжига на гибридном языке ДРАКОН-Lua:

Скачать исходник в формате DRAKON Editor: anneal.drn Из этого файла можно сгенерировать работающий скрипт на Lua.

Степан Митькин