<<
>>

Алгоритм Метрополиса

Метрополис вместе с другими авторами предложил следующий метод пошагово- го моделирования системы при фиксированной температуре T. В любой момент времени модель хранит текущее состояние системы и пытается сгенерировать новое состояние, применяя возмущение к текущему состоянию.
Будем считать, что нас интересуют только состояния системы, «достижимые» из некоторого фик- сированного исходного состояния через последовательность мелких возмущений; предполагается, что множество таких состояний C конечно. За один шаг сначала генерируется небольшое случайное возмущение в текущем состоянии S системы, приводящее к новому состоянию S'. Пусть E(S) и E(S') обозначают энергии S и S' соответственно. Если E(S') < E(S), то текущее состояние заменяется на S'. В против- ном случае пусть ΔE = E(S') - E(S) > 0. Текущее состояние заменяется состоянием S' с вероятностью e-ΔE/(kT), а в противном случае текущим состоянием остается S.

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

(12.2) Обозначим

7- = ∑

Пусть для состояния S запись fS(t) обозначает долю первых t шагов, в которых модель пребывает в состоянии S.

Тогда предел f (t) при стремлении t к ∞, с вероят- ностью, стремящейся к 1, равен ∙ e-E^)/^т\

Именно такой факт нам и нужен; фактически он означает, что модель проводит приблизительно нужное время в каждом состоянии в соответствии с уравнением Гиббса-Больцмана.

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

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

Начать с исходного решения S0, констант к и T За один шаг:

Пусть S - текущее решение

Случайно выбрать S' среди соседей S с равномерным распределением

Если c(S') < c(S)

Обновить S^ S'

Иначе

С вероятностью e~MS')~c(S))/(kT)

Обновить S^ S'

Иначе

Оставить S без изменений

Конец Если

Таким образом, для экземпляра задачи о вершинном покрытии, состоящего из графа-звезды из раздела 12.1 (x1 соединяется с каждым из узлов y1, ..., yn_1), мы видим, что алгоритм Метрополиса быстро выходит из локального минимума, воз- никающего при удалении x: соседнее решение, в котором x1 возвращается обратно, будет сгенерировано и принято с положительной вероятностью. В более сложных графах алгоритм Метрополиса тоже может до некоторой степени исправить не- верные решения, принятые в ходе выполнения.

В то же время алгоритм Метрополиса не всегда ведет себя так, как нужно, при- чем даже в очень простых ситуациях. Вернемся к самому первому из рассмотрен- ных графов — графу G без ребер. Градиентный спуск решает этот экземпляр без всяких проблем, последовательно удаляя узлы, пока не удалит все. Но хотя алго- ритм Метрополиса начинает работать именно так, при приближении к глобальному максимуму он начинает буксовать. Рассмотрим ситуацию, в которой текущее ре- шение содержит только c узлов, где с намного меньше общего количества узлов n. С очень высокой вероятностью соседнее решение, сгенерированное алгоритмом Метрополиса, будет иметь размер c + 1, а не c - 1, и с разумной вероятностью это перемещение вверх будет принято.

Таким образом, по мере работы алгоритма сокращать размер вершинного покрытия становится все труднее и труднее; при приближении к дну воронки начинаются «метания».

Это поведение также проявляется и в более сложных ситуациях, и не столь оче- видными способами; конечно, странно видеть его в таком простом случае. Чтобы понять, как справиться с проблемой, мы вернемся к физической аналогии, зало- женной в основу алгоритма Метрополиса, и спросим: какой смысл имеет параметр температуры в контексте оптимизации?

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Алгоритм Метрополиса:

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. АЛГОРИТМ
  3. АЛГОРИТМ УДАЧИ
  4. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. ЗАДАЧА: РЕШЕНИЕ
  13. Переживание