Довідка та теорія
Імітація відпалу наслідує повільне охолодження металу. Нагріті атоми вільно блукають; зі зниженням температури вони осідають у кристалі з низькою енергією. Алгоритм трактує довжину маршруту як «енергію» й охолоджує віртуальну температуру.
Задача комівояжера
Для n міст знайти найкоротший замкнений маршрут,
що відвідує кожне рівно один раз. Вона NP-складна, тож ми
шукаємо короткий маршрут, а не доведено оптимальний.
Сусідні ходи
Кожен крок пропонує сусідній маршрут ходом
2-opt (обернути сегмент, розплутавши ребра) або
перестановкою двох міст, потім вимірює зміну
довжини ΔE.
Критерій Метрополіса
Якщо ΔE ≤ 0, хід приймається. Інакше його
приймають з імовірністю P = exp(−ΔE / T). Висока
T ⇒ приймається майже все (дослідження); низька
T ⇒ жадібно (використання).
Геометричне охолодження
Температура змінюється як T ← α · T, де швидкість
охолодження α трохи менша за 1. Повільніше
охолодження досліджує більше й зазвичай дає коротші маршрути.
Вихід із локальних мінімумів
Чистий підйом на гору застрягає там, де кожен сусід гірший. Іноді приймаючи гірший маршрут, відпал може вибратися й досягти кращого басейну, перш ніж температура його зафіксує.
Часті питання
Що таке імітація відпалу?
Ймовірнісний метод оптимізації, натхненний повільним охолодженням металів. Він робить випадкові зміни, завжди приймаючи покращення, але також приймаючи гірші стани з імовірністю, що залежить від температури, що дозволяє виходити з локальних мінімумів.
Чому метод приймає гірші розв'язки?
Прийняття гірших ходів з імовірністю
e^(−ΔE/T) дозволяє пошуку вибратися з локальних
мінімумів. За високої температури він досліджує широко; зі
зниженням температури стає жадібним і осідає у хорошому
басейні.
Що таке критерій прийняття Метрополіса?
Хід, що знижує вартість, завжди приймають. Хід, що підвищує
вартість на ΔE, приймають з імовірністю
exp(−ΔE/T), де T — поточна
температура.
Що таке графік охолодження?
Він визначає, як знижується температура. Ця симуляція
використовує геометричний графік, T ← α·T з α
трохи менше за 1. Повільніше охолодження зазвичай дає
коротші маршрути, але триває довше.
Що таке задача комівояжера?
Найкоротший маршрут, що відвідує кожне місто рівно один раз і повертається до початку. Вона NP-складна, тож імітація відпалу швидко знаходить короткі, близькі до оптимальних маршрути.
Що таке ходи 2-opt і перестановки?
Хід 2-opt обертає сегмент маршруту, розплутуючи два ребра. Хід перестановки міняє місцями два міста. Обидва дають сусідній маршрут для порівняння з поточним.
Що показує частка прийняття?
Частина запропонованих ходів, прийнятих нещодавно. Вона висока, поки температура висока, і падає до нуля, коли графік охолоджується.
Чи знаходить метод оптимальний маршрут?
Не гарантовано. За нескінченно повільного охолодження він теоретично сходиться до глобального оптимуму, але на практиці повертає високоякісний близький до оптимального розв'язок.
Як швидкість охолодження впливає на результат?
Швидкість, близька до 1 (напр. 0,999), охолоджує повільно й зазвичай дає коротші маршрути. Менша швидкість (напр. 0,99) сходиться швидко, але частіше застрягає в локальному мінімумі.
Де її застосовують на практиці?
У компонуванні мікросхем VLSI, плануванні, маршрутизації транспорту, відновленні зображень, навчанні нейронних мереж і багатьох інших комбінаторних задачах із великим, нерівним простором пошуку.