Главная arrow Поиск arrow Эмуляциия отжига
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Поиск с эмуляцией отжига Печать

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

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

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

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

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

Алгоритм поиска с эмуляцией отжига, который представляет собой одну из версий алгоритма стохастического поиска с восхождением к вершине, в которой разрешены некоторые ходы вниз. Ходы вниз принимаются к исполнению с большей вероятностью на ранних этапах выполнения графика отжига, а затем, по мере того как проходит время, выполняются менее часто. Входной параметр schedule определяет значение температуры Г как функции от времени


function Simulated-Annealing(problem, schedule) returns состояние
  решения
  inputs: problem, задача
    schedule, отображение между временем и "температурой"
  local variables: current, узел
    next, узел
    T, "температура", от которой зависит вероятность
    шагов вниз
  current <— Make-Node(Initial-State[problem])
  for t <— 1 to oo do
    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