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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален.
Найти источники: «Имитация отжига» - новости · газеты · книги · ученый · JSTOR ( декабрь 2009 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

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

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

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

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

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

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

Обзор [ править ]

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

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

Базовая итерация [ править ]

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

Соседи штата [ править ]

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

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

Вероятности принятия [ править ]

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

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

В первоначальном описании имитации отжига вероятность была равна 1, когда - т.е. процедура всегда спускалась вниз, когда находила способ сделать это, независимо от температуры. Во многих описаниях и реализациях имитации отжига это условие все еще является частью определения метода. Однако это условие не обязательно для работы метода. ${\ Displaystyle Р (е, е _ {\ mathrm {новый}}, Т)}$ ${\ Displaystyle е _ {\ mathrm {новый}} <е}$

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

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

График отжига [ править ]

Медленный

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

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

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

Псевдокод [ править ]

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

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

Выбор параметров [ редактировать ]

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

Достаточно близко к соседу [ править ]

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

Вероятности перехода [ править ]

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

Вероятности принятия [ править ]

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

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

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

Эффективная генерация кандидатов [ править ]

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

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

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

Избегание барьеров [ править ]

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

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

График охлаждения [ править ]

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

Перезапускается [ править ]

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

Связанные методы [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

↑ Пинкус, Мартин (ноябрь – декабрь 1970 г.). "Метод Монте-Карло для приближенного решения некоторых типов задач оптимизации с ограничениями" . Журнал Американского общества исследования операций . 18 (6): 967–1235. doi : 10.1287 / opre.18.6.1225 - через JSTOR.
^ Хачатурян, А .: Семеновская, С .: Вайнштейн Б., Армен (1979). «Статистико-термодинамический подход к определению амплитудных фаз конструкций». Советская физика, Кристаллография . 24 (5): 519–524.CS1 maint: multiple names: authors list (link)
^ Хачатурян, А .; Семеновская, С .; Вайнштейн, Б. (1981). «Термодинамический подход к структурному анализу кристаллов» . Acta Crystallographica . A37 (5): 742–754. doi : 10.1107 / S0567739481001630 - через https://ui.adsabs.harvard.edu/abs/1981AcCrA..37..742K .CS1 maint: multiple names: authors list (link)
^ Laarhoven, PJM ван (Peter JM) (1987). Имитационный отжиг: теория и приложения . Аартс, ЭХЛ (Эмиль Х.Л.). Дордрехт: Д. Рейдел. ISBN 90-277-2513-6. OCLC 15548651 .
^ a b Киркпатрик, S .; Гелатт-младший, CD; Векки, депутат (1983). «Оптимизация путем имитации отжига». Наука . 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 .
^ Метрополис, Николай; Розенблут, Арианна В .; Rosenbluth, Marshall N .; Teller, Augusta H .; Теллер, Эдвард (1953). «Уравнение состояний на быстрых вычислительных машинах». Журнал химической физики . 21 (6): 1087. Полномочный код : 1953JChPh..21.1087M . DOI : 10.1063 / 1.1699114 .
^ Granville, V .; Криванек, М .; Рассон, Ж.-П. (1994). «Имитация отжига: доказательство сходимости». IEEE Transactions по анализу шаблонов и машинному анализу . 16 (6): 652–656. DOI : 10.1109 / 34.295910 .
^ Moscato, P .; Fontanari, И. Ф. (1990), "Стохастические по сравнению с детерминированным обновлением в моделируемом отжиге", Физика Буква A , 146 (4): 204-208, DOI : 10.1016 / 0375-9601 (90) 90166-L
^ Dueck, G .; Шойера, Т. (1990), "Порог приема: Алгоритм оптимизации общего назначения , появляющиеся выше моделируемого отжига", Журнал вычислительной физики , 90 (1): 161-175, DOI : 10,1016 / 0021-9991 (90) 90201- B , ISSN 0021-9991
^ Franz, A .; Hoffmann, KH; Саламон, P (2001), "Лучшая оптимальная стратегия для нахождения основных состояний", Physical Review Letters , 86 (3): 5219-5222, DOI : 10,1103 / PhysRevLett.86.5219 , PMID 11384462
^ Де Висенте, Хуан; Ланкарес, Хуан; Гермида, Роман (2003). «Размещение методом термодинамического отжига». Физика Буквы A . 317 (5–6): 415–423. Bibcode : 2003PhLA..317..415D . DOI : 10.1016 / j.physleta.2003.08.070 .
^ Дель Мораль, Пьер; Дусе, Арно; Ясра, Аджай (2006). «Последовательные пробоотборники Монте-Карло». Журнал Королевского статистического общества, Series B . 68 (3): 411–436. arXiv : cond-mat / 0212648 . DOI : 10.1111 / j.1467-9868.2006.00553.x . S2CID 12074789 .
^ Moscato, Пабло (Июнь 1993). «Введение в популяционные подходы для оптимизации и иерархических целевых функций: обсуждение роли запретного поиска». Анналы исследований операций . 41 (2): 85–121. DOI : 10.1007 / BF02022564 . S2CID 35382644 .
^ Moscato, P. (1989). «Об эволюции, поиске, оптимизации, генетических алгоритмах и боевых искусствах: к меметическим алгоритмам». Программа параллельных вычислений Калифорнийского технологического института (отчет 826).

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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

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

[2] Хачатурян, А .: Семеновская, С .: Вайнштейн Б., Армен (1979). «Статистико-термодинамический подход к определению амплитудных фаз конструкций». Советская физика, Кристаллография . 24 (5): 519–524.CS1 maint: multiple names: authors list (link)

[3] Хачатурян, А .; Семеновская, С .; Вайнштейн, Б. (1981). «Термодинамический подход к структурному анализу кристаллов» . Acta Crystallographica . A37 (5): 742–754. doi : 10.1107 / S0567739481001630 - через https://ui.adsabs.harvard.edu/abs/1981AcCrA..37..742K .CS1 maint: multiple names: authors list (link)

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

[:2-5] Киркпатрик, S .; Гелатт-младший, CD; Векки, депутат (1983). «Оптимизация путем имитации отжига». Наука . 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 .

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

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

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

[:4-9] Метрополис, Николай; Розенблут, Арианна В .; Rosenbluth, Marshall N .; Teller, Augusta H .; Теллер, Эдвард (1953). «Уравнение состояний на быстрых вычислительных машинах». Журнал химической физики . 21 (6): 1087. Полномочный код : 1953JChPh..21.1087M . DOI : 10.1063 / 1.1699114 .

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

[11] Moscato, P .; Fontanari, И. Ф. (1990), "Стохастические по сравнению с детерминированным обновлением в моделируемом отжиге", Физика Буква A , 146 (4): 204-208, DOI : 10.1016 / 0375-9601 (90) 90166-L

[12] Dueck, G .; Шойера, Т. (1990), "Порог приема: Алгоритм оптимизации общего назначения , появляющиеся выше моделируемого отжига", Журнал вычислительной физики , 90 (1): 161-175, DOI : 10,1016 / 0021-9991 (90) 90201- B , ISSN 0021-9991

[13] Franz, A .; Hoffmann, KH; Саламон, P (2001), "Лучшая оптимальная стратегия для нахождения основных состояний", Physical Review Letters , 86 (3): 5219-5222, DOI : 10,1103 / PhysRevLett.86.5219 , PMID 11384462

[14] Де Висенте, Хуан; Ланкарес, Хуан; Гермида, Роман (2003). «Размещение методом термодинамического отжига». Физика Буквы A . 317 (5–6): 415–423. Bibcode : 2003PhLA..317..415D . DOI : 10.1016 / j.physleta.2003.08.070 .

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

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

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

[1]