Simulated Annealing: как металлурги научили компьютер находить лучшие решения

🎯 Зачем это нужно?

Представь, что ты пытаешься найти самый короткий маршрут для доставки пиццы по 100 адресам в городе 🍕. Обычные алгоритмы застревают в “почти хороших” решениях - как будто ты нашёл неплохой маршрут, но не можешь выбраться из своего района, чтобы найти ещё лучший!

Где это используется:

• 📱 Chip design: Intel размещает миллиарды транзисторов так, чтобы минимизировать задержки
• 🚚 Логистика: DHL оптимизирует маршруты тысяч грузовиков одновременно
• 🧬 Биоинформатика: Google DeepMind предсказывает структуру белков
• 🎮 Game AI: алгоритм создаёт интересные уровни в процедурно генерируемых играх

📚 История вопроса

В 1983 году физики Киркпатрик, Гелатт и Векки заметили странное: когда кузнецы медленно охлаждают раскалённый металл (отжиг), атомы успевают найти самое “удобное” расположение - металл становится прочнее! 🔥→❄️

А что если так же “охлаждать” алгоритмы оптимизации? Начать с “горячего” поиска (принимать даже плохие решения), а потом постепенно “остывать” (становиться более разборчивым).

Забавный факт: метод Metropolis, лежащий в основе SA, создали в 1953 году для моделирования… ядерных взрывов на первых компьютерах! 💥

💡 Интуиция

Обычная оптимизация = альпинист в тумане, который хочет забраться на самую высокую гору 🏔️. Он чувствует наклон под ногами и всегда идёт вверх. Проблема? Он может застрять на маленькой горке, думая что он на Эвересте!

[МЕДИА: image_01] Описание: Ландшафт оптимизации с локальными и глобальным минимумами, показывающий как SA “прыгает” между холмами Промпт: “3D optimization landscape with multiple local minima and one global minimum, animated ball representing simulated annealing jumping between peaks with decreasing probability, educational visualization, modern clean style”

Simulated Annealing = умный альпинист 🧠:

• В начале (T высокая): “горячий” - может телепортироваться даже в плохие места, исследуя всю карту
• Постепенно “остывает”: снижает вероятность плохих прыжков
• В конце (T низкая): ведёт себя как обычный градиентный спуск

Ключевая идея: иногда нужно стать хуже, чтобы потом стать лучше! 📈📉📈

📐 Формальное определение

Алгоритм Simulated Annealing:

1. Инициализация: начальное решение x₀, температура T₀
2. На каждой итерации:
   • Генерируем соседа: x’’ = neighbor(x')
   • Вычисляем изменение: ΔE = f(x’’) - f(x')
   • Критерий принятия:
     • Если ΔE < 0 (лучше) → принимаем всегда
     • Если ΔE ≥ 0 (хуже) → принимаем с вероятностью P = e^(-ΔE/T)
3. Охлаждение: T ← α·T (где 0.8 ≤ α ≤ 0.99)
4. Стоп: когда T мала или найдено хорошее решение

Распределение Больцмана: P(state) ∝ e^(-E(state)/T)

• При T → ∞: все состояния равновероятны (хаос)
• При T → 0: только лучшие состояния (порядок)

🔍 Примеры с разбором

Пример 1: Задача коммивояжёра (4 города)

Города: A(0,0), B(1,0), C(1,1), D(0,1) Начальный маршрут: A→B→C→D→A, длина = 4

[МЕДИА: image_02]
Описание: Квадрат из 4 городов с разными маршрутами и их длинами Промпт: “traveling salesman problem visualization with 4 cities in square formation, multiple route options shown in different colors, distances labeled, clean educational diagram”

Итерация при T = 2.0:

1. Текущий: A→B→C→D→A (длина = 4)
2. Сосед: A→C→B→D→A (длина = 2+√2 ≈ 3.41)
3. ΔE = 3.41 - 4 = -0.59 < 0 → принимаем! ✅

Итерация при T = 0.5:

1. Текущий: A→C→B→D→A (длина ≈ 3.41)
2. Сосед: A→D→B→C→A (длина = 2+√2 ≈ 3.41)
3. ΔE ≈ 0, P = e^(0/0.5) = 1 → принимаем с вероятностью ≈ 50%

Пример 2: Функция Растригина

f(x,y) = 20 + x² - 10cos(2πx) + y² - 10cos(2πy)

Эта функция имеет множество локальных минимумов, но глобальный минимум в (0,0) где f = 0.

T = 10: примем переход из (0.5, 0.5) в (1.5, 0.5) даже если он хуже:

• ΔE ≈ 8, P = e^(-8/10) ≈ 0.45 (45% шанс)

T = 0.1: тот же переход:

• P = e^(-8/0.1) ≈ 10^(-35) (практически 0%)

🎮 Практика

Базовый уровень 🟢

Задание 1: При T = 1, текущая энергия E = 10, новая энергия E’’ = 12. Какова вероятность принятия нового решения?

Задание 2: Температура снижается по закону T = 100 · 0.9^t. При какой итерации T станет меньше 1?

Задание 3: Объясни, почему при T → 0 алгоритм превращается в жадный поиск?

Задание 4: Что произойдёт, если охлаждать слишком быстро (α = 0.5)?

Продвинутый уровень 🟡

Задание 5: Реализуй псевдокод SA для минимизации f(x) = x² - 4x + 7 на интервале [-10, 10]:

def simulated_annealing():
    x = random.uniform(-10, 10)  # начальная точка
    T = 100
    alpha = 0.95
    
    while T > 0.01:
        # твой код здесь
        pass
Задание 6: Для задачи размещения 8 ферзей на доске выбери функцию соседства:
a) переставить двух ферзей местами
b) передвинуть одного ферзя на соседнюю клетку
c) переставить ферзей в двух строках
Задание 7: График функции имеет 5 локальных минимумов со значениями [3, 7, 2, 9, 1]. При T = 2 мы находимся в минимуме со значением 7. Рассчитай вероятности перехода в каждый другой минимум.
Челлендж 🔴
Задание 8: Adaptive Cooling: предложи схему охлаждения, которая замедляется при нахождении хороших решений и ускоряется при застревании.
Задание 9: Multi-start SA: как модифицировать алгоритм, чтобы запустить несколько "отжигов" параллельно и выбрать лучший результат?
Задание 10: В генетическом алгоритме мутация аналогична переходу к соседу в SA. Как можно объединить SA с генетическими операторами?
⚠️ Частые ошибки
❌ Ошибка: Слишком быстрое охлаждение (α = 0.5)
✅ Правильно: Медленное охлаждение (α = 0.95-0.99)
💡 Почему: Быстрое охлаждение = недостаточное исследование пространства
❌ Ошибка: Плохая функция соседства (слишком маленькие или большие изменения)
✅ Правильно: Сбалансированная функция соседства
💡 Почему: Маленькие шаги = медленная сходимость, большие = хаос
❌ Ошибка: Фиксированная начальная температура для любой задачи
✅ Правильно: T₀ зависит от масштаба целевой функции
💡 Почему: Если T₀ слишком мала, алгоритм сразу жадный; слишком велика - долго случайный
❌ Ошибка: Игнорирование критерия останова
✅ Правильно: Остановка по температуре ИЛИ количеству итераций без улучшения
💡 Почему: Можем "переотжечь" и потерять хорошее решение
❌ Ошибка: Использование SA для выпуклых функций
✅ Правильно: Градиентные методы для выпуклых функций, SA для мультимодальных
💡 Почему: SA медленнее градиентных методов на "хороших" функциях
🎓 Главное запомнить
✅ Суть: Разрешаем плохие переходы с убывающей вероятностью P = e^(-ΔE/T)
✅ Формула: Распределение Больцмана + геометрическое охлаждение
✅ Применение: Комбинаторная оптимизация с множественными локальными минимумами
🔗 Связь с другими темами
Назад к уроку 297: SA часто используется для настройки гиперпараметров других алгоритмов оптимизации
Вперёд: Genetic Algorithms (урок 299) - другой природно-вдохновлённый метод, который можно комбинировать с SA
Связи:
Марковские цепи (SA = цепь Маркова с зависящими от температуры переходами)
Reinforcement Learning (exploration vs exploitation дилемма)
Monte Carlo методы (случайная генерация соседей)