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

Метод вероятностной оптимизации и метаэвристика

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

Задача коммивояжера в 3D для 120 точек решена с помощью моделирования отжига.

Имитированный отжиг ( 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 . Эти вероятности в конечном итоге приводят систему к переходу в состояния с более низкой энергией. Обычно этот шаг повторяется до тех пор, пока система не достигнет состояния, достаточно хорошего для приложения, или пока заданный бюджет вычислений не будет исчерпан.

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

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

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

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

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

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

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

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

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

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

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

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

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

Псевдокод

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обход барьеров

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

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

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

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

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

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

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

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

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

• Адаптивный моделируемый отжиг
• Автоматическое размещение этикеток
• Комбинаторная оптимизация
• Двухфазная эволюция
• Разрезы графов в компьютерном зрении
• Интеллектуальный алгоритм капель воды
• Цепь Маркова
• Молекулярная динамика
• Мультидисциплинарная оптимизация
• Оптимизация роя частиц
• Место и маршрут
• Квантовый отжиг
• Задача коммивояжера

Рекомендации

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: multiple names: authors list (link)
4. Хачатурян, А.; Семеновская С.; Вайнштейн, Б. (1981). «Термодинамический подход к структурному анализу кристаллов». Акта Кристаллографика . А37 (5): 742–754. Бибкод : 1981AcCrA..37..742K. дои : 10.1107/S0567739481001630.{{cite journal}}: CS1 maint: multiple names: authors list (link)
5. Лаарховен, ван PJM (Питер JM) (1987). Имитированный отжиг: теория и приложения. Аартс, ЭХЛ (Эмиль ХЛ). Дордрехт: Д. Рейдель. ISBN 90-277-2513-6. ОСЛК  15548651.
6. Киркпатрик, С.; Гелатт-младший, компакт-диск; Векки, член парламента (1983). «Оптимизация путем моделирования отжига». Наука . 220 (4598): 671–680. Бибкод : 1983Sci...220..671K. CiteSeerX 10.1.1.123.7607 . дои : 10.1126/science.220.4598.671. JSTOR  1690046. PMID  17813860. S2CID  205939. 
7. Хачатурян, А.; Семеновская С.; Вайнштейн, Б. (1979). «Статистически-термодинамический подход к определению фаз амплитуды структуры». Сов.Физ. Кристаллография . 24 (5): 519–524.
8. Хачатурян, А.; Семеновская С.; Вайнштейн, Б. (1981). «Термодинамический подход к структурному анализу кристаллов». Акта Кристаллографика . 37 (А37): 742–754. Бибкод : 1981AcCrA..37..742K. дои : 10.1107/S0567739481001630.
9. Черны, В. (1985). «Термодинамический подход к задаче коммивояжера: эффективный алгоритм моделирования». Журнал теории оптимизации и приложений . 45 : 41–51. дои : 10.1007/BF00940812. S2CID  122729427.
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 , Берлин, Гейдельберг: Springer Berlin Heidelberg, vol. 1996, стр. 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. doi :10.1016/j.physleta.2003.08.070.
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.
19. Москато, П. (1989). «Об эволюции, поиске, оптимизации, генетических алгоритмах и боевых искусствах: на пути к меметическим алгоритмам». Программа параллельных вычислений Калифорнийского технологического института (отчет 826).
20. Деб, Bandyopadhyay (июнь 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.
• Штробль, Маргария; Баркер, Д. (2016). «О моделировании фазовых переходов отжига в реконструкции филогении». Молекулярная филогенетика и эволюция . 101 : 46–55. doi :10.1016/j.ympev.2016.05.001. ПМК  4912009 . ПМИД  27150349.
• В. Васильев, А. Прахова: «Использование имитации отжига в управлении гибкими производственными системами», Международный журнал INFORMATION THEORIES & APPLICATIONS, ТОМ 6/1999.

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

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