Визуальный язык ДРАКОН

Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность/Надёжность

Инструменты пользователя

Инструменты сайта


algoritmy:annealing

Поиск симуляцией отжига

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

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

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

Алгоритм:

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

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

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

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

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

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

algoritmy/annealing.txt · Последние изменения: 2012/08/30 22:04 — Степан Митькин