Как моделируемые работы отжига

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

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

  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. Переотжиг устанавливает параметры отжига на нижние значения, чем номер итерации, таким образом повышая температуру в каждой размерности. Параметры отжига зависят от значений предполагаемых градиентов целевой функции в каждой размерности. Основная формула

    ki=журнал(T0Timax j(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. Доступный от http://www.ingber.com/asa96_lessons.ps.gz

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте