UK 
EnglishТипова
Polski🌡️ Імітація відпалу — вихід із локальних мінімумів
Розв'яжіть маршрут комівояжера імітацією відпалу: приймайте гірші ходи з імовірністю e^(−ΔE/T), доки температура падає, виходячи з локальних мінімумів перед осіданням на короткий маршрут.
Про імітацію відпалу
Імітація відпалу (SA) — це ймовірнісна метаевристика, запропонована Кіркпатриком, Джелаттом і Веккі у 1983 році, натхненна фізичним процесом контрольованого охолодження в металургії: повільне охолодження розплавленого матеріалу дозволяє атомам осісти в низькоенергетичних кристалічних ґратках, тоді як швидке гартування захоплює їх у високоенергетичних аморфних станах. В оптимізації SA починає з високої «температури» T і приймає гірші рішення з імовірністю e−ΔE/T (критерій Метрополіса), що дозволяє вийти з локальних мінімумів; коли T знижується за розкладом охолодження, алгоритм дедалі більше поводиться як підйом на вершину (hill-climbing) і сходиться. SA може знаходити близькі до оптимальних розв'язки для NP-складних задач, як-от задача комівояжера (TSP), де вичерпний перебір неможливий.
Ця симуляція застосовує SA до TSP на випадковому наборі міст: спостерігайте, як маршрут покращується в міру охолодження температури, як прийняті гірші ходи підсвічуються помаранчевим, і порівняйте кінцеву довжину маршруту з жадібним методом найближчого сусіда. Регульовані параметри включають початкову температуру, швидкість охолодження та кількість міст, що дозволяє напряму дослідити компроміс між якістю та часом виконання.
Поширені запитання
Чому імітація відпалу приймає гірші рішення?
Прийняття гірших рішень з імовірністю e−ΔE/T дозволяє алгоритму виходити з локальних мінімумів — конфігурацій, де будь-яка мала зміна погіршує рішення, але які не є глобально оптимальними. За високої температури T приймаються майже всі гірші ходи (алгоритм широко досліджує простір); зі зниженням T приймається дедалі менше гірших ходів, і алгоритм зосереджується на використанні знайденого. Цей баланс між дослідженням і використанням є основним механізмом, що відрізняє SA від простого підйому на вершину.
Який розклад охолодження дає найкращі результати?
Логарифмічне охолодження (T(t) = T₀/ln(1+t)) теоретично гарантовано знаходить глобальний оптимум при t→∞, але непрактично повільне. На практиці стандартом є геометричне охолодження T(t+1) = α·T(t) з α ∈ [0,95; 0,999]: воно охолоджує достатньо швидко, щоб бути практичним, але достатньо повільно, щоб дозволити вихід з локальних мінімумів. Оптимальні α та початкове T₀ залежать від задачі; T₀ часто обирають так, щоб на початку приймалося 80% гірших ходів, забезпечуючи ретельне раннє дослідження.
Як імітація відпалу застосовується до задачі комівояжера?
Стан TSP — це маршрут (перестановка міст); околиця визначається 2-opt обмінами (розвертання сегмента маршруту) або 3-opt ходами (перез'єднання трьох сегментів маршруту). Енергія E — це загальна довжина маршруту. Кожна ітерація пропонує випадкового сусіда: якщо він коротший — приймається; якщо довший на ΔL — приймається з імовірністю e−ΔL/T. Після мільйонів ітерацій зі спадним T, SA зазвичай знаходить маршрути в межах 1–3% від оптимального для сотень міст.
Чи гарантовано імітація відпалу знаходить глобальний оптимум?
За логарифмічного охолодження (T(t) = c/ln(t+2)) SA сходиться до глобального оптимуму з імовірністю 1 за нескінченного часу — результат, отриманий Гаєком (1988). На практиці скінченні прогони з геометричним охолодженням не гарантують глобального оптимуму. Для TSP з n містами обчислення глобального оптимуму NP-складне, але SA з хорошими 2-opt або Lin-Kernighan ходами стабільно знаходить рішення в межах кількох відсотків від оптимального для n ≤ 1000 міст за секунди.
Що таке критерій Метрополіса і звідки він походить?
Критерій Метрополіса e−ΔE/T походить зі статистичної механіки: у канонічному ансамблі за температури T імовірність того, що система перебуває в енергетичному стані E, пропорційна e−E/kT (розподіл Больцмана). Коефіцієнт прийняття e−ΔE/T для ходу, що підвищує енергію на ΔE, забезпечує збіжність марковського ланцюга до розподілу Больцмана за фіксованої T — властивість, яка гарантує, що SA найчастіше відвідує низькоенергетичні (хороші) рішення за низьких температур.
Як імітація відпалу порівнюється з генетичними алгоритмами?
Обидва підходи є метаевристиками, натхненними популяціями, для NP-складної оптимізації. SA підтримує одне поточне рішення й використовує температуру для контролю різноманітності; генетичні алгоритми підтримують популяцію рішень і використовують схрещування та мутацію. SA простіше реалізувати й налаштувати; генетичні алгоритми можуть використовувати структуру рішення через схрещування. На практиці SA часто перевершує базові генетичні алгоритми на TSP для помірної кількості міст, тоді як генетичні алгоритми (особливо з локальним пошуком — «меметичні алгоритми») краще масштабуються на дуже великі задачі.
Що таке повторний нагрів (reheat) і коли його слід використовувати?
Повторний нагрів періодично підвищує T до вищого значення, якщо алгоритм, схоже, застряг у локальному мінімумі протягом багатьох ітерацій. Це може допомогти SA вийти з глибоких локальних улоговин, з яких саме лише геометричне охолодження вийти не може. Однак повторний нагрів ускладнює аналіз збіжності й може витрачати обчислювальний час даремно. Адаптивні розклади охолодження, що відстежують частку прийнятих ходів і динамічно коригують T (наприклад, підтримуючи цільову частку прийняття 20%), часто є більш обґрунтованою альтернативою.
Які реальні задачі використовують імітацію відпалу?
SA використовується для розміщення елементів у НВІС-мікросхемах (мінімізація довжини провідників — IBM застосовувала цей метод для чипа, що став основою оригінального Mac), згортання білків (мінімізація вільної енергії), складання розкладів (іспитів, екіпажів авіакомпаній), проєктування телекомунікаційних мереж і відновлення зображень у томографії. Сучасні реалізації SA часто гібридизують з евристиками локального пошуку, щоб суттєво покращити якість рішення в межах того самого обчислювального бюджету.
Як обрати початкову температуру T₀?
Поширена евристика: взяти вибірку випадкових ходів, обчислити середнє зростання енергії ΔE̅ для тих, що погіршують рішення, а потім встановити T₀ = −ΔE̅ / ln(χ₀), де χ₀ — бажана початкова ймовірність прийняття (зазвичай 0,8). Це гарантує, що алгоритм стартує достатньо «гарячим», щоб приймати 80% гірших ходів, забезпечуючи широке початкове дослідження. Альтернативно, T₀ можна встановити як стандартне відхилення значень цільової функції на випадкових рішеннях, масштабоване константою.
У чому різниця між імітацією відпалу та basin-hopping?
Basin-hopping (Вейлс і Дой, 1997) поєднує кроки випадкового збурення з локальною мінімізацією: кожен «крок» SA виконує повний градієнтний спуск до найближчого локального мінімуму перед застосуванням критерію Метрополіса. Це перетворює енергетичний ландшафт на спрощений «улоговинний» ландшафт (плаский всередині кожної улоговини, розривний на її межах), яким SA набагато легше орієнтуватися. Basin-hopping є стандартним методом у обчислювальній хімії для пошуку структур білків і кластерів.