Алгоритм імітації відпалу (англ. 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.]
- Ананий В. Левитин (2006). Глава 3. Метод грубой силы: Задача коммивояжера. . Москва: «Вильямс». с. 159—160. ISBN . Архів оригіналу за 2 жовтня 2011. Процитовано 15 січня 2011.
- S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery (2011). Chapter 10.12 Simulated Annealing Methods. . W.H. Press. с. 549—555. Архів оригіналу за 3 лютого 2021. Процитовано 1 березня 2021.
Див. також
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm imitaciyi vidpalu angl Simulated annealing zagalnij algoritmichnij metod rozv yazannya zadachi globalnoyi optimizaciyi osoblivo diskretnoyi ta kombinatornoyi optimizaciyi v yakomu procedura poshuku globalnogo rozv yazku imituye fizichnij proces vidpalu Vin chasto vikoristovuyetsya koli poshuk nablizhenogo globalnogo optimumu vazhlivishij nizh poshuk tochnogo lokalnogo optimumu za vstanovlenij promizhok chasu Metod ye adaptaciyeyu algoritmu Metropolis Gastings metodu Monte Karlo dlya generuvannya zrazkovih staniv termodinamichnoyi sistemi opublikovanogo Nikolas Metropolis u 1953 roci Imitaciya vidpalyuvannya shukaye maksimum Metoyu tut ye dosyagti najvishoyi tochki prote vikoristannya prostogo algoritmu shodzhennya shilom tut ne dostatno oskilki ye bagato lokalnih maksimumiv Globalnij maksimum znahoditsya shlyahom povilnogo znizhennya temperaturi Kombinatorni zadachiBagato problem v oblasti proektuvannya planuvannya ta virobnictva mozhe buti zmodelovano Zadachi kombinatornoyi optimizaciyi pridilyayetsya velika uvaga protyagom ostannih dvoh desyatilit Dosyagnennya v kombinatornij optimizaciyi podilyayetsya na 2 pidklasi Pershij mistit ti problemi yaki mozhna efektivno rozv yazati Dlya prikladu linijne programuvannya pidbirannya merezhevi problemi Drugij mistit problemi yaki ne mayut algoritmu yakij rozv yazuye kozhen vipadok za polinomialnij chas Otzhe ye vipadki yaki potrebuyut super polinomialnogo abo j eksponencialnogo chasu dlya optimalnogo rozv yazannya Bagato vidomih problem i zadach vidnosyat do cogo klasu napevne najvidomishim prikladom ye zadacha komivoyazhera Ochevidno sho skladni zadachi povinni obroblyatisya na praktici Grubo kazhuchi ce mozhna zrobiti dvoma tipami algoritmiv U pershomu vipadku vikoristovuyutsya algoritmi optimizaciyi yaki znahodyat mozhlivij optimalnij rozv yazok z vikoristannyam velikoyi kilkosti chasu ta obchislen U drugomu vipadku zastosovuyut evristichni algoritmi yaki dayut zmogu znajti nablizheni rozv yazki vikonuyuchi neveliku kilkist obchislen Algoritm imitaciyi vidpalu odin z najvidomishih lokalnih poshukovih algoritmiv Lokalnij poshukLokalnij poshuk poshuk sho zdijsnyuyetsya algoritmami lokalnogo poshuku grupoyu algoritmiv u yakih poshuk vedetsya tilki na pidstavi potochnogo stanu a ranishe projdeni stani ne vrahovuyutsya j ne zapam yatovuyutsya Osnovnoyu metoyu poshuku ye ne znahodzhennya optimalnogo shlyahu do cilovoyi tochki a optimizaciya deyakoyi cilovoyi funkciyi tomu zadachi rozv yazuvani podibnimi algoritmami nazivayut zadachami optimizaciyi Dlya opisu prostoru staniv u takih zadachah vikoristovuyut landshaft prostoru staniv u comu predstavlenni zadacha zvoditsya do poshuku stanu globalnogo maksimumu abo minimumu na danomu landshafti Na pochatku 1980 h Kirkpatrick 1983 i nezalezhno Cerny 1985 vveli koncepciyi vidpalu u kombinatornij optimizaciyi Spochatku ci koncepciyi v znachnij miri buli pobudovani na analogiyi mizh fizichnim procesom vidpalu tverdih til i problemoyu virishennya velikih kombinatornih optimizacij Algoritm imitaciyi vidpaluAlgoritm imitaciyi vidpalu zagalnij algoritmichnij metod rozv yazannya zadachi globalnoyi optimizaciyi osoblivo diskretnoyi ta kombinatornoyi optimizaciyi U galuzi fiziki kondensovanih seredovish vidpalom nazivayetsya teplovij proces otrimannya nizkih energetichnih staniv tila v teplovij bani termostati Cej proces skladayetsya z dvoh krokiv Kirkpatrick ta in 1983 pidvishennya temperaturi teplovoyi bani do maksimalnogo znachennya do tverdih rozplaviv povilne znizhennya temperaturi teplovoyi bani poki chastinki ne vporyadkuyutsya v osnovnij stan tila U ridkij fazi chastinki roztashovuyutsya vipadkovim chinom a v osnovnomu stani tverdogo tila vsi chastinki roztashovani v dobre strukturovani gratki dlya yakih vidpovidna energiya minimalna Osnovnij stan tverdogo tila otrimuyetsya tilki todi koli maksimalne znachennya temperaturi dosit visoke i oholodzhennya zdijsnyuyetsya dosit povilno V inshomu vipadku tilo zastigne v metastabilnomu stani a ne v istinnomu stani Algoritm gruntuyetsya na imitaciyi fizichnogo procesu yakij vidbuvayetsya pri kristalizaciyi rechovini z ridkogo stanu v tverdij u tomu chisli pri vidpali metaliv Peredbachayetsya sho atomi vzhe vishikuvalisya v kristalichnu reshitku ale she dopustimi perehodi okremih atomiv z odniyeyi komirki v inshu Peredbachayetsya sho proces protikaye pri postupovomu znizhenni temperaturi Perehid atoma z odniyeyi komirki v inshu vidbuvayetsya z deyakoyu jmovirnistyu prichomu imovirnist zmenshuyetsya z ponizhennyam temperaturi Stijka kristalichna reshitka vidpovidaye minimumu energiyi atomiv tomu atom abo perehodit v stan z menshim rivnem energiyi abo zalishayetsya na misci Cej algoritm takozh nazivayetsya algoritmom Metropolisa za im yam jogo avtora Nikolasa Metropolis Za dopomogoyu modelyuvannya takogo procesu shukayetsya taka tochka abo mnozhina tochok na yakih dosyagayetsya minimum deyakoyi chislovoyi funkciyi Povertayuchis do imitaciyi vidpalu algoritm Metropolis mozhe buti vikoristanij dlya generuvanya poslidovnosti rishen zadachi kombinatornoyi optimizaciyi pripuskayuchi ekvivalentnosti mizh fizichnoyu sistemoyu bagatoh chastinok i zavdannyam kombinatornoyi optimizaciyi rozv yazannya zadachi kombinatornoyi optimizaciyi ekvivalentni stanu fizichnoyi sistemi vartist rishennya ekvivalentno energiyi stanu sistemi Krim togo mi vvodimo keruyuchij parametr yakij vidigraye rol temperaturi Takim chinom Simulated annealing algoritm mozhna rozglyadati yak iteraciyi algoritmu Metropolis vikonani na zmenshennya znachennya keruyuchogo parametra Znachennya chotiroh funkcij v proceduri SIMULATED ANNEALING ochevidni INITIALIZE obchislyuye i zadaye pochatkovi znachennya parametram c ta L GENERATE vibiraye susidij rozv yazok vidnosno potochnogo rozv yazku CALCULATE LENGTH i CALCULATE CONTROL obchislyuye novi znachennya parametriv L ta c vidpovidno Porivnyuyuchi simulated annealing z iteracijnim polipshennyam ochevidno sho simulated annealing mozhna rozglyadati yak uzagalnennya Algoritm imitaciyi vidpalu staye identichnim iteracijnomu pokrashennyu v razi koli znachennya keruyuchogo parametra prijmayetsya yak nul Sho stosuyetsya porivnyannya produktivnist oboh algoritmiv dlya bilshosti zavdan simulated annealing pracyuye shvidshe nizh iteracijne pokrashennya Pidsumkovij chas realizaciyi modelyuvannya vidpalu vihodit shlyahom stvorennya poslidovnosti odnoridnih lancyuzhkiv Markova obmezhenoyi dovzhini pri nizhidnomu znachenni keruyuchogo parametra Dlya cogo naboru parametriv povinno buti zaznacheno sho viznachaye zbizhnist algoritmu Ci parametri ob yednani v tak zvanij grafik oholodzhennya Grafik oholodzhennya viznachaye skinchennu poslidovnist znachen parametra i skinchenne chislo perehodiv pri kozhnomu znachenni keruyuchogo parametra Tochnishe vin viznachaye pochatkove znachennya parametra kontrolyu c0 zmenshennya funkciyi dlya znizhennya vartosti kontrolnogo parametra kinceve znachennya kontrolnogo parametra vkazanij kriterij zupinki takozh skinchenne znachennya dovzhini kozhnogo odnoridnogo lancyuzhka Markova Poshuk adekvatnih grafikiv oholodzhennya buv predmetom bagatoh doslidzhen protyagom ostannih rokiv Vidguki dayutsya Van Laarhoven i Aarts 1987 Collins ta in 1988 Romeo ta Sangiovanni Vincentelli 1991 Statichnij grafik oholodzhennya Ce prostij grafik yakij takozh nazivayetsya geometrichnim grafikom Vin pohodit she z pochatku roboti nad grafikom oholodzhennya Vin i dosi vikoristovuyetsya v bagatoh praktichnih situaciyah Ostatochne znachennya kontrolnogo parametra tut ostatochna velichina fiksuyetsya i otrimuye nevelike znachennya yake mozhe buti pov yazane z najmensh mozhlivoyu rizniceyu u vartosti mizh dvoma susidnimi rozv yazkami Dovzhina Markovskogo lancyuga Dovzhina Markovskih lancyugiv vstanovlyuyetsya znachennyam yake maye vidnoshennya do velichini susidnih prikladnih zadach UzagalnennyaZ momentu svoyeyi poyavi v 1983 roci modelyuvannya vidpalu bulo zastosovane do dosit velikoyi kilkosti riznih problem u riznih oblastyah Bilshe 20 rokiv dosvidu priveli taki zagalni sposterezhennya Visoka yakist rozv yazkiv mozhe buti otrimana ale inodi za rahunok velikih obsyagiv obchislen U bagatoh praktichnih situaciyah de nayavni algoritmi ne pracyuyut modelyuvannya vidpalu maye veliki plyusi zagalnist zastosuvannya i prostota realizaciyi Takim chinom modelyuvannya vidpalu ye algoritmom yakij vsi praktiki matematiki ta naukovci komp yuternih nauk povinni mati u svoyemu instrumentariyi Dzherela informaciyiSpringer Search Methodologies Introductory Tutorials in Optimization and Decision Support Techniques 2005 ISBN 0387234608 Ananij V Levitin 2006 Glava 3 Metod gruboj sily Zadacha kommivoyazhera Moskva Vilyams s 159 160 ISBN 5 8459 0987 2 Arhiv originalu za 2 zhovtnya 2011 Procitovano 15 sichnya 2011 S A Teukolsky W T Vetterling and B P Flannery 2011 Chapter 10 12 Simulated Annealing Methods W H Press s 549 555 Arhiv originalu za 3 lyutogo 2021 Procitovano 1 bereznya 2021 Div takozhGenetichni algoritmi Algoritm shodzhennya na vershinu