Введение
Вероятностная техника оптимизации и метаэвристика
Симулированный отжиг (SA) – это вероятностная техника для приближенного нахождения глобального оптимума заданной функции. В частности, это метаэвристика для приближенного решения задачи глобальной оптимизации в большом пространстве поиска. При большом количестве локальных оптимумов SA способен находить глобальный оптимум. Он часто используется, когда пространство поиска дискретно (например, задача коммивояжера, задача выполнимости булевых формул, предсказание структуры белка и планирование задач в цехе). Для задач, где нахождение приблизительного глобального оптимума важнее, чем нахождение точного локального оптимума за фиксированное время, симулированный отжиг может быть предпочтительнее точных алгоритмов, таких как метод градиентного спуска или метод ветвей и границ. Название алгоритма происходит от процесса отжига в металлургии – техники, включающей нагрев и контролируемое охлаждение материала для изменения его физических свойств. Оба эти атрибута материала зависят от его термодинамической свободной энергии. Нагрев и охлаждение материала влияют как на температуру, так и на термодинамическую свободную энергию, или энергию Гиббса. Симулированный отжиг может применяться для решения очень сложных вычислительных задач оптимизации, где точные алгоритмы оказываются неэффективными; хотя он обычно достигает лишь приближенного решения глобального минимума, этого может быть достаточно для многих практических задач. Задачи, решаемые с помощью SA, обычно формулируются как целевая функция множества переменных с учетом ряда математических ограничений. На практике ограничения могут быть включены в целевую функцию в виде штрафных санкций. Аналогичные методы были независимо разработаны несколько раз, в том числе Pincus (1970), Khachaturyan et al. (1979, 1981), Kirkpatrick, Gelatt и Vecchi (1983) и Cerny (1985). В 1983 году этот подход был использован Kirkpatrick, Gelatt Jr., Vecchi, или методом стохастической выборки. Метод является адаптацией алгоритма Метрополиса – Хестингса, метода Монте-Карло для генерации выборочных состояний термодинамической системы, опубликованного N. Metropolis et al. в 1953 году.
Обзор
Состояние s некоторых физических систем и функция E(s), которую необходимо минимизировать, аналогично внутренней энергии системы в данном состоянии. Задача состоит в том, чтобы перевести систему из произвольного начального состояния в состояние с минимально возможной энергией.
Основная итерация
На каждом шаге эвристика имитации отжига рассматривает некоторое соседнее состояние s* текущего состояния s и с определенной вероятностью решает, перейти в состояние s* или остаться в состоянии s. Эти вероятности в конечном итоге направляют систему к состояниям с меньшей энергией. Как правило, этот шаг повторяется до тех пор, пока система не достигнет состояния, достаточно хорошего для решения задачи, или пока не будет исчерпан выделенный вычислительный ресурс.
Соседи государства
Оптимизация решения включает в себя оценку соседних состояний, которые являются новыми состояниями, полученными путем небольшого изменения текущего состояния. Например, в задаче коммивояжера каждое состояние обычно определяется как перестановка городов, которые необходимо посетить, а соседние состояния – это набор перестановок, полученных путем обмена любых двух городов. Четко определенный способ изменения состояния для получения соседнего состояния называется "ходом", и различные ходы приводят к разным наборам соседних состояний. Эти ходы обычно приводят к минимальным изменениям текущего состояния, чтобы постепенно улучшить решение путем итеративного улучшения его частей (например, связей между городами в задаче коммивояжера). Простые эвристики, такие как метод восхождения на холм, которые перемещаются от лучшего соседа к лучшему и останавливаются, когда достигнут решения, у которого нет лучших соседей, не могут гарантировать нахождение какого-либо из существующих оптимальных решений. Их результат может оказаться лишь локальным оптимумом, в то время как истинное оптимальное решение будет глобальным оптимумом, который может отличаться. Метаэвристики используют соседние состояния для исследования пространства решений, и хотя они предпочитают переходить к лучшим соседям, они также принимают и худшие, чтобы избежать застревания в локальных оптимумах; при достаточно длительном времени работы они могут найти глобальный оптимум.
График отжига
Название и вдохновение алгоритма требуют включения интересной особенности, связанной с изменением температуры, в его рабочие характеристики. Это подразумевает постепенное снижение температуры в процессе моделирования. Алгоритм изначально запускается со значением , установленным на большое число (или бесконечность), которое затем уменьшается на каждом шаге в соответствии с графиком отжига – он может быть задан пользователем, но должен завершиться к концу выделенного временного бюджета. Таким образом, предполагается, что система сначала будет исследовать широкую область пространства поиска, содержащую хорошие решения, игнорируя незначительные особенности энергетической функции; затем постепенно перемещаться к областям с низкой энергией, которые становятся все более узкими, и, наконец, двигаться вниз по склону, следуя эвристике наискорейшего спуска. Для любой конечной задачи вероятность того, что алгоритм имитации отжига завершится на глобально оптимальном решении, стремится к 1 при увеличении длительности графика отжига. Однако этот теоретический результат не является особо полезным, поскольку время, необходимое для обеспечения значительной вероятности успеха, обычно превышает время, требуемое для полного перебора пространства решений.
Выбор параметров
Для того, чтобы применить метод имитации отжига к конкретной задаче, необходимо определить следующие параметры: пространство состояний, функцию энергии (цели), процедуру генерации кандидатов, функцию вероятности принятия и расписание отжига, А ТАКЖЕ начальную температуру. Выбор этих параметров может существенно повлиять на эффективность метода. К сожалению, не существует набора параметров, который был бы оптимальным для всех задач, и нет универсального способа найти наилучшие параметры для конкретной задачи. В следующих разделах приводятся некоторые общие рекомендации.
Достаточно близкий сосед
Моделированное отжигание можно представить как случайное блуждание по графу поиска, вершины которого соответствуют всем возможным состояниям, а ребра – возможным переходам между состояниями. Важным требованием к функции является то, что она должна обеспечивать достаточно короткий путь на этом графе от начального состояния к любому состоянию, которое может быть глобальным оптимумом; диаметр графа поиска должен быть небольшим. В примере с задачей коммивояжера, приведенном выше, пространство поиска для n = 20 городов содержит n! = 2 432 902 008 176 640 000 (2,4 квинтиллиона) состояний; однако число соседей каждой вершины равно ребрам (выбираемым из n по 2), а диаметр графа равен .
Вероятности перехода
Для исследования поведения моделируемого отжига применительно к конкретной задаче, может быть полезно рассмотреть вероятности перехода, возникающие в результате различных решений, принятых при реализации алгоритма. Для каждого ребра графа поиска вероятность перехода определяется как вероятность того, что алгоритм моделируемого отжига перейдет в состояние *s'* при текущем состоянии *s*. Эта вероятность зависит от текущей температуры, определяемой функцией *T*, от порядка генерации возможных переходов функцией *neighbor_function*, и от функции вероятности принятия (следует отметить, что вероятность перехода не равна *P(s'|s)*, поскольку кандидаты проверяются последовательно).
Вероятность принятия
Спецификация , , и частично избыточна. На практике часто используют одну и ту же функцию принятия для многих задач, подстраивая две другие функции под конкретную задачу. В оригинальной формулировке метода Киркпатриком и др. функция вероятности принятия определялась как 1, если , и 0 в противном случае. Эта формула была поверхностно обоснована аналогией с переходами в физической системе и соответствует алгоритму Метрополиса — Хэстингса при T=1 и симметричном предложении распределения в алгоритме Метрополиса — Хэстингса. Однако эта вероятность принятия часто применяется в имитационном отжиге, даже когда функция, аналогичная предложению распределения в Метрополисе — Хэстингсе, не является симметричной или вообще не является вероятностной. В результате, вероятности переходов в алгоритме имитационного отжига не соответствуют переходам в аналогичной физической системе, и долгосрочное распределение состояний при постоянной температуре не обязано иметь сходство с распределением термодинамического равновесия состояний этой физической системы при любой температуре. Тем не менее, большинство описаний имитационного отжига исходят из исходной функции принятия, которая, вероятно, жестко запрограммирована во многих реализациях SA. В 1990 году Москато и Фонтанари, а независимо от них Дьюк и Шейер, предложили, что детерминированное обновление (то есть не основанное на вероятностном правиле принятия) может ускорить процесс оптимизации, не влияя на конечное качество. Москато и Фонтанари, наблюдая аналогичную кривую "удельной теплоемкости" отжига с "пороговым обновлением", полученную в их исследовании, пришли к выводу, что "стохастичность обновления Метрополиса в алгоритме имитационного отжига не играет существенной роли в поиске минимумов, близких к оптимальным". Вместо этого они предположили, что "сглаживание ландшафта функции стоимости при высокой температуре и постепенное определение минимумов в процессе охлаждения являются ключевыми факторами успеха имитационного отжига". Впоследствии метод получил распространение под названием "принятие порога" благодаря термину, предложенному Дьюком и Шейером. В 2001 году Франц, Хоффман и Саломон показали, что детерминированная стратегия обновления действительно является оптимальной в широком классе алгоритмов, моделирующих случайное блуждание по ландшафту стоимости/энергии.
Эффективное формирование кандидатов
При выборе генератора кандидатов необходимо учитывать, что после нескольких итераций алгоритма имитации отжига текущее состояние, как ожидается, будет иметь значительно более низкую энергию, чем случайное состояние. Поэтому, как общее правило, генератор следует ориентировать на кандидаты, для которых энергия целевого состояния, вероятно, будет близка к энергии текущего состояния. Эта эвристика (являющаяся основным принципом алгоритма Метрополиса — Хестингса) склонна исключать как очень хорошие, так и очень плохие ходы-кандидаты; однако первые обычно встречаются гораздо реже, чем вторые, поэтому эвристика, как правило, достаточно эффективна. Например, в задаче о коммивояжере, ожидается, что перестановка двух последовательных городов в маршруте с низкой энергией (длиной) окажет умеренное влияние на его энергию (длину); в то время как перестановка двух произвольных городов гораздо вероятнее увеличит его длину, чем уменьшит. Таким образом, генератор соседних перестановок, основанный на последовательных обменах, должен работать лучше, чем генератор, основанный на произвольных обменах, хотя последний может обеспечить несколько более короткий путь к оптимуму (с обменами вместо ). Более точное выражение эвристики заключается в том, что следует пробовать первые состояния-кандидаты, для которых велико. Для "стандартной" функции принятия, указанной выше, это означает, что находится в пределах или меньше. Таким образом, в примере с коммивояжером можно использовать функцию, которая переставляет два случайных города, где вероятность выбора пары городов стремится к нулю при увеличении расстояния между ними более чем на .
Предотвращение барьеров
При выборе генератора кандидатов необходимо также попытаться уменьшить количество "глубоких" локальных минимумов – состояний (или наборов связанных состояний), энергия которых значительно ниже, чем у всех соседних состояний. Такие "замкнутые области притяжения" энергетической функции могут "застревать" алгоритм имитации отжига с высокой вероятностью (примерно пропорциональной числу состояний в области) и на очень длительное время (примерно экспоненциально зависящее от разницы энергий между окружающими состояниями и дном области). Как правило, невозможно создать генератор кандидатов, который бы одновременно удовлетворял этой цели и отдавал приоритет кандидатам с близкой энергией. С другой стороны, часто можно существенно повысить эффективность имитации отжига, внеся относительно простые изменения в генератор. Например, в задаче коммивояжера легко найти два маршрута, , с почти одинаковой длиной, таких что (1) является оптимальным, (2) любая последовательность обменов пар городов, преобразующая в , проходит через маршруты, значительно превышающие по длине оба маршрута, и (3) можно преобразовать в , просто перевернув порядок следования некоторого набора последовательных городов. В этом примере и оказываются в разных "глубоких областях притяжения", если генератор выполняет только случайные обмены пар городов, но попадут в одну и ту же область, если генератор выполняет случайное переворачивание сегментов.
График охлаждения
Физическая аналогия, используемая для обоснования моделируемого отжига, предполагает, что скорость охлаждения достаточно низкая, чтобы вероятностное распределение текущего состояния оставалось близким к термодинамическому равновесию в любой момент времени. К сожалению, время релаксации – время, необходимое для восстановления равновесия после изменения температуры – сильно зависит от "топографии" энергетической функции и текущей температуры. В алгоритме моделируемого отжига время релаксации также сложным образом зависит от генератора кандидатов. Важно отметить, что все эти параметры обычно предоставляются алгоритму моделируемого отжига в виде "черных ящиков". Поэтому идеальную скорость охлаждения невозможно определить заранее, и ее следует эмпирически подбирать для каждой задачи. Адаптивные алгоритмы моделируемого отжига решают эту проблему, связывая график охлаждения с ходом поиска. Другие адаптивные подходы, такие как термодинамический моделируемый отжиг, автоматически регулируют температуру на каждом шаге, основываясь на разнице энергий между двумя состояниями в соответствии с законами термодинамики.
Перезапуск
Иногда предпочтительнее вернуться к решению, которое было значительно лучше, чем постоянно двигаться от текущего состояния. Этот процесс называется перезапуском имитированного отжига. Для этого значения s и e устанавливаются равными sbest и ebest, и, возможно, перезапускается график отжига. Решение о перезапуске может основываться на нескольких критериях. Среди них – перезапуск после фиксированного числа шагов, перезапуск, если текущая энергия слишком высока по сравнению с наилучшей энергией, достигнутой на данный момент, случайный перезапуск и другие.