Алгоритм імітації відпалу
Алгоритм імітації відпалу (англ. Simulated annealing) - загальний алгоритмічний метод розв'язання задачі глобальної оптимізації, особливо дискретної та комбінаторної оптимізації, в якому процедура пошуку глобального розв'язку імітує фізичний процес відпалу. Він часто використовується, коли пошук наближеного глобального оптимуму важливіший, ніж пошук точного локального оптимуму за встановлений проміжок часу. Метод є адаптацією алгоритму Метрополіс–Гастінгс, методу Монте-Карло для генерування зразкових станів термодинамічної системи, опублікованого Ніколас Метрополіс у 1953 році.
Багато проблем в області проектування, планування та виробництва може бути змодельовано. Задачі комбінаторної оптимізації приділяється велика увага протягом останніх двох десятиліть. Досягнення в комбінаторній оптимізації поділяється на 2 підкласи. Перший містить ті проблеми, які можна ефективно розв'язати. Для прикладу: лінійне програмування, підбирання, мережеві проблеми. Другий містить проблеми, які не мають алгоритму, який розв'язує кожен випадок за поліноміальний час. Отже, є випадки які потребують супер-поліноміального або й експоненціального часу для оптимального розв'язання. Багато відомих проблем і задач відносять до цього класу, напевне найвідомішим прикладом є задача комівояжера. Очевидно, що складні задачі повинні оброблятися на практиці. Грубо кажучи, це можна зробити двома типами алгоритмів. У першому випадку використовуються алгоритми оптимізації, які знаходять можливий оптимальний розв'язок, з використанням великої кількості часу, та обчислень. У другому випадку застосовують евристичні алгоритми, які дають змогу знайти наближені розв'язки, виконуючи невелику кількість обчислень. Алгоритм імітації відпалу один з найвідоміших локальних пошукових алгоритмів.
Локальний пошук — пошук, що здійснюється алгоритмами локального пошуку, групою алгоритмів, у яких пошук ведеться тільки на підставі поточного стану, а раніше пройдені стани не враховуються й не запам'ятовуються. Основною метою пошуку є не знаходження оптимального шляху до цільової точки, а оптимізація деякої цільової функції, тому задачі, розв'язувані подібними алгоритмами, називають задачами оптимізації. Для опису простору станів у таких задачах використовують ландшафт простору станів, у цьому представленні задача зводиться до пошуку стану глобального максимуму (або мінімуму) на даному ландшафті. На початку 1980-х Kirkpatrick (1983) і незалежно Cerny (1985) ввели концепції відпалу у комбінаторній оптимізації. Спочатку ці концепції в значній мірі були побудовані на аналогії між фізичним процесом відпалу твердих тіл і проблемою вирішення великих комбінаторних оптимізацій.
Алгоритм імітації відпалу — загальний алгоритмічний метод розв'язання задачі глобальної оптимізації, особливо дискретної та комбінаторної оптимізації. У галузі фізики конденсованих середовищ, відпалом називається тепловий процес отримання низьких енергетичних станів тіла в тепловій бані (термостаті). Цей процес складається з двох кроків (Kirkpatrick та ін., 1983):
- підвищення температури теплової бані до максимального значення, до твердих розплавів
- повільне зниження температури теплової бані, поки частинки не впорядкуються в основний стан тіла
У рідкій фазі частинки розташовуються випадковим чином, а в основному стані твердого тіла всі частинки розташовані в добре структуровані ґратки, для яких відповідна енергія мінімальна. Основний стан твердого тіла отримується тільки тоді, коли максимальне значення температури досить високе і охолодження здійснюється досить повільно. В іншому випадку, тіло застигне в метастабільному стані, а не в істинному стані. Алгоритм ґрунтується на імітації фізичного процесу, який відбувається при кристалізації речовини з рідкого стану в твердий, у тому числі при відпалі металів. Передбачається, що атоми вже вишикувалися в кристалічну решітку, але ще допустимі переходи окремих атомів з однієї комірки в іншу. Передбачається, що процес протікає при поступовому зниженні температури. Перехід атома з однієї комірки в іншу відбувається з деякою ймовірністю, причому імовірність зменшується з пониженням температури. Стійка кристалічна решітка відповідає мінімуму енергії атомів, тому атом або переходить в стан з меншим рівнем енергії, або залишається на місці. (Цей алгоритм також називається алгоритмом Метрополіса , за ім'ям його автора Ніколаса Метрополіс).
За допомогою моделювання такого процесу шукається така точка або множина точок, на яких досягається мінімум деякої числової функції.
Повертаючись до імітації відпалу, алгоритм Metropolis може бути використаний для генеруваня послідовності рішень задачі комбінаторної оптимізації, припускаючи еквівалентності між фізичною системою багатьох частинок і завданням комбінаторної оптимізації:
- розв'язання задачі комбінаторної оптимізації еквівалентні стану фізичної системи
- вартість рішення еквівалентно енергії стану системи.
Крім того, ми вводимо керуючий параметр, який відіграє роль температури. Таким чином Simulated annealing алгоритм, можна розглядати як ітерації алгоритму Metropolis, виконані на зменшення значення керуючого параметра. Значення чотирьох функцій в процедурі SIMULATED_ANNEALING очевидні:
- INITIALIZE обчислює і задає початкові значення параметрам c та L
- GENERATE вибирає сусідій розв'язок відносно поточного розв'язку
- CALCULATE.LENGTH і CALCULATE_CONTROL обчислює нові значення параметрів L та c відповідно
Порівнюючи simulated annealing з ітераційним поліпшенням, очевидно що simulated annealing можна розглядати як узагальнення. Алгоритм імітації відпалу стає ідентичним ітераційному покращенню в разі, коли значення керуючого параметра приймається як нуль. Що стосується порівняння продуктивність обох алгоритмів, для більшості завдань simulated annealing працює швидше, ніж ітераційне покращення.
Підсумковий час реалізації моделювання відпалу виходить шляхом створення послідовності однорідних ланцюжків Маркова обмеженої довжини при низхідному значенні керуючого параметра. Для цього набору параметрів повинно бути зазначено, що визначає збіжність алгоритму. Ці параметри об'єднані в так званий графік охолодження. Графік охолодження визначає скінченну послідовність значень параметра, і скінченне число переходів при кожному значенні керуючого параметра. Точніше, він визначає:
- початкове значення параметра контролю c0
- зменшення функції для зниження вартості контрольного параметра
- кінцеве значення контрольного параметра, вказаний критерій зупинки, також скінченне значення довжини кожного однорідного ланцюжка Маркова.
Пошук адекватних графіків охолодження був предметом багатьох досліджень протягом останніх років. Відгуки даються Van Laarhoven і Aarts (1987), Collins та ін. (1988), Romeo та Sangiovanni-Vincentelli (1991).
Статичний графік охолодження. Це простий графік, який також називається геометричним графіком. Він походить ще з початку роботи над графіком охолодження. Він і досі використовується в багатьох практичних ситуаціях. Остаточне значення контрольного параметра, тут остаточна величина фіксується і отримує невелике значення, яке може бути пов'язане з найменш можливою різницею у вартості між двома сусідніми розв'язками.
Довжина Марковського ланцюга. Довжина Марковських ланцюгів встановлюється значенням, яке має відношення до величини сусідніх прикладних задач.
З моменту своєї появи в 1983 році моделювання відпалу було застосоване до досить великої кількості різних проблем у різних областях. Більше 20 років досвіду привели такі загальні спостереження:
- Висока якість розв'язків може бути отримана, але іноді за рахунок великих обсягів обчислень.
- У багатьох практичних ситуаціях, де наявні алгоритми не працюють, моделювання відпалу має великі плюси: загальність застосування і простота реалізації.
Таким чином, моделювання відпалу є алгоритмом, який всі практики математики та науковці комп'ютерних наук повинні мати у своєму інструментарії.
- Springer,.Search Methodologies - Introductory Tutorials in Optimization and Decision Support Techniques.[2005.ISBN 0387234608]
- Ананий В. Левитин (2006). Глава 3. Метод грубой силы: Задача коммивояжера. Алгоритмы: введение в разработку и анализ. Москва: «Вильямс». с. 159—160. ISBN 5-8459-0987-2. Архів оригіналу за 2 жовтня 2011. Процитовано 15 січня 2011.
- S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery (2011). Chapter 10.12 Simulated Annealing Methods. Art of Scientific Computing. W.H. Press. с. 549—555. Архів оригіналу за 3 лютого 2021. Процитовано 1 березня 2021.