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


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

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

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

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

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

обзор

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

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

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

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

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

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

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

Приемочные вероятности

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

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

В исходном описании моделируемого отжига, вероятность была равна 1 , когда -ie, процедура всегда перемещается вниз по склону , когда он нашел способ сделать это, независимо от температуры. Многие описания и реализации моделируемого отжига до сих пор принимают это условие как часть определения метода. Однако это условие не является существенным для метода работы.

Функция обычно выбирается так, чтобы вероятность принятия хода уменьшается , когда разница увеличивается, то есть небольшие двигается в горе, более вероятно , чем крупные. Однако, это требование не является строго необходимым, при условии , что указанное выше требование.

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

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

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

Быстро
Медленный

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

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

ПСЕВДОКОД

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

  • Пусть S = s 0
  • Для к = 0 через K макс (эксклюзив):
    • Т ← температура ( K / K макс )
    • Выберите случайный сосед, S нового ← сосед ( ы )
    • Если Р ( Е ( ы ), Е ( с новым ), Т ) ≥ случайных (0, 1) :
      • ss новый
  • Выход: конечное состояние с

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

Для того чтобы применить моделируемый метод отжига к конкретной задаче, необходимо указать следующие параметры: пространство состояний, функция энергии (цель) Е () , кандидат генератора процедура сосед () , функция вероятности приема Р () , и графики отжига температура () и начальная температура <инициализации Темпа>. Эти решения могут оказать существенное влияние на эффективность метода. К сожалению, нет выбора этих параметров , которые будут хороши для всех проблем, и нет общего способа , чтобы найти лучший выбор для данной задачи. В следующих разделах приводятся некоторые общие рекомендации.

Имитации отжига может быть смоделирована как блуждания по поиску графа, вершинами которого являются все возможные состояния, а ребра являются кандидатами движется. Существенное требование для соседа () функции является то , что она должна обеспечивать достаточно короткий путь на этот график из начального состояния любого государства , которое может быть глобальной оптимальным - диаметр поиска графа должен быть малы. В передвижном примере коммивояжера выше, например, пространство поиска для п = 20 городов имеет п! = 2,432,902,008,176,640,000 (2,4 квинтильонов) состояния; пока функция сосед генератор , который обменивает два города подряд может получить из любого состояния (тур) в любое другое состояние в в большинстве этапов.

Переходные вероятности

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

Приемочные вероятности

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

При разработке методы Киркпатрик и др., Функция вероятности приема была определена как 1 , если , и в противном случае. Эта формула была поверхностно оправдано по аналогии с переходами физической системы; она соответствует алгоритму Метрополиса-Гастингса , в случае , когда Т = 1 и распределение предложение Метрополис → Гастингс является симметричным. Тем не менее, эта вероятность приема часто используется для имитации отжига , даже если сосед () функция, которая аналогична распределению предложений в Метрополисе-Hastings, не является симметричной, или нет вероятностного вообще. В результате переходные вероятности алгоритма имитации отжига не соответствуют переходам аналогичной физической системы, а также долгосрочного распределения состояний при постоянной температуре не должна иметь никакого сходства с термодинамического равновесного распределения по состояниям , что физическая система, при любой температуре. Тем не менее, большинство описаний имитации отжига предполагают первоначальную функцию приема, которая , вероятно , трудно закодированный во многих реализациях SA.

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

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

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

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

избегание Барьер

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

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

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

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

Перезапуск

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

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

  • Взаимодействуя Метрополис-Hasting алгоритмы (ака Последовательная Монте - Карло ) в сочетании имитации отжига движется с приемочным-отказ от наиболее приспособленных особей , оснащенных взаимодействующего механизмом рециркуляции.
  • Квантовый отжига использует так называемые «квантовые флуктуации» вместо тепловых колебаний , чтобы получить за счет высоких , но тонких барьеров в целевой функции.
  • Стохастический туннелирования попытки преодолеть возрастающие трудности смоделированных трассы отжига имеют в побеге из локальных минимумов при понижении температуры, с помощью «туннелирования» через барьеры.
  • Поиск Табу обычно перемещается в соседние страны с более низкой энергией, но будет принимать в горе двигается , когда он считает себя застряла в локальном минимуме; и позволяет избежать циклов, сохраняя «табу список» решений уже видели.
  • Эволюция Двухфазная представляет собой семейство алгоритмов и процессов (к которому принадлежит имитации отжиг) , которые опосредуют между локальным и глобальным поиском за счетом использования фазовых изменений в пространстве поиска.
  • Реактивная поисковая оптимизация фокусируется на сочетание машинного обучения с оптимизацией, путем добавления внутреннего контура обратной связи для самостоятельного мелодии свободных параметров алгоритма к характеристикам задачи, в частности, и местной ситуация вокруг текущим решения.
  • Стохастический градиентный спуск проходит много жадных поисков из случайных начальных местоположений.
  • Генетические алгоритмы поддержания пула решений , а не только один. Новые решения кандидатов формируются не только «мутация» (как в SA), но и «рекомбинация» двух решений из пула. Вероятностные критерии, аналогичные тем , которые используются в SA, используются для выбора кандидатов на мутации или комбинации, а также для отбрасывания лишних решений из пула.
  • Закончил оптимизация digressively «сглаживает» целевую функцию при оптимизации.
  • Ant оптимизация колонии (ACO) использует много муравьев (или агентов) , чтобы пересечь пространство решений и найти локально продуктивные районы.
  • Метод кросс-энтропии (СЕ) генерирует решения кандидатов с помощью параметризованного распределения вероятностей. Параметры обновляются с помощью кросс-энтропии минимизации, так, чтобы генерировать лучшие образцы в следующей итерации.
  • Гармония поиск подражает музыканты в процессе импровизации , где каждый музыкант играет ноту найти лучшую гармонию все вместе.
  • Стохастический оптимизация является зонтичным набором методов , который включает имитацию отжига и многочисленные другие подходы.
  • Оптимизация роя частиц представляет собой алгоритм , по образцу роя интеллекта , который находит решение задачи оптимизации в пространстве поиска, или модели и прогнозировать социальное поведение в присутствии целей.
  • Алгоритм бегуна-корень (АСР) является мета-эвристического алгоритма оптимизации для решения унимодальных и мультимодальных проблемы, вдохновленные бегунов и корней растений в природе.
  • Интеллектуальная капли воды алгоритма (МЖД) , который имитирует поведение естественной капли воды , чтобы решить проблемы оптимизации
  • Параллельный темперирования является моделированием модельных копий при различных температурах (или гамильтонианах ) , чтобы преодолеть потенциальные барьеры.

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

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

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

внешняя ссылка