Документация Engee

Алгоритм имитации отжига

Конструктор

SimulatedAnnealing(; neighbor = default_neighbor!,
                    T = default_temperature,
                    p = kirkpatrick)

Конструктор принимает три ключевых слова:

  • neighbor = a!(x_proposed, x_current), изменяемая функция текущего x и предложенного x

  • T = b(iteration), функция текущей итерации, которая возвращает температуру

  • p = c(f_proposal, f_current, T), функция текущей температуры, текущего значения функции и предлагаемого значения функции, которая возвращает вероятность принятия

Описание

Имитация отжига — это метод оптимизации без производных. Он основан на алгоритме Метрополиса-Гастингса, который первоначально использовался для создания выборок из термодинамической системы и часто применяется для формирования выборов из апостериорного значения при выполнении байесовского вывода. По сути, это вероятностный метод поиска минимума функции часто в достаточно больших областях. По историческим причинам, указанным выше, в алгоритме используются такие термины, как охлаждение, температура и вероятность принятия.

Как видно из конструктора, реализация имитации отжига характеризуется температурой, функцией соседа и вероятностью принятия. Температура контролирует, насколько волатильными могут быть изменения в кандидатах на минимизацию, поскольку она входит в вероятность принятия. Например, исходная функция вероятности принятия Киркпатрика и др. может быть записана следующим образом.

p(f_proposal, f_current, T) = exp(-(f_proposal - f_current)/T)

Высокая температура повышает вероятность принятия выбора, увеличивая вероятность принятия до 1. Как и в алгоритме Метрополиса-Гастингса, мы всегда принимаем меньшее значение функции, но иногда принимаем и большее. По мере снижения температуры мы с большей вероятностью будем принимать только те кандидаты x, которые уменьшают значение функции. Чтобы получить новое значение f_proposal, нам нужна функция соседа. Простая функция соседа добавляет стандартный обычный выбор к каждому измерению x.

function neighbor!(x_proposal::Array, x::Array)
    for i in eachindex(x)
        x_proposal[i] = x[i]+randn()
    end
end

Как видно, разделить роль различных компонентов алгоритма не представляется возможным. Например, как функциональная форма функции принятия, так и температура и (косвенно) функция соседа определяют, будет ли принят следующий выбор x или нет.

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

Пример

Справочные материалы