Simulované žíhání

Simulované žíhání (SA) (Simulated annealing) je heuristická optimalizační metoda, řadící se mezi tzv. evoluční algoritmy, inspirovaná žíháním kovových slitin s cílem získání jejich optimálních vlastností, užívaná k řešení složitých optimalizačních úloh, které nelze řešit konvenčními metodami jako např. metoda Lagrangeových multiplikátorů, lineární programování, kvadratické programování atd.

Evoluční algoritmy

Evoluční algoritmy se užívají k nalezení dostatečně kvalitního řešení optimalizačních úloh v dostatečně krátkém čase. Mezi evoluční algoritmy inspirované přírodou se zahrnuje celé spektrum optimalizačních heuristických technik, např. genetické algoritmy či simulované žíhání. Heuristiky můžeme popsat jako zkratkovitý postup prohledávání prostoru řešení bez záruky správného výsledku, nicméně jsou zbaveny celé řady neduhů konvenčních optimalizačních metod, jako např. požadavek spojitosti či diferencovatelnosti objektivní resp. vazební funkce, respektování omezujících podmínek, uvíznutí v mělkém lokálním minimu atd. Na druhou stranu však je při jejich aplikaci zapotřebí nastavení jistých volných parametrů, které je nutné „naladit“ v závislosti na konkrétním optimalizačním problému, tak jako např. počáteční resp. konečnou teplotu a počet iterací dále popsaného algoritmu simulovaného žíhání.

Algoritmus simulovaného žíhání

Simulované žíhání vychází z evoluce termodynamických systémů. Žíháním označujeme ve fyzice proces, při kterém je těleso zahřáté na vysokou teplotu postupně ochlazováno, čímž se odstraňují vnitřní defekty tělesa. Vlivem vysoké teploty se částice látky v tělese náhodně uspořádají, tím se defekty krystalické mřížky zahladí a postupným ochlazováním pak částice ustalujeme do rovnovážných poloh spolu s poklesem pravděpodobnosti vzniku defektů nových.

Představme si, že argument optimalizované funkce jednoznačně určuje makrostav nějakého termodynamického systému o energii rovné funkční hodnotě, pak můžeme vyjádřit jeho termodynamickou pravděpodobnost:

$P(E_{i})=|\{x\in {\mathbb {R} }^{n}|f(x)=E_{i}\}|$

jako počet jemu odpovídajících mikrostavů. Ponoříme-li uvedený systém nabývající různých makrostavů o energiích $E_{i}$ do tepelné lázně o energii $E_{0}$, pak dle Boltzmannovy rovnice, pro jednotkovou velikost Boltzmannovy konstanty, pomocí Taylorova rozvoje diferencovatelné funkce můžeme po vyrovnání teplot vyjádřit pro $E=E_{0}+E_{i}=const$ a $E>>E_{i}$ entropii lázně:

$S\left(E_{i}\right)=\ S\left(E\right)-{\frac {dS\left(E\right)}{dE_{i}}}E_{i}={\mathrm {ln} P(E-E_{i}\ })$

a dále užitím definice teploty $dS(E)/dE=\left(1/T\right)$ pro $T>0$ vyjádříme termodynamickou pravděpodobnost makrostavu tepelné lázně jako funkci energie makrostavu vloženého systému, tj. pomocí Boltzmannova faktoru :

$P\left(E-E_{i}\right)=ce^{-\ {\frac {E_{i}}{T}}}$

Algoritmus simulovaného žíhání spočívá v perturbaci kandidáta na optimum a následném rozhodnutí o jeho nahrazení perturbací v každé iteraci algoritmu dle Metropolisova kritéria:

$p\left({x}_{i}\to {x}_{j}\right)={\frac {P(E_{j})}{P(E_{i})}}=e^{-\ {\frac {\Delta E}{T}}}\ \ \ \ \ \ \ \ \ \ \Delta E>0$

$p\left({x}_{i}\to {x}_{j}\right)=1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Delta E\leq 0$

vyjadřujícího pravděpodobnost přechodu systému z jednoho makrostavu do druhého, kde $\Delta E=E_{j}-E_{i}$ a $\Delta E/T$ vyjadřuje přírůstek entropie, tj. v souladu s druhou větou termodynamickou nemožný jev je v uvedeném kritériu uměle předefinován na jev jistý. Posloupnost akceptovaných perturbací, tj. přípustných řešení optimalizační úlohy, tvoří Markovův řetězec s pamětí řádu jedna, tj. výskyt daného řešení je podmíněn pouze výskytem řešení předcházejícího. Perturbace ležící mimo oblast přípustných řešení se zamítají automaticky.

pravděpodobnost přechodu systému z jednoho makrostavu do druhého v závislosti na přírůstku optimalizované funkce a teplotě

Ze závislosti $p(\Delta f)$ je zřejmé, že výrazně „horší“ řešení se akceptuje vůči předcházejícímu řešení s mnohem menší pravděpodobností než řešení jen o málo „horší“. Závislost $p(T)$ lze užít k řízení pravděpodobnosti akceptace řešení během iteračního cyklu. Iterační cyklus startujeme s tak vysokou teplotou, aby se po jistou dobu akceptovalo téměř každé navržené řešení, což případně umožní počáteční aproximaci řešení „vyklouznout“ z oblasti mělkých lokálních minim, ke konci iteračního cyklu naopak teplotu dostatečně snížíme tak, aby se neakceptovalo téměř žádné „horší“ řešení, tj. během iteračního cyklu chladíme systém představující optimalizační úlohu z dostatečně vysoké teploty na dostatečně nízkou teplotu tak, že nám v závěru cyklu řešení „zamrzne“ v dostatečně hlubokém lokálním minimu. Pokles teploty může být zvolen např. jako exponenciální:

$T=T_{0}e^{-\ {\frac {iter}{\tau }}}\ \ \ \ \ \ \ \ \ \ \tau =-{\frac {N}{\mathrm {ln} ({T_{\infty }}/{T_{0}})\ }}\ \ \ \ \ \ \ \ \ \ T_{\infty }\approx {\mathop {\mathrm {lim} } _{iter\to \infty }T_{0}e^{-\ {\frac {iter}{\tau }}}\ }=0$

kde $T_{0}$ resp. $T_{\infty }$ je počáteční resp. konečná teplota a $N$ je počet iterací algoritmu.

Výběr parametrů

Před užitím metody simulovaného žíhání na konkrétní optimalizační problém je třeba určit následující: předpis optimalizované funkce, omezující podmínky, postup perturbace kandidáta na optimum, pravděpodobnost přijetí perturbace na místo výchozího kandidáta, plán žíhání spočívající v naladění počáteční a konečné teploty včetně způsobu jejího poklesu během iteračního cyklu a počet iterací. Tyto volby mohou mít významný dopad na efektivitu metody. Bohužel neexistuje žádný obecný způsob, jak výše uvedené pro konkrétní problém určit. V následujících částech je uvedeno několik obecných pokynů.

Základní iterace

V každém iteračním kroku simulovaného žíhání proběhne výběr sousedního stavu (perturbace) stavu současného (kandidát) a rozhodne se o jeho případném přijetí. Tento krok se opakuje, dokud se nedosáhne dostatečné kvality současného kandidáta, tj. řešení optimalizační úlohy, nebo dokud není vyčerpán daný počet iterací.

Perturbace řešení

Perturbace řešení zahrnuje problém výběru sousedních stavů, což jsou nové stavy produkované nevelkou změnou daného stavu. Například v problému obchodního cestujícího je každý stav obvykle definován jako permutace měst, která mají být navštívena, a sousedé jakéhokoli stavu jsou množinou permutací vytvořených prohozením jakýchkoli dvou z těchto měst. Dobře definovaný způsob, jakým jsou stavy prohazovány, aby vytvářely sousední stavy, se nazývá "pohyb" a různé pohyby poskytují různé sady sousedních stavů. Tyto kroky obvykle vedou k minimálním změnám posledního stavu, ve snaze o postupné vylepšování řešení iterativním vylepšováním jeho částí (například městská spojení v problému obchodního cestujícího).

Konvenční algoritmy jako gradientní sestup, které se pohybují hledáním jednoho lepšího souseda za druhým, se zastaví, když dosáhnou řešení, které nemá lepší sousedy, nemohou zaručit, že dosáhnou globálního optima, ale pouze lokálního optima. Heuristiky používají sousedy řešení jako způsob, jak prozkoumat prostor řešení, a přestože dávají přednost lepším sousedům, přijímají také horší sousedy, aby se vyhnuli uvíznutí v lokálních optimech, tak mohou najít globální optima, pokud běží dostatečně dlouho.

Dostatečně blízko souseda

Simulované žíhání lze modelovat jako náhodný průchod grafem, jehož vrcholy jsou všechny možné stavy a jejichž hrany jsou kandidátní pohyby. Základním požadavkem na funkci hledání souseda je, že musí na tomto grafu poskytovat dostatečně krátkou cestu od počátečního stavu do jakéhokoli stavu, který může být globálním optimem. Ve výše uvedeném příkladu obchodního cestujícího má například stavový prostor pro $n=20$ měst $n!=2432902008176640000$ stavů; počet sousedů každého vrcholu je $\sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}=190$ hran.

Roku 1990, Moscato a Fontanari a nezávisle Dueck and Scheuer navrhl, aby deterministická aktualizace kandidáta (tj. ta, která není založena na pravidlu pravděpodobnosti přijetí), mohla urychlit proces optimalizace, aniž by to mělo dopad na konečnou kvalitu řešení. Moscato a Fontanari docházejí k závěru, že stochastika aktualizace dle Metropolisova kritéria v simulovaném žíhacím algoritmu nehraje při hledání blízké souseda roli. Místo toho navrhli, že „vyhlazení prostředí optimalizované funkce při vysoké teplotě a postupné definování minim během procesu chlazení jsou základními ingrediencemi pro úspěch simulovaného žíhání“. Metoda se následně popularizovala pod označením "akceptování prahu" kvůli Dueckově a Scheuerově označení. V roce 2001 Franz, Hoffmann a Salamon ukázali, že deterministická aktualizační strategie je skutečně optimální v rámci velké třídy algoritmů, které simulují náhodnou procházku po stavovém prostoru.

Efektivní generování sousedů

Při výběru generátoru sousedů je třeba vzít v úvahu, že po několika iteracích simulovaného žíhacího algoritmu se očekává, že aktuální stav bude mít mnohem nižší energii než náhodný stav. Obecně by tedy měl být generátor vychýlen směrem k pohybům, kde je pravděpodobné, že energie cílového stavu bude podobná energii aktuálního stavu. Tento heuristický algoritmus má tendenci vylučovat "velmi dobré“ pohyby i "velmi špatné“; první možnost je však obvykle mnohem méně častá než druhá, takže heuristika má obecně dobrou účinnost.

U výše uvedeného problému obchodního cestujícího se například očekává, že výměna dvou po sobě jdoucích měst bude mít mírný vliv na změnu energie (délku); vzhledem k tomu, že u výměny dvou libovolných měst je mnohem pravděpodobnější, že výměna prodlouží délku cesty, než ji zkrátí. Očekává se tedy, že generátor prohození sousedních měst bude fungovat lépe než generátor prohození libovolných měst, i když by tento mohl poskytnout poněkud kratší cestu k optimu.

Z uvedeného plyne, že je třeba prohodit sousedy, pro které pro akceptační funkci $p(\Delta E,T)$ platí, že $\Delta E$ je menší než $T$. Ve výše uvedeném příkladu obchodního cestujícího by tedy bylo možné použít generátor, který prohodí dvě náhodná města, kde pravděpodobnost výběru dvojice měst klesne, jak jejich vzdálenost překročí $T$.

Pravděpodobnost přechodu

Pro zkoumání chování simulovaného žíhání u konkrétního problému může být užitečné vzít v úvahu "pravděpodobnosti přechodu“, které vyplývají z různých konstrukčních možností provedených při implementaci algoritmu. Tato pravděpodobnost závisí na aktuální teplotě, na pořadí, ve kterém se pohyby kandidátů generují, a na funkci pravděpodobnosti přijetí. (Všimněte si, že pravděpodobnost přechodu není "jednoduše“ $p(\Delta E,T)$, protože kandidáti jsou testováni sériově.)

Metropolisovo kritérium přijetí je povrchně ospravedlněno analogií s přechody termodynamického systému; odpovídá Metropolisovu–Hastingsovu algoritmu v případě, že $T=1$ a Metropolisovo–Hastingsovo návrhové rozdělení je symetrické. Tato pravděpodobnost přijetí se však často používá pro simulované žíhání, i když distribuční funkce, která je analogická návrhovému rozdělení Metropolis–Hastings není symetrická. Výsledkem je, že pravděpodobnosti přechodu algoritmu simulovaného žíhání neodpovídají přechodům analogického fyzikálního systému a dlouhodobé rozdělení stavů při konstantní teplotě nemusí být nijak podobné distribuci termodynamické rovnováhy ve stavech fyzikálního systému při jakékoli teplotě. Většina popisů simulovaného žíhání nicméně předpokládá původní akceptační funkci, která je pravděpodobně zakódována v mnoha implementacích SA.

Plán žíhání

Rychlé

Pomalé

Příklad ilustrující vliv plánu chlazení na výkon simulovaného žíhání. Problémem je změnit uspořádání pixelů v obrazu tak, aby se minimalizovala určitá funkce potenciální energie, což způsobí, že podobné barvy přitahují na krátkou vzdálenost a odpuzují na mírně větší vzdálenost . Elementární pohyby vymění dva sousední pixely. Tyto snímky byly získány s rychlým plánem chlazení (vlevo) a plánem pomalého chlazení (vpravo), čímž byly získány výsledky podobné amorfním a kristalickým strukturám.

Název a inspirace algoritmu vyžadují zajímavou vlastnost související s kolísáním teploty, která má být vložena do provozních parametrů algoritmu. To vyžaduje postupné snižování teploty v průběhu simulace. Algoritmus začíná zpočátku s teplotou nastavenou na vysokou hodnotu a poté se v každém kroku snižuje podle nějakého "žíhacím plánu“, který může uživatel určit, ale musí končit s teplotou blížící se nule. Tímto způsobem se očekává, že se systém bude pohybovat zpočátku směrem k široké oblasti stavového prostoru obsahujícího dobré řešení, ignorující lokální optima energetické funkce a padající do stále se zužující oblasti globálního optima podle heuristiky gradientního sestupu.

Pro jakýkoli daný konečný problém se pravděpodobnost, že algoritmus skončí řešením v globálním optimu, blíží jedné, ovšem pro počet iterací blížící se nekonečnu. Tento teoretický výsledek však není příliš užitečný, protože doba potřebná k nalezení globálního optima obvykle přesáhne dobu řešení problému hrubou silou.

Fyzikální analogie simulovaného žíhání předpokládá, že rychlost ochlazování je dostatečně nízká na to, aby rozdělení pravděpodobnosti současného stavu bylo vždy blízko termodynamické rovnováze. Bohužel doba relaxace potřebná k obnovení rovnováhy během ochlazování silně závisí na „topografii“ optimalizované funkce. V žíhacím algoritmu závisí doba relaxace také na generátoru kandidátů, a to velmi komplikovaným způsobem. Všimněte si, že všechny tyto parametry jsou obvykle žíhacímu algoritmu poskytovány jako černá skříňka. Ideální rychlost chlazení proto nelze určit předem a měla by být empiricky upravena pro každý problém. Adaptivní simulované žíhání řeší tento problém spojením plánu chlazení s postupem hledání optima. Další adaptivní přístup jako Termodynamické simulované žíhání, automaticky upravuje teplotu v každém kroku na základě rozdílu energie mezi těmito dvěma stavy podle zákonů termodynamiky.

Vyhýbání se překážkám

Při výběru generátoru kandidátů je také nutné pokusit se snížit počet "hlubokých“ lokálních minim, které mají mnohem nižší energii než všechny sousední stavy. Takové "uzavřené údolí“ energetické funkce mohou zachytit žíhací algoritmus s vysokou pravděpodobností a po velmi dlouhou dobu. Zpravidla je nemožné navrhnout generátor kandidátů, který splní tento cíl a také upřednostní kandidáty s podobnou energií. Na druhou stranu lze často výrazně zlepšit účinnost simulovaného žíhání pomocí relativně jednoduchých změn v generátoru. Například v problému obchodního cestujícího není těžké vytvořit dvě cesty $A$, $B$ s téměř stejnou délkou tak, že 1) $A$ je optimální, 2) každá sekvence prohození párů stavů, která převádí $A$ na $B$, prochází cestami, které jsou mnohem delší než obě cesty, a 3) $A$ lze převést na $B$ převrácením (obrácením pořadí) sady po sobě jdoucích stavů. V tomto příkladu leží $A$ a $B$ v různých "údolích“, pokud generátor provádí pouze náhodné výměny párů; ale budou ve stejném údolí, pokud generátor provede náhodné převrácení segmentu.

Příklad

Simulované žíhání hledající maximum. Cílem je dosáhnout nejvyššího bodu; nestačí však použít jednoduchý gradientní algoritmus, jelikož je mnoho lokálních maxim. Pomalým ochlazením teploty je nalezeno globální maximum.

Související články

• Genetický algoritmus

Externí odkazy

• Obrázky, zvuky či videa k tématu Simulované žíhání na Wikimedia Commons