Алгоритм Метрополиса и имитация отжига - Локальный поиск

Первые идеи улучшенного алгоритма локального поиска были представлены в работе Метрополиса, Розенблата и Теллера (Metropolis, Rosenbluth, Teller, 1953). Они рассматривали задачу моделирования поведения физической системы в соответствии с принципами статистической механики. Базовая модель из этой области подразумевает, что вероятность нахождения физической системы в состоянии с энергией E пропорциональна функции Гиббса-Больцмана e^-E/(kT), где T > 0 — температура, а k > 0 — константа. Присмотримся к этой функции. Для любой температуры Tфункция монотонно убывает по энергии E, поэтому из формулы следует, что физическая система находится в низкоэнергетическом состоянии с большей вероятностью, чем в высокоэнергетическом. Теперь рассмотрим эффект температуры T; при малых T вероятность низкоэнергетического состояния существенно выше вероятности высокоэнергетического состояния. Однако при высокой температуре разность между двумя вероятностями становится очень малой и система почти с равной вероятностью может оказаться в любом состоянии.

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

Метрополис вместе с другими авторами предложил следующий метод пошагового моделирования системы при фиксированной температуре 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) Обозначим

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

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

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

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

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

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

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

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

Ни одна из крайних температур — ни очень низкая, ни очень высокая — не является эффективным методом решения задач минимизации в целом. Этот принцип также проявляется в физических системах: если взять твердое тело и нагреть его до очень высокой температуры, трудно ожидать сохранения стройной кристаллической структуры, даже если она предпочтительна с энергетической точки зрения; и это можно объяснить большим значением кТ в выражении e^-E(S)/(kT), с которым огромное количество менее выгодных состояний становится слишком вероятным. С этой же точки зрения можно рассматривать “метания” алгоритма Метрополиса в простом экземпляре задачи о вершинном покрытии: он пытается найти самое низкое энергетическое состояние при слишком высокой температуре, когда все конкурирующие состояния имеют слишком высокую вероятность. С другой стороны, если взять расплав и очень быстро заморозить его, не стоит также рассчитывать на формирование идеальной кристаллической структуры, скорее вы получите деформированную структуру с множеством дефектов. Дело в том, что при очень малых T мы слишком близко подходим к области градиентного спуска, и система захватывается в одном из многочисленных провалов своей гребенчатой энергетической поверхности. Интересно заметить, что при очень малых T утверждение (12.2) показывает, что в пределе большая часть времени случайных блужданий проводится в низшем энергетическом состоянии. Проблема в том, что случайное блуждание тратит слишком много времени, чтобы хотя бы отдаленно приблизиться к этому пределу.

В начале 1980-х годов ученые изучали связи между минимизацией энергии и комбинаторной оптимизацией. Киркпатрик, Гелатт и Веччи (Kirkpatrick, Gelatt, Vecchi, 1983) размышляли над обсуждаемой темой и задали следующий вопрос: как решить эту задачу для физических систем и какой тип алгоритма предполагает такое решение? В физических системах для перевода материала в кристаллическое состояние используется процесс, называемый отжигом: материал постепенно охлаждается с очень высокой температуры, что дает ему достаточно времени для достижения равновесия на промежуточных убывающих температурах. Таким образом удается избежать энергетических минимумов, с которыми материал сталкивается на всем протяжении процесса охлаждения, и в конечном итоге достичь глобального оптимума.

Этот процесс можно попытаться смоделировать на алгоритмическом уровне; так появился алгоритмический метод, известный как имитация отжига. Метод имитации отжига основан на выполнении алгоритма Метрополиса с постепенным снижением значения T в ходе выполнения. Конкретный способ обновления T называется по естественным причинам планом охлаждения; при его планировании учитывается целый ряд факторов. Формально план охлаждения представляет собой функцию т, отображающую {1, 2, 3, ...} на положительные вещественные числа; на итерации i алгоритма Метрополиса в определении вероятности используется температура T = т(i).

На качественном уровне очевидно, что имитация отжига допускает большие изменения в решении на ранних стадиях его выполнения, при высокой температуре. Затем в процессе поиска температура понижается, чтобы снизить вероятность отмены уже происшедших изменений. Имитация отжига также может рассматриваться как попытка оптимизации альтернативы, следующей из (12.2). Согласно (12.2), значения T, сколь угодно близкие к 0, обеспечивают наивысшую вероятность решений с минимальной стоимостью; однако (12.2) само по себе ничего не говорит о скорости сходимости используемых ей функций f_S(t). Как выясняется, эти функции сходятся намного быстрее для больших значений T; чтобы быстро найти решения с минимальной стоимостью, полезно ускорить сходимость, начав процесс при больших T, с последующим сокращением его для повышения вероятности оптимальных решений. Хотя, насколько нам известно, физические системы достигают минимального энергетического состояния через процесс отжига, метод имитации отжига не предоставляет гарантий нахождения оптимального решения. Чтобы понять, почему это так, рассмотрим ситуацию с двойной воронкой на рис. 12.2. Если две воронки занимают равную площадь, то при высоких температурах система с равной вероятностью может оказаться в любой из двух. При снижении температуры переходы между двумя воронками постоянно усложняются. Нет никаких гарантий, что в конце процесса система окажется на дне более глубокой воронки.

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