Вопрос 29: Алгоритм имитации отжига

Алгоритм имитации отжига это алгоритм, как и муравьиный алгоритм, относится к вероятностным методам решения. Ключевым моментом в таких подходах является случайный выбор одного из нескольких возможных решений вместо анализа каждого. Это позволяет сократить время счета. Простой перебор для задач, сложность которых растет по показательному или факториальному закону в зависимости от порядка графа, может даже для небольших оказаться недопустимо длительным. Для поставленной задачи необходимо реализовать алгоритм имитации отжига, который представлен ниже:

На входе: минимальная температура $T_{min}$, начальная температура $T_{max}$. $T_{1} = T_{max}$.

Пока $T_{i} > T_{min}$:

• $s_{c} = F(s_{i - 1})$
• $deltaE = E(s_{c}) - E(s_{i - 1}))$
• Если $deltaE <= 0$, тогда $s_{i} = s_{c}$
• Если $deltaE >= 0$ переход осуществляется с вероятностью $P(deltaE) = e^{-deltaE / T_{i}}$
• Понимажем температуру по формуле $T_{i} = T_{max} / ln(i)$

Выбор начального решения

Хорошей стратегий является случайный выбор начального решения. Также в качестве начального решения можно предложить решение полученное другими методами. Это предоставляет алгоритму базу, на основании которой он будет строить более оптимальное решение.

Оценка решения

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

Основной шаг алгоритма

Основной шаг при некоторой температуре повторяется несколько раз. Возможно, что один раз. Также возможен вариант с зависимостью числа повторов от температуры.

Случайное изменение решения

Этот этап сильно зависит от специфики задачи. Однако, изменение стоит производить локальные. Например, для задачи коммивояжера, хорошей стратегий будет обмен, в текущем порядке следования городов, двух случайных городов местами. В результате изменения у нас будет два решения: текущее и измененное.

Критерий допуска

Для определенности будем считать, что оптимизация заключается в ми-нимизации энергии. В большинстве случаев этот подход справедлив. Критерий допуска заключается в проверке и возможной замене текущего решения измененным.

Уменьшение температуры

Важной частью алгоритма является уменьшение температуры. При большой температуре вероятность выбора менее оптимального решения высока. Однако, в процессе работы алгоритма температура снижается, и вероятность выбора менее оптимального решения снижается. Выбор способа уменьшения температуры может быть различным и выбирается экспериментально. Главное, чтобы температура монотонно убывала к нулю. Хорошей стратегий является умножение на каждом шаге температуры на некоторый коэффициент немного меньший единицы.

Выбор начальной и пороговой температуры

Этот выбор тоже следует производить экспериментально. Естественными рекомендациями могут служить выбор пороговой температуры близкой к нулю, а начальной достаточно высокой.