Имитация отжига - Simulated annealing

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

Задача коммивояжера в 3D для 120 точек решена с имитацией отжига.

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

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

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

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

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

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

Обзор

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

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

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

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

Псевдокод

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

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

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

Достаточно рядом с соседом

Имитация отжига может быть смоделирована как случайное блуждание по поисковому графу, вершины которого являются всеми возможными состояниями, а ребра - возможными перемещениями. Существенным требованием к 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 Р (е, е ', Т)}$

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

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

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

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

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

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

В приведенной выше задаче коммивояжера, например, ожидается , что обмен местами двух последовательных городов в поездке с низким энергопотреблением будет иметь умеренное влияние на его энергию (продолжительность); тогда как обмен местами двух произвольных городов с большей вероятностью увеличит его длину, чем уменьшит. Таким образом, ожидается, что генератор соседей с последовательной заменой будет работать лучше, чем генератор с произвольной заменой, даже если последний может обеспечить несколько более короткий путь к оптимуму (с заменой вместо ). ${\ displaystyle n-1}$${\ Displaystyle п (п-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}$

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

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

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

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

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

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

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

использованная литература

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

• А. Дас и Б.К. Чакрабарти (ред.), Квантовый отжиг и связанные с ним методы оптимизации , Лекция по физике, 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] Многоцелевой алгоритм оптимизации на основе моделирования отжига: AMOSA.