Лекция: Алгоритм отжига.

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

В этом разделе мы рассмотрим метод оптимизации, который называется отжигом, или симуляцией восстановления(Simulated annealing). Как ясно из названия, метод по­иска моделирует процесс восстановления. Восстановление — это физический про­цесс, который заключается в нагреве и последующем контролируемом охлажде­нии субстанции. В результате получается прочная кристаллическая структура, которая отличается от структуры с дефектами, образующейся при быстром бес­порядочном охлаждении. Структура здесь представляет собой кодированное ре­шение, температура используется для. того, чтобы указать, как и когда будут приниматься новые решения.

Чтобы понять суть эмуляции отжига, переведем наше внимание с восхождения к вершине на градиентный спуск (т.е. минимизацию стоимости) и представим себе, что наше задание — загнать теннисный шарик в самую глубокую лунку на неровной поверхности. Если бы мы просто позволили шарику катиться по этой поверхности, то он застрял бы в одном из локальных минимумов. А встряхивая поверхность, можно вытолкнуть шарик из локального минимума. Весь секрет состо­ит в том, что поверхность нужно трясти достаточно сильно, чтобы шарик можно бы­ло вытолкнуть из локальных минимумов, но не настолько сильно, чтобы он вылетел из глобального минимума. Процесс поиска решения с эмуляцией отжига заключает­ся в том, что вначале происходит интенсивное встряхивание, которое в алгоритме соответствует нагреву до высокой температуры, после чего интенсивность встряхивания постепенно уменьшается, что в алгоритме моделируется понижением температуры.

Самый внутренний цикл алгоритма с эмуляцией отжига (рис. 10.31) полностью аналогичен циклу алгоритма с восхождением к вершине, но в нем вместо наилучшего хо­да выполняется случайно выбранный ход. Если этот ход улучшает ситуацию, то всегда принимается. В противном случае алгоритм принимает данный ход с некоторой вероят­ностью, меньшей 1. Эта вероятность уменьшается экспоненциально с «ухудшением» хо­да — в зависимости от величины DE, на которую ухудшается его оценка. Кроме того, эта ве­роятность уменьшается по мере снижения «температуры» Т т.е.. «плохие» ходы скорее всего могут быть разрешены в начале, когда температура высока, но становятся менее вероят­ными по мере снижения Т.

На первых порах, в начале 1980-х годов, поиск с эмуляцией отжига широко ис­пользовался для решения задач компоновки СБИС. Кроме того, этот алгоритм на­шел широкое применение при решении задач планирования производства и других крупномасштабных задач оптимизации.

Рисунок 10.31. Алгоритм поиска с эмуляцией отжига, который представляет собой одну из версий алгоритма стохастического поиска с восхождением к вершине, в которой разрешены некоторые ходы вниз.