|
||
Počátkem 80. let Kirkpatrick, Gelatt a Vecchi ve Watsonově výzkumném centru v sídle společnosti IBM v USA a také Černý v MFF UK v Bratislavě dostali nápad jak vytvořit algoritmus, který může řešit problémem globální optimalizace - hledání globálního optima.
V tomto algoritmu autoři využili fyzikální podstaty simulovaného žíhání, která vychází z fyzikální představy procesů při odstranění defektů krystalické mřížky. Krystal se zahřeje na vysokou teplotu a potom se pomalu ochlazuje (žíhá). Defekty krystalické mřížky mají při vysoké teplotě vysokou pravděpodobnost zániku. Pomalé ochlazování systému zabezpečuje malou pravděpodobnost vzniku nových defektů. Při žíhání se soustava snaží dostat do stavu s minimální energií - krystal bez defektů. V optimalizaci je krystal reprezentován nějakým přípustným řešením. Každému krystalu lze přiřadit energii krystalu ve formě hodnoty účelové funkce. Dalším parametrem je teplota, což je formální analogie teploty krystalu. [16]
Simulované žíhání je dalším algoritmem odvozeným od horolezeckého algoritmu. Jako u předchozí metody sekvenčního prohledávání - horolezeckého algoritmu lze užít transformace aktuálního nejlepšího prvku na nový prvek, tedy prvek v okolí. V našem případě bude znovu využito náhodně vygenerovaného prvku v okolí.
Při prohledávání stavového prostoru se může snadno stát, že algoritmus uvízne v lokálním minimu. V metodě se tomu snažíme zabránit tím, že zpočátku provádíme velké změny a díky tomu se můžeme dostat z lokálního minima. Velikost změny záleží na teplotě. Čím větší je teplota, tím větší se provádí změny. V průběhu výpočtu algoritmu je teplota postupně snižována na základě rychlosti konvergence. Pokud algoritmus konverguje rychle, snižuje se teplota také rychle. Konverguje-li algoritmus pomalu, zpomalí se snižování teploty, aby se případně podařilo vyprostit z lokálního minima. [23]
Existuje mnoho variant jak snižovat teplotu, vyjmenujeme alespoň 2 základní:
kde:
• 
… Aktuální teplota.
• 
… Předchozí teplota v přechozí k-té iteraci.
• 
… Definovaná konstanta, doporučená hodnota 
podle literatury [27], pokud 
.
• 
… Definovaná konstanta počtu iterací, po nichž má být provedena redukce teploty.
• 
… Čítač iterací.
• mod … Zbytek po celočíselném dělení.
2. Simulované hašení: [16]
kde:
• 
… Nezáporná konstanta pro simulované hašení, 
.
U simulovaného hašení je na začátku algoritmu pravděpodobnost přijetí horšího skoro rovna jedné. Poté co je přijat horší prvek, pravděpodobnost se snižuje spolu s klesající teplotou. To je patrné na následujícím obrázku (viz 
).
SimulatedAnnealing2 - v počáteční fázi algoritmu (viz 
) je nastavena teplota na hodnotu 1 tzn., že v počátku algoritmu je pravděpodobnost přijetí horšího řešení největší (řádek 5). Ochlazovací plán je prováděn na základě simulovaného hašení - aktuální teplota je spočtena na základě koeficientu definovaným uživatelem (řádek 13). Tento algoritmus se dá přirovnat k algoritmu s restartem v posledním známém bodě - pokud není splněna podmínka kritéria ukončení. Algoritmus stále pokračuje v hledání optima tím způsobem, že pokud teplota spadne pod definovanou spodní mez, je opět nastavena na počáteční hodnotu jedna a tím pádem se znovu zvýšila pravděpodobnost přijmutí horšího prvku (řádek 16).
U algoritmů simulovaného žíhání se původní prvek nahrazuje novým horším prvkem v následném procesu simulovaného žíhání s pravděpodobností dle Metropolisova vzorce: [12]
kde:
• p … Pravděpodobnost přijetí nového řešení.
• min … Minimum ze dvou hodnot.
• 
… Účelová funkce.
Konkrétních předpisů pro výpočet této pravděpodobnosti je několik, můžeme si vybrat, který se nám pro danou úlohu lépe hodí.
Při vhodném nastavení počáteční teploty (dosti velká hodnota) metoda simulovaného žíhání prohledává nejprve prostor řešení silně stochasticky, přijímá i stavy s horším ohodnocením, než má současné řešení (globální charakter algoritmu). Tato vlastnost simulovaného žíhání je velmi důležitým rysem této metody, protože poskytuje možnost relativně snadno se dostat z lokálního minima a prohledat i jiné oblasti v prostoru řešení. Tato možnost se pak postupně snižuje úměrně se zmenšováním teploty. Pro velmi malé teploty připustí Metropolisovo kritérium prakticky akceptování už jen lepšího řešení než je současné (lokální charakter algoritmu). [17]
Dá se dokázat, že pokud je ochlazovací plán dostatečně pomalý a metoda generování nových přípustných řešení pokrývá celý stavový prostor, pak simulované žíhání konverguje v pravděpodobnosti ke globálnímu optimu.
Protože se pohybujeme ve stavovém prostoru i směrem k horším řešením, musíme si pamatovat dosud nejlepší nalezené řešení, nebo toto řešení můžeme opustit a již se k němu nevrátit.
Podle publikovaných výsledků v některých zahraničních článcích, je simulované žíhání jedním z nejúspěšnějších tradičních stochastických optimalizačních algoritmů. Proto by mohlo být rychlejší a přesnější než genetické algoritmy. Každé volání účelové funkce se využívá přímo k prohledávání stavového prostoru, nepotřebujeme žádná nadbytečná volání účelové funkce. [16]