Как моделируется процесс отжига Работ

Контур алгоритма

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

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

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

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

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

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

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

    • @acceptancesa (по умолчанию) - Моделируемая функция приемки отжига. Вероятность принятия:

      11+exp(Δmax(T)),

      где

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

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

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

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

    • @temperatureexp (по умолчанию) - T = T 0 * 0,95 ^ k.

    • @temperaturefastT = <reservedrangesplaceholder1> 0 / k.

    • @temperatureboltz - T = T 0/log (k).

    • @myfun - Пользовательская функция температуры, myfun. Синтаксис пользовательской функции температуры см. в разделе «Опции температуры».

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

    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] Ингбер, Л. Адаптивный моделируемый отжиг (ASA): Извлеченные уроки. Приглашен в специальный выпуск Польского журнала «Контроль и кибернетика» по теме «Моделируемый отжиг, применяемый к комбинаторной оптимизации». 1995. Доступно от https://www.ingber.com/asa96_lessons.ps.gz

См. также

Похожие темы

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