Описание тега simulated-annealing

Имитация отжига (SA) - это обобщенная вероятностная метаэвристика для задачи глобальной оптимизации поиска хорошего приближения к глобальному оптимуму данной функции в большом пространстве поиска.

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

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

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

Метод был независимо описан Скоттом Киркпатриком, К. Даниэлем Гелаттом и Марио П. Векки в 1983 году и Владо Эрнё в 1985 году. Метод представляет собой адаптацию алгоритма Метрополиса-Гастингса, метода Монте-Карло для генерации образцов состояний термодинамическая система, изобретенная М. Н. Розенблютом и опубликованная в статье Н. Метрополиса и др. в 1953 г.

Источник: Википедия (имитация отжига).