Как симулированные работы отжига

Схема алгоритма

Симулированный алгоритм отжига выполняет следующие шаги:

  1. Алгоритм генерирует случайную испытательную точку. Алгоритм выбирает расстояние испытательной точки от текущей точки вероятностным распределением со шкалой в зависимости от текущей температуры. Вы устанавливаете испытательное распределение расстояния точки как функцию с AnnealingFcn опция. Выбор:

    • @annealingfast (значение по умолчанию) — Длина шага равняется текущей температуре, и направление однородно случайно.

    • @annealingboltz — Длина шага равняется квадратному корню из температуры, и направление однородно случайно.

    • @myfun — Пользовательский алгоритм отжига, myfun. Для пользовательского синтаксиса функций отжига смотрите Настройки Алгоритма.

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

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

    • @acceptancesa (значение по умолчанию) — Симулированная приемная функция отжига. Вероятность принятия

      11+exp(Δmax(T)),

      где

      Δ = новая цель – старая цель.
      T 0 = начальная температура i компонента
      T = текущая температура.

      И начиная с Δ и начиная с T положительны, вероятность принятия между 0 и 1/2. Меньшая температура приводит к меньшей приемной вероятности. Кроме того, больший Δ приводит к меньшей приемной вероятности.

    • @myfun — Пользовательская приемная функция, myfun. Для пользовательского приемного синтаксиса функций смотрите Настройки Алгоритма.

  3. Алгоритм систематически понижает температуру, храня лучшую точку, найденную до сих пор. TemperatureFcn опция задает функцию использование алгоритма, чтобы обновить температуру. Позвольте k обозначить параметр отжига. (Параметр отжига совпадает с номером итерации до переотжига. Опции:

    • @temperatureexp (значение по умолчанию) — T = T 0 * 0.95^k.

    • @temperaturefastT = T 0 / k.

    • @temperatureboltzT = T 0 / журнал (k).

    • @myfun — Пользовательская температурная функция, myfun. Для пользовательского температурного синтаксиса функций см. Температурные Опции.

  4. simulannealbnd повторно отжигает после того, как это примет ReannealInterval 'points'. Переотжиг устанавливает параметры отжига на нижние значения, чем номер итерации, таким образом повышая температуру в каждой размерности. Параметры отжига зависят от значений предполагаемых градиентов целевой функции в каждой размерности. Основная формула

    ki=log(T0Timaxj(sj)si),

    где

    ki = отжиг параметра для i компонента.
    T 0 = начальная температура i компонента.
    Ti = текущая температура i компонента.
    si = градиент цели в направлении различие времен i границ в направлении i.

    simulannealbnd охраняет значения параметров отжига против Inf и другие неподходящие значения.

  5. Алгоритм останавливается, когда среднее изменение в целевой функции мало относительно FunctionTolerance, или когда это достигает любого другого критерия остановки. Смотрите Останавливающиеся Условия для Алгоритма.

Для получения дополнительной информации об алгоритме смотрите Ingber [1].

Остановка условий для алгоритма

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

  • FunctionTolerance — Запуски алгоритма до среднего изменения в значении целевой функции в StallIterLim итерации меньше значения FunctionTolerance. Значением по умолчанию является 1e-6.

  • MaxIterations — Алгоритм останавливается, когда количество итераций превышает это максимальное количество итераций. Можно задать максимальное количество итераций как положительное целое число или Inf. Значением по умолчанию является Inf.

  • MaxFunctionEvaluations задает максимальное количество оценок целевой функции. Алгоритм останавливается, если количество вычислений функции превышает значение MaxFunctionEvaluations. Значением по умолчанию является 3000*numberofvariables.

  • MaxTime задает максимальное время в секундах запуски алгоритма перед остановкой. Значением по умолчанию является Inf.

  • ObjectiveLimit — Алгоритм останавливается, когда лучшее значение целевой функции меньше значения ObjectiveLimit. Значением по умолчанию является -Inf.

Библиография

[1] Ingber, L. Адаптивный симулированный отжиг (ASA): Уроки извлечены. Приглашенный доклад к специальному выпуску польского Управления Журналом и Кибернетики на “Симулированном Отжиге, Примененном Комбинаторная Оптимизация”. 1995. Доступный от https://www.ingber.com/asa96_lessons.ps.gz

Смотрите также

Похожие темы