Алгоритм Метрополиса
Метрополис и др. доказали, что их моделирующий алгоритм обладает следу- ющим свойством (чтобы не отвлекаться надолго, мы опускаем доказательство; на самом деле оно является прямым следствием некоторых базовых свойств случай- ных блужданий):
(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 повышающие перемещения почти никогда не принимаются и алгоритм Метрополиса ведет себя практически идентично градиентному спуску.
Еще по теме Алгоритм Метрополиса:
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- Алгоритм исцеления:
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- 2. Специфика и алгоритмы работы с источниками.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
- ЗАДАЧА: РЕШЕНИЕ
- Переживание