<<
>>

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

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

получите деформированную структуру с множеством дефектов.

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

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

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

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

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

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

12.3.

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

Еще по теме Имитация отжига:

  1. Переговоры с душевнобольными.
  2. 6. БЮРОКРАТИЯ
  3. Первый путь
  4. МОДЕЛИРОВАНИЕ ИЛИ ПОДРАЖАНИЕ?
  5. МЫШЛЕНИЕ ДООПЕРАЦИОНАЛЬНОЕ
  6. 10 приемов воздействия на противника
  7. СИМУЛЯЦИЯ
  8. Задачи и упражнения
  9. 1. Создание видимости одного преступления для сокрытия другого
  10. 3. Содержание дисциплины
  11. Экстремальные морально-психологические факторы:
  12. ШКОЛА ЖЕНЕВСКАЯ
  13. Эволюция типа научно-популярного, познавательного журнала.
  14. Рефлексивное мышление в деятельности юриста.
  15. Теперь можно сесть и почитать и поработать...
  16. 4.1. Понятия «индивид» и «личность». Формирование личности
  17. Метаязык двух слов.
  18. 8.6.1. Замена головы
  19. 4. Формирование коммуникативных навыков