Моделируемый алгоритм отжига выполняет следующие шаги:
Алгоритм генерирует случайную пробную точку. Алгоритм выбирает расстояние пробной точки от текущей точки по распределению вероятностей со шкалой, зависящей от текущей температуры. Распределение пробных точек задается как функция с помощью AnnealingFcn вариант. Варианты:
@annealingfast (по умолчанию) - длина шага равна текущей температуре, а направление равномерно случайное.
@annealingboltz - Длина шага равна квадратному корню температуры, и направление равномерно случайное.
@myfun - Пользовательский алгоритм отжига, myfun. Синтаксис пользовательской функции отжига см. в разделе Настройки алгоритма.
После генерации пробной точки алгоритм сдвигает ее, при необходимости, чтобы оставаться в пределах границ. Алгоритм сдвигает каждую неосуществимую составляющую пробной точки на значение, выбираемое равномерно случайным образом между нарушенной границей и (осуществимым) значением при предыдущей итерации.
Алгоритм определяет, лучше или хуже новая точка, чем текущая. Если новая точка лучше текущей, она становится следующей точкой. Если новая точка хуже текущей, алгоритм может сделать ее следующей точкой. Алгоритм принимает худшую точку на основе приемочной функции. Выберите функцию приемки с помощью AcceptanceFcn вариант. Варианты:
@acceptancesa (по умолчанию) - Функция приемки моделирования отжига. Вероятность принятия -
)),
где
Δ = новая цель - старая цель.
T0 = начальная температура компонента i
T = текущая температура.
Поскольку Δ и T положительны, вероятность принятия находится в диапазоне от 0 до 1/2. Меньшая температура приводит к меньшей вероятности принятия. Кроме того, большее Δ приводит к меньшей вероятности принятия.
@myfun - Пользовательская функция приемки, myfun. Дополнительные сведения о синтаксисе пользовательских функций приемки см. в разделе Настройки алгоритма.
Алгоритм систематически понижает температуру, сохраняя наилучшую точку, найденную до сих пор. TemperatureFcn определяет функцию, используемую алгоритмом для обновления температуры. Пусть k обозначает параметр отжига. (Параметр отжига совпадает с номером итерации до повторного отжига.) Опции:
@temperatureexp (по умолчанию) - T = T0 * 0,95 ^ k.
@temperaturefast - Т = T0/к.
@temperatureboltz - T = T0/log (k).
@myfun - Пользовательская температурная функция, myfun. Синтаксис пользовательской температурной функции см. в разделе Параметры температуры.
simulannealbnd заново отжигает после того, как принимает ReannealInterval точки. Повторный отжиг устанавливает параметры отжига на более низкие значения, чем номер итерации, таким образом повышая температуру в каждом измерении. Параметры отжига зависят от значений расчетных градиентов целевой функции в каждом измерении. Основная формула:
si),
где
ki = параметр отжига для компонента i.
T0 = начальная температура компонента i.
Ti = текущая температура компонента i.
si = градиент цели в направлении i раз разность границ в направлении i.
simulannealbnd защищает значения параметров отжига от Inf и другие ненадлежащие ценности.
Алгоритм останавливается, когда среднее изменение целевой функции невелико относительно 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