Имитация отжига

Имитация отжига ( SA ) — вероятностный метод приближения глобального оптимума заданной функции . В частности, это метаэвристика для приближения глобальной оптимизации в большом пространстве поиска для задачи оптимизации . Для большого количества локальных оптимумов SA может найти глобальный оптимум. ^[1] Он часто используется, когда пространство поиска дискретно (например, задача коммивояжера , задача выполнимости булевых функций , предсказание структуры белка и планирование работы в цехе ). Для задач, где нахождение приблизительного глобального оптимума важнее, чем нахождение точного локального оптимума за фиксированный промежуток времени, имитация отжига может быть предпочтительнее точных алгоритмов, таких как градиентный спуск или ветвь и граница .

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

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

Похожие методы были независимо введены в нескольких случаях, включая Pincus (1970), ^[2] Khachaturyan et al (1979, ^[3] 1981 ^[4] ), Kirkpatrick, Gelatt and Vecchi (1983), и Cerny (1985). ^[5] В 1983 году этот подход был использован Kirkpatrick, Gelatt Jr., Vecchi, ^[6] для решения задачи коммивояжера . Они также предложили его нынешнее название — имитация отжига.

Это понятие медленного охлаждения, реализованное в алгоритме имитации отжига, интерпретируется как медленное уменьшение вероятности принятия худших решений по мере исследования пространства решений. Принятие худших решений позволяет проводить более обширный поиск глобального оптимального решения. В целом алгоритмы имитации отжига работают следующим образом. Температура постепенно уменьшается от начального положительного значения до нуля. На каждом временном шаге алгоритм случайным образом выбирает решение, близкое к текущему, измеряет его качество и переходит к нему в соответствии с зависящими от температуры вероятностями выбора лучших или худших решений, которые во время поиска соответственно остаются равными 1 (или положительными) и уменьшаются к нулю.

Моделирование может быть выполнено либо путем решения кинетических уравнений для функций плотности вероятности , ^[7]^[8], либо с использованием метода стохастической выборки. ^[6]^[9] Метод является адаптацией алгоритма Метрополиса–Гастингса , метода Монте-Карло для генерации выборочных состояний термодинамической системы, опубликованного Н. Метрополисом и др. в 1953 году. ^[10]

Обзор

Состояние s некоторых физических систем и минимизируемая функция E ( s ) аналогичны внутренней энергии системы в этом состоянии. Цель состоит в том, чтобы перевести систему из произвольного начального состояния в состояние с минимально возможной энергией.

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

Основная итерация

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

Соседи штата

Оптимизация решения включает оценку соседей состояния задачи, которые являются новыми состояниями, полученными путем консервативного изменения заданного состояния. Например, в задаче коммивояжера каждое состояние обычно определяется как перестановка городов, которые необходимо посетить, а соседи любого состояния являются набором перестановок, полученных путем обмена любых двух из этих городов. Четко определенный способ, которым состояния изменяются для получения соседних состояний, называется «ходом», и различные ходы дают различные наборы соседних состояний. Эти ходы обычно приводят к минимальным изменениям последнего состояния в попытке постепенного улучшения решения путем итеративного улучшения его частей (например, связей городов в задаче коммивояжера). Еще лучше изменить порядок интервала городов на обратный. Это меньший ход, поскольку обмен двух городов может быть достигнут путем двукратного изменения интервала.

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

Вероятности принятия

Вероятность перехода из текущего состояния в новое состояние-кандидат определяется функцией вероятности принятия , которая зависит от энергий и двух состояний, а также от глобального изменяющегося во времени параметра, называемого температурой . Состояния с меньшей энергией лучше, чем состояния с большей энергией. Функция вероятности должна быть положительной, даже когда больше . Эта функция не позволяет методу застрять на локальном минимуме, который хуже глобального. $с$ $s_{\mathrm {новый} }$ $P(e,e_{\mathrm {new}},T)$ $e=E(s)$ ${\ displaystyle e_ {\ mathrm {new} } = E (s_ {\ mathrm {new} })}$ $Т$ $P$ $e_{\mathrm {новый} }$ $е$

Когда стремится к нулю, вероятность должна стремиться к нулю, если и к положительному значению в противном случае. Для достаточно малых значений система будет все больше отдавать предпочтение ходам, которые идут «вниз» (т. е. к более низким значениям энергии), и избегать тех, которые идут «вверх». С процедурой сводится к жадному алгоритму , который делает только переходы вниз. $Т$ $P(e,e_{\mathrm {new}},T)$ $e_{\mathrm {new} }>e$ $T$ $T=0$

В первоначальном описании имитации отжига вероятность была равна 1, когда —т. е. процедура всегда двигалась вниз, когда находила способ сделать это, независимо от температуры. Многие описания и реализации имитации отжига все еще принимают это условие как часть определения метода. Однако это условие не является обязательным для работы метода. $P(e,e_{\mathrm {new} },T)$ $e_{\mathrm {new} }<e$

Функция обычно выбирается так, чтобы вероятность принятия хода уменьшалась при увеличении разницы, то есть небольшие подъемы более вероятны, чем большие. Однако это требование не является строго необходимым, при условии, что выполняются вышеуказанные требования. $P$ $e_{\mathrm {new} }-e$

Учитывая эти свойства, температура играет решающую роль в управлении эволюцией состояния системы с точки зрения ее чувствительности к изменениям энергий системы. Точнее, для большого значения эволюция чувствительна к более грубым изменениям энергии, в то время как она чувствительна к более тонким изменениям энергии, когда мало. $T$ $s$ $T$ $s$ $T$

График отжига

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

Название и вдохновение алгоритма требуют, чтобы интересная функция, связанная с изменением температуры, была встроена в рабочие характеристики алгоритма. Это требует постепенного снижения температуры по мере продолжения моделирования. Алгоритм изначально начинается с установки высокого значения (или бесконечности), а затем она уменьшается на каждом шаге, следуя некоторому графику отжига , который может быть указан пользователем, но должен заканчиваться ближе к концу выделенного временного бюджета. Таким образом, ожидается, что система будет сначала блуждать в направлении широкой области пространства поиска, содержащей хорошие решения, игнорируя небольшие особенности энергетической функции; затем дрейфовать в направлении областей с низкой энергией, которые становятся все уже и уже, и, наконец, двигаться вниз в соответствии с эвристикой наискорейшего спуска . $T$ $T=0$

Для любой заданной конечной задачи вероятность того, что алгоритм имитации отжига завершится глобальным оптимальным решением, приближается к 1 по мере расширения графика отжига. ^[11] Однако этот теоретический результат не особенно полезен, поскольку время, необходимое для обеспечения значительной вероятности успеха, обычно превышает время, необходимое для полного поиска пространства решений . ^[12]

Псевдокод

Следующий псевдокод представляет эвристику имитации отжига, как описано выше. Она начинается с состояния $s 0$ и продолжается до тех пор, пока не будет выполнено максимум $k max$ шагов. В процессе вызов $neighbor(s)$ должен генерировать случайно выбранного соседа заданного состояния $s$ ; вызов $random(0, 1)$ должен выбрать и вернуть значение в диапазоне $[0, 1]$ , равномерно случайным образом . Расписание отжига определяется вызовом $temperatura(r)$ , который должен выдавать температуру для использования, учитывая долю $r$ временного бюджета, которая была затрачена до сих пор.

Пусть $с = с 0$
Для k = 0 до k _max (исключая):
- $T \leftarrow температура( 1 - (k+ 1) / k макс)$
- Выберите случайного соседа, $s new \leftarrow сосед(и)$
- Если P ( E ( s ), E ( s _new ), T ) ≥ random(0, 1) :
  - $с \leftarrow с новый$
Выход: конечное состояние $s$

Выбор параметров

Чтобы применить метод имитации отжига к конкретной проблеме, необходимо указать следующие параметры: пространство состояний, энергетическую (целевую) функцию E(), процедуру генератора кандидатов neighbor (), функцию вероятности принятия P()и график отжига temperature()И начальную температуру init_temp. Эти выборы могут оказать значительное влияние на эффективность метода. К сожалению, нет выбора этих параметров, который был бы хорош для всех проблем, и нет общего способа найти лучший выбор для данной проблемы. В следующих разделах приведены некоторые общие рекомендации.

Достаточно близко к соседу

Имитация отжига может быть смоделирована как случайное блуждание по графу поиска, вершинами которого являются все возможные состояния, а ребрами — кандидаты на ходы. Существенным требованием к функции neighbor ()является то, что она должна обеспечивать достаточно короткий путь на этом графе от начального состояния до любого состояния, которое может быть глобальным оптимумом — диаметр графа поиска должен быть небольшим. Например, в приведенном выше примере коммивояжера пространство поиска для n = 20 городов имеет n! = 2 432 902 008 176 640 000 (2,4 квинтиллиона) состояний; однако число соседей каждой вершины равно ребрам (исходя из n, выбираем 20), а диаметр графа равен . $\sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}=190$ $n-1$

Вероятности перехода

Чтобы исследовать поведение имитации отжига на конкретной задаче, может быть полезно рассмотреть вероятности перехода , которые являются результатом различных вариантов дизайна, сделанных при реализации алгоритма. Для каждого ребра графа поиска вероятность перехода определяется как вероятность того, что алгоритм имитации отжига перейдет в состояние, когда его текущее состояние равно . Эта вероятность зависит от текущей температуры, как указано , от порядка, в котором кандидаты-ходы генерируются функцией , и от функции вероятности принятия . (Обратите внимание, что вероятность перехода не просто , поскольку кандидаты тестируются последовательно.) $(s,s')$ $s'$ $s$ temperature()neighbor ()P() $P(e,e',T)$

Вероятности принятия

Спецификация neighbour(), P(), и temperature()частично избыточна. На практике обычно используют одну и ту же функцию принятия P()для многих задач и корректируют две другие функции в соответствии с конкретной задачей.

В формулировке метода Киркпатрика и др. функция вероятности принятия была определена как 1, если , и в противном случае. Эта формула была поверхностно обоснована по аналогии с переходами физической системы; она соответствует алгоритму Метрополиса–Гастингса , в случае, когда T=1 и распределение предложений Метрополиса–Гастингса симметрично. Однако эта вероятность принятия часто используется для имитации отжига, даже когда функция , которая аналогична распределению предложений в Метрополисе–Гастингсе, не является симметричной или вообще не является вероятностной. В результате вероятности перехода алгоритма имитации отжига не соответствуют переходам аналогичной физической системы, и долгосрочное распределение состояний при постоянной температуре не обязательно должно иметь какое-либо сходство с распределением термодинамического равновесия по состояниям этой физической системы при любой температуре. Тем не менее, большинство описаний имитации отжига предполагают исходную функцию принятия, которая, вероятно, жестко закодирована во многих реализациях SA. $P(e,e',T)$ $e'<e$ $\exp(-(e'-e)/T)$ neighbor () $T$

В 1990 году Москато и Фонтанари ^[13] и независимо Дюк и Шойер ^[14] предположили, что детерминированное обновление (то есть не основанное на правиле вероятностного принятия) может ускорить процесс оптимизации, не влияя на конечное качество. Москато и Фонтанари, наблюдая аналог кривой «удельной теплоты» отжига «обновления порога», возникшей в их исследовании, делают вывод, что «стохастичность обновления Метрополиса в алгоритме имитационного отжига не играет большой роли в поиске почти оптимальных минимумов». Вместо этого они предположили, что «сглаживание ландшафта функции стоимости при высокой температуре и постепенное определение минимумов в процессе охлаждения являются основными составляющими успеха имитационного отжига». Метод впоследствии популяризировался под названием «прием порога» благодаря названию Дюка и Шойера. В 2001 году Франц, Хоффманн и Саламон показали, что детерминированная стратегия обновления действительно является оптимальной в большом классе алгоритмов, которые имитируют случайное блуждание по ландшафту стоимости/энергии. ^[15]

Эффективная генерация кандидатов

При выборе генератора neighbor ()-кандидата необходимо учитывать, что после нескольких итераций алгоритма имитации отжига ожидается, что текущее состояние будет иметь гораздо более низкую энергию, чем случайное состояние. Поэтому, как правило, следует наклонять генератор в сторону ходов-кандидатов, где энергия целевого состояния, вероятно, будет близка к энергии текущего состояния. Эта эвристика (которая является основным принципом алгоритма Метрополиса–Гастингса ) имеет тенденцию исключать как очень хорошие ходы-кандидаты, так и очень плохие ; однако первые обычно встречаются гораздо реже, чем вторые, поэтому эвристика, как правило, довольно эффективна. $s'$

В задаче коммивояжера выше, например, ожидается, что обмен двух последовательных городов в низкоэнергетическом туре окажет скромное влияние на его энергию (длину); тогда как обмен двух произвольных городов с гораздо большей вероятностью увеличит его длину, чем уменьшит ее. Таким образом, ожидается, что генератор соседей с последовательным обменом будет работать лучше, чем генератор с произвольным обменом, хотя последний может обеспечить несколько более короткий путь к оптимуму (с обменами вместо ). $n-1$ $n(n-1)/2$

Более точное утверждение эвристики заключается в том, что следует попробовать первые кандидатные состояния, для которых велико. Для «стандартной» функции принятия выше это означает, что имеет порядок или меньше. Таким образом, в примере с коммивояжером выше можно использовать функцию, которая меняет местами два случайных города, где вероятность выбора пары городов исчезает по мере увеличения их расстояния сверх . $s'$ $P(E(s),E(s'),T)$ $P$ $E(s')-E(s)$ $T$ neighbor () $T$

Избегание барьеров

При выборе кандидата-генератора neighbor ()необходимо также попытаться сократить количество «глубоких» локальных минимумов — состояний (или наборов связанных состояний), которые имеют гораздо более низкую энергию, чем все его соседние состояния. Такие «закрытые водосборные бассейны» энергетической функции могут захватить алгоритм имитации отжига с высокой вероятностью (примерно пропорциональной числу состояний в бассейне) и на очень долгое время (примерно экспоненциальное от разности энергий между окружающими состояниями и дном бассейна).

Как правило, невозможно разработать генератор кандидатов, который будет удовлетворять этой цели и также отдавать приоритет кандидатам с похожей энергией. С другой стороны, часто можно значительно повысить эффективность имитации отжига путем относительно простых изменений в генераторе. Например, в задаче коммивояжера несложно продемонстрировать два тура , , с почти одинаковой длиной, так что (1) является оптимальным, (2) каждая последовательность обменов парами городов, которая преобразуется в , проходит через туры, которые намного длиннее обоих, и (3) может быть преобразована в путем переворачивания (изменения порядка) набора последовательных городов. В этом примере и лежат в разных «глубоких бассейнах», если генератор выполняет только случайные обмены парами; но они будут находиться в одном бассейне, если генератор выполняет случайные перевороты сегментов. $A$ $B$ $A$ $A$ $B$ $A$ $B$ $A$ $B$

График охлаждения

Физическая аналогия, которая используется для обоснования имитации отжига, предполагает, что скорость охлаждения достаточно низка для того, чтобы распределение вероятностей текущего состояния всегда было близко к термодинамическому равновесию . К сожалению, время релаксации — время, которое необходимо ждать для восстановления равновесия после изменения температуры — сильно зависит от «топографии» энергетической функции и от текущей температуры. В алгоритме имитации отжига время релаксации также зависит от генератора-кандидата, причем очень сложным образом. Обратите внимание, что все эти параметры обычно предоставляются как функции черного ящика для алгоритма имитации отжига. Поэтому идеальную скорость охлаждения невозможно определить заранее, и ее следует эмпирически корректировать для каждой задачи. Адаптивные алгоритмы имитации отжига решают эту проблему, связывая график охлаждения с ходом поиска. Другие адаптивные подходы, такие как термодинамическая имитация отжига ^[16], автоматически корректируют температуру на каждом шаге на основе разницы энергий между двумя состояниями в соответствии с законами термодинамики.

Перезапуски

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

Связанные методы

Взаимодействующие алгоритмы Метрополиса-Хастинга (также известные как последовательный Монте-Карло ^[17] ) объединяют имитацию отжига с принятием-отклонением наиболее подходящих особей, оснащенных взаимодействующим механизмом рециркуляции.
Квантовый отжиг использует «квантовые флуктуации» вместо тепловых флуктуаций для преодоления высоких, но тонких барьеров в целевой функции.
Стохастическое туннелирование пытается преодолеть возрастающую трудность, с которой сталкиваются имитационные процессы отжига при выходе из локальных минимумов по мере снижения температуры, путем «туннелирования» через барьеры.
Поиск с запретами обычно переходит в соседние состояния с более низкой энергией, но будет предпринимать подъемы, когда застрянет в локальном минимуме; и избегает циклов, сохраняя «список запретов» уже просмотренных решений.
Двухфазная эволюция — это семейство алгоритмов и процессов (к которым относится имитация отжига), которые выполняют роль посредника между локальным и глобальным поиском, используя изменения фаз в пространстве поиска.
Реактивная поисковая оптимизация фокусируется на объединении машинного обучения с оптимизацией путем добавления внутреннего цикла обратной связи для самостоятельной настройки свободных параметров алгоритма в соответствии с характеристиками проблемы, экземпляра и локальной ситуации вокруг текущего решения.
Генетические алгоритмы поддерживают пул решений, а не только одно. Новые решения-кандидаты генерируются не только «мутацией» (как в SA), но и «рекомбинацией» двух решений из пула. Вероятностные критерии, аналогичные используемым в SA, используются для выбора кандидатов на мутацию или комбинацию, а также для отбрасывания избыточных решений из пула.
Меметические алгоритмы ищут решения, используя набор агентов, которые как сотрудничают, так и конкурируют в этом процессе; иногда стратегии агентов включают в себя процедуры имитации отжига для получения высококачественных решений перед их рекомбинацией. ^[18] Отжиг также был предложен как механизм для увеличения разнообразия поиска. ^[19]
Градуированная оптимизация дегрессивно «сглаживает» целевую функцию в процессе оптимизации.
Оптимизация муравьиной колонии (ACO) использует множество муравьев (или агентов) для обхода пространства решений и поиска локально продуктивных областей.
Метод кросс-энтропии (CE) генерирует решения-кандидаты с помощью параметризованного распределения вероятностей. Параметры обновляются с помощью минимизации кросс-энтропии, чтобы генерировать лучшие образцы в следующей итерации.
Поиск гармонии имитирует импровизацию музыкантов, где каждый музыкант играет ноту, чтобы вместе найти наилучшую гармонию.
Стохастическая оптимизация представляет собой комплекс методов, включающий имитацию отжига и множество других подходов.
Оптимизация роя частиц — это алгоритм, смоделированный на основе роевого интеллекта, который находит решение задачи оптимизации в пространстве поиска или моделирует и прогнозирует социальное поведение при наличии целей.
Алгоритм «бегунок-корень» (RRA) — это метаэвристический алгоритм оптимизации для решения унимодальных и многомодальных задач, вдохновленный побегами и корнями растений в природе.
Интеллектуальный алгоритм капель воды (IWD), который имитирует поведение естественных капель воды для решения задач оптимизации
Параллельная закалка представляет собой моделирование копий моделей при различных температурах (или гамильтонианах ) для преодоления потенциальных барьеров.
Многоцелевые алгоритмы имитации отжига использовались в многоцелевой оптимизации . ^[20]

Смотрите также

Ссылки

^ «Что такое имитация отжига?». www.cs.cmu.edu . Получено 13.05.2023 .
^ Пинкус, Мартин (ноябрь–декабрь 1970 г.). «Метод Монте-Карло для приближенного решения некоторых типов задач ограниченной оптимизации». Журнал Американского общества исследований операций . 18 (6): 967–1235. doi :10.1287/opre.18.6.1225.
^ Хачатурян, А.: Семеновская, С.: Вайнштейн Б., Армен (1979). «Статистически-термодинамический подход к определению фаз амплитуды структуры». Советская физическая кристаллография . 24 (5): 519–524.{{cite journal}}: CS1 maint: multiple names: authors list (link)
^ Хачатурян, А.; Семеновская, С.; Вайнштейн, Б. (1981). «Термодинамический подход к структурному анализу кристаллов». Acta Crystallographica . A37 (5): 742–754. Bibcode : 1981AcCrA..37..742K. doi : 10.1107/S0567739481001630.{{cite journal}}: CS1 maint: multiple names: authors list (link)
^ Лаарховен, ван PJM (Питер JM) (1987). Имитированный отжиг: теория и приложения. Аартс, ЭХЛ (Эмиль ХЛ). Дордрехт: Д. Рейдель. ISBN 90-277-2513-6. OCLC 15548651.
^ ab Kirkpatrick, S.; Gelatt Jr, CD; Vecchi, MP (1983). "Оптимизация с помощью имитации отжига". Science . 220 (4598): 671–680. Bibcode :1983Sci...220..671K. CiteSeerX 10.1.1.123.7607 . doi :10.1126/science.220.4598.671. JSTOR 1690046. PMID 17813860. S2CID 205939.
^ Хачатурян, А.; Семеновская, С.; Вайнштейн, Б. (1979). «Статистически-термодинамический подход к определению фаз амплитуды структуры». Сов. физ. кристаллография . 24 (5): 519–524.
^ Хачатурян, А.; Семеновская, С.; Вайнштейн, Б. (1981). «Термодинамический подход к структурному анализу кристаллов». Acta Crystallographica . 37 (A37): 742–754. Bibcode : 1981AcCrA..37..742K. doi : 10.1107/S0567739481001630.
^ Черны, В. (1985). «Термодинамический подход к задаче коммивояжера: эффективный алгоритм моделирования». Журнал теории оптимизации и приложений . 45 : 41–51. doi :10.1007/BF00940812. S2CID 122729427.
^ Метрополис, Николас; Розенблут, Арианна В.; Розенблут, Маршалл Н.; Теллер, Августа Х.; Теллер, Эдвард (1953). «Вычисления уравнений состояния с помощью быстрых вычислительных машин». Журнал химической физики . 21 (6): 1087. Bibcode : 1953JChPh..21.1087M. doi : 10.1063/1.1699114. OSTI 4390578. S2CID 1046577.
^ Гранвиль, В.; Криванек, М.; Рассон, Ж.-П. (1994). «Имитация отжига: доказательство сходимости». Труды IEEE по анализу шаблонов и машинному интеллекту . 16 (6): 652–656. doi :10.1109/34.295910.
^ Нольте, Андреас; Шрадер, Райнер (1997), «Заметка о поведении конечного времени при имитации отжига», Труды по исследованию операций 1996 , т. 1996, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 175–180, doi :10.1007/978-3-642-60744-8_32, ISBN 978-3-540-62630-5, получено 2023-02-06
^ Москато, П.; Фонтанари, Дж. Ф. (1990), «Стохастическое и детерминированное обновление в моделируемом отжиге», Physics Letters A , 146 (4): 204–208, Bibcode : 1990PhLA..146..204M, doi : 10.1016/0375-9601(90)90166-L
^ Дьюк, Г.; Шойер, Т. (1990), «Принятие порога: универсальный алгоритм оптимизации, превосходящий имитацию отжига», Журнал вычислительной физики , 90 (1): 161–175, Bibcode : 1990JCoPh..90..161D, doi : 10.1016/0021-9991(90)90201-B, ISSN 0021-9991
^ Франц, А.; Хоффманн, К. Х.; Саламон, П. (2001), «Лучшая оптимальная стратегия поиска основных состояний», Physical Review Letters , 86 (3): 5219–5222, doi :10.1103/PhysRevLett.86.5219, PMID 11384462
^ Де Висенте, Хуан; Ланчарес, Хуан; Эрмида, Роман (2003). «Размещение методом термодинамического моделирования отжига». Буквы по физике А. 317 (5–6): 415–423. Бибкод : 2003PhLA..317..415D. doi :10.1016/j.physleta.2003.08.070.
^ Дель Мораль, Пьер; Дусе, Арно; Ясра, Аджай (2006). «Последовательные пробоотборники Монте-Карло». Журнал Королевского статистического общества, серия B. 68 (3): 411–436. arXiv : cond-mat/0212648 . дои : 10.1111/j.1467-9868.2006.00553.x. S2CID 12074789.
^ Москато, Пабло (июнь 1993 г.). «Введение в популяционные подходы к оптимизации и иерархическим целевым функциям: обсуждение роли поиска с запретами». Annals of Operations Research . 41 (2): 85–121. doi :10.1007/BF02022564. S2CID 35382644.
^ Москато, П. (1989). «Об эволюции, поиске, оптимизации, генетических алгоритмах и боевых искусствах: на пути к меметическим алгоритмам». Программа параллельных вычислений Калтеха (отчет 826).
^ Деб, Бандйопадхай (июнь 2008 г.). «Алгоритм многоцелевой оптимизации на основе имитации отжига: AMOSA». Труды IEEE по эволюционным вычислениям . 12 (3): 269–283. doi :10.1109/TEVC.2007.900837. S2CID 12107321.

Дальнейшее чтение

А. Дас и Б.К. Чакрабарти (редакторы), Квантовый отжиг и связанные с ним методы оптимизации, лекции по физике, том 679, Springer, Гейдельберг (2005)
Вайнбергер, Э. (1990). «Коррелированные и некоррелированные ландшафты приспособленности и как их отличить». Биологическая кибернетика . 63 (5): 325–336. doi :10.1007/BF00202749. S2CID 851736.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Раздел 10.12. Методы имитации отжига". Numerical Recipes: The Art of Scientific Computing (3-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-88068-8. Архивировано из оригинала 2011-08-11 . Получено 2011-08-13 .
Штробл, MAR; Баркер, Д. (2016). «О фазовых переходах с имитацией отжига в реконструкции филогении». Молекулярная филогенетика и эволюция . 101 : 46–55. Bibcode :2016MolPE.101...46S. doi :10.1016/j.ympev.2016.05.001. PMC 4912009 . PMID 27150349.
В.Васильев, А.Прахова: «Использование имитационного отжига в управлении гибкими производственными системами», Международный журнал ИНФОРМАЦИОННЫЕ ТЕОРИИ И ПРИЛОЖЕНИЯ, ТОМ 6/1999

Внешние ссылки

Имитация отжига Приложение Javascript, позволяющее экспериментировать с имитацией отжига. Исходный код включен.
«Алгоритм общего моделирования отжига» Архивировано 23 сентября 2008 г. на Wayback Machine Программа MATLAB с открытым исходным кодом для общих упражнений по моделированию отжига.
Самостоятельное занятие по имитации отжига. Проект Викиверситета.
Google в суперпозиции использования и неиспользования квантового компьютера Ars Technica обсуждает возможность того, что компьютер D-Wave, используемый Google, на самом деле может быть эффективным сопроцессором с имитацией отжига.
[1] Алгоритм многокритериальной оптимизации на основе имитации отжига: AMOSA.