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

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

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

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

Подобные методы независимо применялись несколько раз, в том числе Пинкус (1970), ^{[ 2 ]} Хачатурян и др. (1979, ^{[ 3 ]} 1981 ^{[ 4 ]}), Киркпатрик, Гелатт и Векки (1983) и Черни (1985). ^{[ 5 ]} В 1983 году этот подход использовали Киркпатрик, Гелатт-младший, Векки, ^{[ 6 ]} для решения задачи коммивояжера . Они также предложили его нынешнее название — имитация отжига.

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

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

Обзор

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

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

Базовая итерация

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

Соседи государства

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

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

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

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

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

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

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

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

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

Быстрый

Медленный

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

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

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

Псевдокод

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

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

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

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

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

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

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

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

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

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

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

В 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 () необходимо также попытаться уменьшить количество «глубоких» локальных минимумов — состояний (или наборов связанных состояний), которые имеют гораздо меньшую энергию, чем все соседние состояния. Такие «закрытые водосборные бассейны» энергетической функции могут захватывать алгоритм моделирования отжига с высокой вероятностью (примерно пропорционально числу состояний в бассейне) и на очень длительное время (примерно экспоненциально от разницы в энергии между окружающими состояниями и дно бассейна).

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

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

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

Перезапускает

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

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

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

См. также

Ссылки

^ «Что такое имитация отжига?» . www.cs.cmu.edu . Проверено 13 мая 2023 г.
^ Пинкус, Мартин (ноябрь – декабрь 1970 г.). «Метод Монте-Карло для приближенного решения некоторых типов задач оптимизации с ограничениями». Журнал Американского общества исследования операций . 18 (6): 967–1235. дои : 10.1287/опре.18.6.1225 .
^ Хачатурян, А.: Семеновская, С.: Вайнштейн Б., Армен (1979). «Статистически-термодинамический подход к определению фаз амплитуды структуры». Советская Физика, Кристаллография . 24 (5): 519–524. {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Хачатурян А.; Семеновская С.; Вайнштейн, Б. (1981). «Термодинамический подход к структурному анализу кристаллов» . Акта Кристаллографика . А37 (5): 742–754. Бибкод : 1981AcCrA..37..742K . дои : 10.1107/S0567739481001630 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Лаарховен, ван П.Дж.М. (Питер Дж.М.) (1987). Имитированный отжиг: теория и приложения . Аартс, ЭХЛ (Эмиль ХЛ). Дордрехт: Д. Рейдель. ISBN 90-277-2513-6 . OCLC 15548651 .
^ Перейти обратно: ^а ^б Киркпатрик, С.; Гелатт-младший, компакт-диск; Векки, член парламента (1983). «Оптимизация путем моделирования отжига». Наука . 220 (4598): 671–680. Бибкод : 1983Sci...220..671K . CiteSeerX 10.1.1.123.7607 . дои : 10.1126/science.220.4598.671 . JSTOR 1690046 . ПМИД 17813860 . S2CID 205939 .
^ Хачатурян А.; Семеновская С.; Вайнштейн, Б. (1979). «Статистически-термодинамический подход к определению фаз амплитуды структуры». Сов.Физ. Кристаллография . 24 (5): 519–524.
^ Хачатурян А.; Семеновская С.; Вайнштейн, Б. (1981). «Термодинамический подход к структурному анализу кристаллов». Акта Кристаллографика . 37 (А37): 742–754. Бибкод : 1981AcCrA..37..742K . дои : 10.1107/S0567739481001630 .
^ Черный, В. (1985). «Термодинамический подход к задаче коммивояжера: эффективный алгоритм моделирования». Журнал теории оптимизации и приложений . 45 : 41–51. дои : 10.1007/BF00940812 . S2CID 122729427 .
^ Метрополис, Николай; Розенблут, Арианна В.; Розенблут, Маршалл Н.; Теллер, Огаста Х.; Теллер, Эдвард (1953). «Уравнение вычислений состояния с помощью быстрых вычислительных машин». Журнал химической физики . 21 (6): 1087. Бибкод : 1953ЖЧФ..21.1087М . дои : 10.1063/1.1699114 . ОСТИ 4390578 . S2CID 1046577 .
^ Гранвиль, В.; Криванек, М.; Рассон, Ж.-П. (1994). «Имитированный отжиг: доказательство сходимости». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 16 (6): 652–656. дои : 10.1109/34.295910 .
^ Нольте, Андреас; Шредер, Райнер (1997), «Заметки о поведении моделирования отжига в конечном времени» , Operations Research Proceedings 1996 , vol. 1996, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 175–180, doi : 10.1007/978-3-642-60744-8_32 , ISBN 978-3-540-62630-5 , получено 6 февраля 2023 г.
^ Москато, П.; Фонтанари, Дж. Ф. (1990), «Стохастическое и детерминистическое обновление при моделировании отжига», Physics Letters A , 146 (4): 204–208, Бибкод : 1990PhLA..146..204M , doi : 10.1016/0375-9601(90) 90166-Л
^ Дуек, Г.; Шойер, Т. (1990), «Принятие порога: алгоритм оптимизации общего назначения, превосходящий имитацию отжига», Journal of Computational Physics , 90 (1): 161–175, Bibcode : 1990JCoPh..90..161D , doi : 10.1016/0021-9991(90)90201-Б , 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 . дои : 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 г.). «Введение в популяционные подходы к оптимизации и иерархические целевые функции: обсуждение роли табу-поиска». Анналы исследования операций . 41 (2): 85–121. дои : 10.1007/BF02022564 . S2CID 35382644 .
^ Москато, П. (1989). «Об эволюции, поиске, оптимизации, генетических алгоритмах и боевых искусствах: на пути к меметическим алгоритмам». Программа параллельных вычислений Калифорнийского технологического института (отчет 826).
^ Деб, Бандиопадьяй (июнь 2008 г.). «Алгоритм многокритериальной оптимизации на основе моделирования отжига: AMOSA». Транзакции IEEE в эволюционных вычислениях . 12 (3): 269–283. дои : 10.1109/TEVC.2007.900837 . S2CID 12107321 .

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

А. Дас и Б.К. Чакрабарти (ред.), Квантовый отжиг и связанные с ним методы оптимизации, Конспект лекций по физике, Vol. 679, Шпрингер, Гейдельберг (2005)
Вайнбергер, Э. (1990). «Коррелированные и некоррелированные фитнес-ландшафты и как отличить их». Биологическая кибернетика . 63 (5): 325–336. дои : 10.1007/BF00202749 . S2CID 851736 .
Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 10.12. Методы моделирования отжига» . Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8 . Архивировано из оригинала 11 августа 2011 г. Проверено 13 августа 2011 г.
Штробль, Маргария; Баркер, Д. (2016). «О моделировании фазовых переходов отжига в реконструкции филогении» . Молекулярная филогенетика и эволюция . 101 : 46–55. Бибкод : 2016МолПЭ.101...46С . дои : 10.1016/j.ympev.2016.05.001 . ПМК 4912009 . ПМИД 27150349 .
В. Васильев, А. Прахова: «Использование имитации отжига в управлении гибкими производственными системами», Международный журнал INFORMATION THEORIES & APPLICATIONS, ТОМ 6/1999.

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

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

[1] «Что такое имитация отжига?» . www.cs.cmu.edu . Проверено 13 мая 2023 г.

[2] Пинкус, Мартин (ноябрь – декабрь 1970 г.). «Метод Монте-Карло для приближенного решения некоторых типов задач оптимизации с ограничениями». Журнал Американского общества исследования операций . 18 (6): 967–1235. дои : 10.1287/опре.18.6.1225 .

[3] Хачатурян, А.: Семеновская, С.: Вайнштейн Б., Армен (1979). «Статистически-термодинамический подход к определению фаз амплитуды структуры». Советская Физика, Кристаллография . 24 (5): 519–524. {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[4] Хачатурян А.; Семеновская С.; Вайнштейн, Б. (1981). «Термодинамический подход к структурному анализу кристаллов» . Акта Кристаллографика . А37 (5): 742–754. Бибкод : 1981AcCrA..37..742K . дои : 10.1107/S0567739481001630 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[5] Лаарховен, ван П.Дж.М. (Питер Дж.М.) (1987). Имитированный отжиг: теория и приложения . Аартс, ЭХЛ (Эмиль ХЛ). Дордрехт: Д. Рейдель. ISBN 90-277-2513-6 . OCLC 15548651 .

[:2-6] Перейти обратно: ^а ^б Киркпатрик, С.; Гелатт-младший, компакт-диск; Векки, член парламента (1983). «Оптимизация путем моделирования отжига». Наука . 220 (4598): 671–680. Бибкод : 1983Sci...220..671K . CiteSeerX 10.1.1.123.7607 . дои : 10.1126/science.220.4598.671 . JSTOR 1690046 . ПМИД 17813860 . S2CID 205939 .

[:0-7] Хачатурян А.; Семеновская С.; Вайнштейн, Б. (1979). «Статистически-термодинамический подход к определению фаз амплитуды структуры». Сов.Физ. Кристаллография . 24 (5): 519–524.

[:1-8] Хачатурян А.; Семеновская С.; Вайнштейн, Б. (1981). «Термодинамический подход к структурному анализу кристаллов». Акта Кристаллографика . 37 (А37): 742–754. Бибкод : 1981AcCrA..37..742K . дои : 10.1107/S0567739481001630 .

[9] Черный, В. (1985). «Термодинамический подход к задаче коммивояжера: эффективный алгоритм моделирования». Журнал теории оптимизации и приложений . 45 : 41–51. дои : 10.1007/BF00940812 . S2CID 122729427 .

[:4-10] Метрополис, Николай; Розенблут, Арианна В.; Розенблут, Маршалл Н.; Теллер, Огаста Х.; Теллер, Эдвард (1953). «Уравнение вычислений состояния с помощью быстрых вычислительных машин». Журнал химической физики . 21 (6): 1087. Бибкод : 1953ЖЧФ..21.1087М . дои : 10.1063/1.1699114 . ОСТИ 4390578 . S2CID 1046577 .

[11] Гранвиль, В.; Криванек, М.; Рассон, Ж.-П. (1994). «Имитированный отжиг: доказательство сходимости». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 16 (6): 652–656. дои : 10.1109/34.295910 .

[12] Нольте, Андреас; Шредер, Райнер (1997), «Заметки о поведении моделирования отжига в конечном времени» , Operations Research Proceedings 1996 , vol. 1996, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 175–180, doi : 10.1007/978-3-642-60744-8_32 , ISBN 978-3-540-62630-5 , получено 6 февраля 2023 г.

[13] Москато, П.; Фонтанари, Дж. Ф. (1990), «Стохастическое и детерминистическое обновление при моделировании отжига», Physics Letters A , 146 (4): 204–208, Бибкод : 1990PhLA..146..204M , doi : 10.1016/0375-9601(90) 90166-Л

[14] Дуек, Г.; Шойер, Т. (1990), «Принятие порога: алгоритм оптимизации общего назначения, превосходящий имитацию отжига», Journal of Computational Physics , 90 (1): 161–175, Bibcode : 1990JCoPh..90..161D , doi : 10.1016/0021-9991(90)90201-Б , ISSN 0021-9991

[15] Франц, А.; Хоффманн, К.Х.; Саламон, П. (2001), «Лучшая оптимальная стратегия поиска основных состояний», Physical Review Letters , 86 (3): 5219–5222, doi : 10.1103/PhysRevLett.86.5219 , PMID 11384462

[16] Де Висенте, Хуан; Ланчарес, Хуан; Гермида, Роман (2003). «Размещение методом термодинамического моделирования отжига». Письма по физике А. 317 (5–6): 415–423. Бибкод : 2003PhLA..317..415D . дои : 10.1016/j.physleta.2003.08.070 .

[:3-17] Дель Мораль, Пьер; Дусе, Арно; Ясра, Аджай (2006). «Последовательные пробоотборники Монте-Карло». Журнал Королевского статистического общества, серия B. 68 (3): 411–436. arXiv : cond-mat/0212648 . дои : 10.1111/j.1467-9868.2006.00553.x . S2CID 12074789 .

[18] Москато, Пабло (июнь 1993 г.). «Введение в популяционные подходы к оптимизации и иерархические целевые функции: обсуждение роли табу-поиска». Анналы исследования операций . 41 (2): 85–121. дои : 10.1007/BF02022564 . S2CID 35382644 .

[martial_arts-19] Москато, П. (1989). «Об эволюции, поиске, оптимизации, генетических алгоритмах и боевых искусствах: на пути к меметическим алгоритмам». Программа параллельных вычислений Калифорнийского технологического института (отчет 826).

[20] Деб, Бандиопадьяй (июнь 2008 г.). «Алгоритм многокритериальной оптимизации на основе моделирования отжига: AMOSA». Транзакции IEEE в эволюционных вычислениях . 12 (3): 269–283. дои : 10.1109/TEVC.2007.900837 . S2CID 12107321 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]