Имитация отжига и её применения

Имитация отжига и её применения

Физическая аналогия: медленное охлаждение

В металлургии «отжиг» — нагрев металла до высокой температуры и медленное охлаждение. При высокой температуре атомы имеют много энергии и могут «перепрыгивать» через энергетические барьеры, находя лучшую кристаллическую структуру. При медленном охлаждении — оседают в глобальном минимуме энергии (идеальный кристалл). При быстром охлаждении — «замерзают» в локальном минимуме (стекло).

Идея метаэвристики Simulated Annealing (SA): имитировать этот процесс! Алгоритм принимает «ухудшающие» шаги с убывающей вероятностью — это позволяет «вырываться» из локальных оптимумов и в итоге найти глобальный.

Алгоритм Simulated Annealing

Параметры:

• T₀ — начальная температура (высокая)
• α ∈ (0,1) — темп охлаждения (обычно 0.9–0.99)
• Lₖ — число итераций при температуре T_k

Алгоритм:

1. s = s₀ (начальное решение), T = T₀, BestS = s₀
2. Пока T > T_min: a. Повторить Lₖ раз:
   • s' = random_neighbor(s) (случайный сосед)
   • Δ = f(s') − f(s) (изменение цели)
   • Если Δ < 0 (улучшение): s = s' (всегда принимаем)
   • Иначе: s = s' с вероятностью exp(−Δ/T) b. T ← α · T
3. Вернуть BestS

Вероятность принятия ухудшения: exp(−Δ/T). При T → ∞: вероятность → 1 (принимаем любой шаг, случайное блуждание). При T → 0: вероятность → 0 (принимаем только улучшения, обычный ЛП).

Ключевое свойство: при высокой T алгоритм «исследует» пространство решений, при низкой — «эксплуатирует» найденные хорошие решения.

Теоретические гарантии

Теорема Гемана-Гемана (1984): если T(k) = C/log(1+k) (логарифмическое охлаждение), SA сходится к глобальному оптимуму с вероятностью 1.

Почему не используется? Слишком медленно. Логарифмическое охлаждение означает, что нужно O(e^C) итераций при температуре ~1. На практике используют геометрическое охлаждение T ← αT, α = 0.95–0.99, что нарушает условие теоремы.

Практическая сходимость: SA находит хорошие (но не гарантированно оптимальные) решения за разумное время. Для TSP: туры в 1-2% от оптимума за секунды.

Настройка параметров SA

Начальная температура T₀: выбирается так, чтобы начальный «acceptance rate» ≈ 80-90%. Например, можно запустить 1000 случайных шагов, вычислить среднее ухудшение Δ̄, и выбрать T₀ так, чтобы exp(−Δ̄/T₀) = 0.8.

Темп охлаждения α: компромисс между качеством и временем. α = 0.99 → длинный прогон, хорошее качество. α = 0.9 → быстро, хуже качество.

Число итераций Lₖ при каждой температуре: часто Lₖ = n (размер задачи). Больше итераций при одной температуре → лучше «равновесие».

Критерий остановки: T < T_min, или нет улучшений за последние k·Lₖ итераций.

SA для VLSI Layout

Задача: n компонентов на чипе, минимизировать суммарную длину соединительных проводников. Это задача размещения (Placement Problem) в VLSI (Very Large Scale Integration).

SA подход:

• Решение: координаты каждого компонента на сетке
• Соседство: swap двух компонентов или перемещение одного компонента
• Функция стоимости: суммарная длина Steiner-дерева для каждой сети

Историческое значение: SA был впервые применён именно для VLSI Layout — IBM, 1983 (Kirkpatrick, Gelatt, Vecchi). Статья в Science — одна из самых цитируемых в информатике. SA сокращал длину проводников на 10-20% по сравнению с детерминированными методами.

Современные VLSI tools: SA по-прежнему основа, но с десятками улучшений: адаптивная температура, параллельные прогоны, «перезапуск» при застревании.

SA vs. другие методы

Вывод: SA подходит для задач с большим числом локальных оптимумов, где важна простота реализации. Tabu — для структурированных задач с выраженной «памятью». Для TSP лучше всего — LK-эвристик.

Тонкости имитационного отжига

Качество SA сильно зависит от выбора параметров:

• Начальная температура T₀: должна быть достаточно высокой, чтобы исходно принимались почти все ходы (≈ 80% acceptance rate)
• Расписание охлаждения: классическое геометрическое T_k = α · T_{k-1} с α ∈ [0.85, 0.99]; адаптивные расписания (Lundy-Mees) уменьшают T в зависимости от прогресса
• Окрестность: должна позволять «достижимость» любой точки. Слишком маленькие ходы — медленная сходимость, слишком большие — потеря локальной структуры

Теоретическая сходимость

При достаточно медленном охлаждении (T_k ≥ c/log(k+1) для подходящего c) SA сходится к глобальному оптимуму с вероятностью 1 (Geman & Geman, 1984). На практике этот предел недостижим — приходится мириться с локальным оптимумом.

Параллельные варианты

• Parallel tempering (replica exchange): несколько копий SA с разными температурами обмениваются состояниями. Высокотемпературные копии исследуют, низкотемпературные эксплуатируют.
• Population SA: многоагентный вариант с обменом информацией
• GPU реализации: тысячи параллельных запусков SA с разными начальными точками

Гибридные методы

SA часто комбинируется с другими техниками:

• SA + Local Search: после нахождения хорошего решения SA — локальная оптимизация для финальной полировки
• Memetic algorithms: SA внутри генетических алгоритмов как мутация
• Variable Neighborhood Search (VNS): SA со сменой окрестности при стагнации

Применения

• VLSI placement: размещение миллионов транзисторов на чипе. SA был стандартом в 1990-е, до сих пор используется в TimberWolf, Cadence
• TSP: на задачах до 100 000 городов SA даёт решения в пределах 2-3% от оптимума
• Расписание самолётов и экипажей: Air France, Lufthansa используют SA для динамической перепланировки при сбоях
• Молекулярный дизайн: предсказание укладки белков, дизайн лекарств — SA на пространстве конформаций
• Финансовые портфели: оптимизация с дискретными ограничениями (количество акций, сектора, риск-категории)