Поиск с эмуляцией отжига
Для любого алгоритма с восхождением к вершине, который никогда не выполняет движения "вниз по склону", к состояниям с более низкой оценкой (или более высокой стоимостью), гарантируется, что он окажется неполным, поскольку такой алгоритм всегда способен зайти в тупик, достигнув локального максимума. В отличие от этого алгоритм с чисто случайным блужданием (т.е. с перемещением к преемнику, выбираемому на равных правах случайным образом из множества преемников) является полным, но чрезвычайно неэффективным. Поэтому представляется разумной попытка скомбинировать каким-то образом восхождение к вершине со случайным блужданием, что позволит обеспечить и эффективность, и полноту. Алгоритмом такого типа является алгоритм с эмуляцией отжига. В металлургии отжигом называется процесс, применяемый для отпуска металла и стекла путем нагревания этих материалов до высокой температуры, а затем постепенного охлаждения, что позволяет перевести обрабатываемый материал в низкоэнергетическое кристаллическое состояние. Чтобы понять суть эмуляции отжига, переведем наше внимание с восхождения к вершине на градиентный спуск (т.е. минимизацию стоимости) и представим себе, что наше задание — загнать теннисный шарик в самую глубокую лунку на неровной поверхности. Если бы мы просто позволили шарику катиться по этой поверхности, то он застрял бы в одном из локальных минимумов. А встряхивая поверхность, можно вытолкнуть шарик из локального минимума. Весь секрет состоит в том, что поверхность нужно трясти достаточно сильно, чтобы шарик можно было вытолкнуть из локальных минимумов, но не настолько сильно, чтобы он вылетел из глобального минимума. Процесс поиска решения с эмуляцией отжига заключается в том, что вначале происходит интенсивное встряхивание (аналогичное нагреву до высокой температуры), после чего интенсивность встряхивания постепенно уменьшается (что можно сравнить с понижением температуры).
Самый внутренний цикл алгоритма с эмуляцией отжига (листинг 4.3) полностью аналогичен циклу алгоритма с восхождением к вершине, но в нем вместо наилучшего хода выполняется случайно выбранный ход. Если этот ход улучшает ситуацию, то всегда принимается. В противном случае алгоритм принимает данный ход с некоторой вероятностью, меньшей 1. Эта вероятность уменьшается экспоненциально с "ухудшением" хода—в зависимости от величины АЕ, на которую ухудшается его оценка. Кроме того, вероятность уменьшается по мере снижения "температуры" т. "плохие" ходы скорее всего могут быть разрешены в начале, когда температура высока, но становятся менее вероятными по мере снижения Т. Можно доказать, что если в графике schedule предусмотрено достаточно медленное снижение Т, то данный алгоритм позволяет найти глобальный оптимум с вероятностью, приближающейся к 1.
На первых порах, в начале 1980-х годов, поиск с эмуляцией отжига широко использовался для решения задач компоновки СБИС. Кроме того, этот алгоритм нашел широкое применение при решении задач планирования производства и других крупномасштабных задач оптимизации. В упр. 4.16 предлагается сравнить его производительность с производительностью поиска с восхождением к вершине и перезапуском случайным образом при решении задачи с п ферзями.
Листинг 4.3. Алгоритм поиска с эмуляцией отжига, который представляет собой одну из версий алгоритма стохастического поиска с восхождением к вершине, в которой разрешены некоторые ходы вниз. Ходы вниз принимаются к исполнению с большей вероятностью на ранних этапах выполнения графика отжига, а затем, по мере того как проходит время, выполняются менее часто. Входной параметр schedule определяет значение температуры Г как функции от времени
function Simulated-Annealing{problem, schedule) returns состояние решения inputs: problem, задача
schedule, отображение между временем и "температурой" local variables: current, узел next, узел
Т, "температура", от которой зависит вероятность шагов вниз
current
T <- schedule[ t]
if T = 0 then return current
next <— случайно выбранный преемник состояния current АЕ <— Value[next] - Value[current] if AE > 0 then current <— next
else current <— next с вероятностью только eAE/T