Визуальный язык ДРАКОН
Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность/Надёжность
Инструменты пользователя
Это старая версия документа.
Симуляция отжига - алгоритм поиска, сочетающий эвристику и случайность. Эвристика указывает перспективное направление поиска. Она помогает избежать необходимости перебирать все варианты. Случайность позволяет не попадать в ловушку локальных максимумов.
В течение работы алгоритма роль случайности постепенно уменьшается. А эвристика, наоборот, становится всё важнее и важнее.
Мера продвижения поиска к результату обозначается числом, которое имеет условное название «температура». Вначале температура максимальна. С каждым шагом алгоритма она снижается. Температура достигает низшей точки при завершении поиска.
Работа алгоритма начинается со случайно выбранного состояния. Для текущего состояния находятся соседние доступные состояния. Из доступных состояний случайным образом выбирается следующее. Близость состояния к цели оценивается эвристической функцией. Если следующее состояние ближе к цели, чем текущее, то оно делается текущим. Если нет, то решение следовать худшему выбору или взять какое-нибудь другое состояние принимается с некоторой вероятностью. Эта вероятность зависит от температуры. Чем температура выше, тем больше вероятность согласиться на менее выгодное направление. Из-за понижения температуры к концу поиска невыгодные состояния исследуются реже.
В начале работы алгоритма происходит более смелое исследование пространства поиска. В конце алгоритм производит тонкую настройку решения. Точность, с которой эвристическая функция делает оценки, очень важна для производительности алгоритма.