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

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

Отжиг — это металлургический метод получения кристаллизованных твердых тел без стеклования. Как только металл расплавится, температуру постепенно снижают, пока он не достигнет твердого состояния. Чтобы удалить все дефекты, металл нагревают, а затем охлаждают с понижением температуры, пока он не достигнет стабильного состояния.

Эта система нисходящих уровней породила алгоритм Метрополиса 1953 года, а затем имитацию отжига IBM в 1983 году.

Представление алгоритма

Таким образом, алгоритм имитации отжига или имитация отжига для англоговорящих является адаптацией алгоритмический процесса отжига.

Цель состоит в том, чтобы достичь устойчивого состояния целевой функции — локального или глобального оптимума — из случайного решения. Это состояние достигается поэтапно, когда принятие мутации зависит от «температуры» стадии.

Алгоритм имитации отжига последовательно генерирует конфигурации из начального решения R0 и начальная температура T0 уменьшаясь с каждой итерацией, до получения стабильной конфигурации. Вероятность принятия новой конфигурации (правило Метрополиса):

  • 1, если конфигурация улучшает целевую функцию;
  • exp(diff(E)/T), где diff(E) — разность энергий, а T — температура; разность энергий является внутренней функцией, зависящей от целевой функции.

Поток алгоритма

Алгоритм отжига следующий:

  1. Возьмем начальное решение R=R0 и начальная температура T=T0. Исходное состояние такое же, как и для точных методов, полученное эвристический (скоростная или прожорливая).
  2. Сгенерировать случайное решение R(я+1) в окрестности текущего решения:
    1. сравнить R(я+1) с Ря по правилу Метрополиса
    2. повторять до тех пор, пока не будет найдено устойчивое решение (или после определенного количества итераций)
  3. Уменьшите температуру T до пороговой температуры Tминили иметь устойчивое решение.
 р0
Т0
так долго как Т > Тмин и Э > еМаксимум
   р(я+1) = сосед (Rя)
   если Э(Р(я+1)) < Е(Rя) Где случайный () < P (разница (E) / T) тогда
      принять Р(я+1)
   обновить Т
возвращаться рнет

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

Поскольку T вначале велико, можно выбрать множество решений, ухудшающих текущее решение. Это позволяет уйти от локального оптимума. На следующем рисунке показано значение целевой функции как функция вектора параметров X. Таким образом, температура позволяет «перепрыгивать» менее «хорошие» области, чтобы выбраться из «долины». Шары и сигналы на следующем рисунке показывают, как высоко могут «прыгать» шары, то есть допуск отрицательного отклонения целевой функции при получении нового решения.

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

Если температура низкая, выйти из локального оптимума труднее:

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

Делиться
ru_RURU
%d такие блоггеры, как: