PA081: Programování numerických výpočtů
9. Simulované žíhání
Aleš Křenek
jaro 2011
Fyzikální analogie
► při vysokých teplotách se molekuly volně pohybují
► s poklesem teploty se pohyb zpomaluje
► látky postupně krystalizují
► rychlé schlazení - velké množství malých krystalů
► není to energeticky optimální stav
► nízká teplota nedovoluje přeskupení
► pomalé schlazení - velké krystaly
► kritická je rychlost ochlazování
Fyzikální analogie
► Bolzmanova distribuce pravděpodobnosti
P(E) = e-vr
► i za nízké teploty existuje malá pravděpodobnost dosažení vysoce energetického stavu
► systém může přejít i „nahoru"
Fyzikální analogie
► Bolzmanova distribuce pravděpodobnosti
P(E) = e-vr
► i za nízké teploty existuje malá pravděpodobnost dosažení vysoce energetického stavu
► systém může přejít i „nahoru"
► standardní optimalizační algoritmy
► cesta k nejbližšímu minimu
► odpovídají rychlému chlazení
► mohou minout globální minimum
Původní algoritmus
► Metropolis et al., 1953, simulace termodynamického systému
► v každém kroku se vygeneruje sada možných následníků
► pravděpodobnost změny konfigurace z Eq do Et
Pí = min{e ,1}
► k dalšímu stavu se přejde na základě náhodného výběru
► postupně se snižuje teplota T
Optimalizační algoritmus
► „energie" je minimalizovaná funkce
► stav systému je aktuální aproximace x
► potřebujeme generátor náhodných změn Ax
► nejproblematičtější část
► existuje-li cesta „dolů", měl by ji nabídnout
► různé navržené metody vhodné pro různé problémy
Modifikovaná simplexová metoda
PA081: Programování numerických
výpočtů
A. Křenek
► zachovává operace reflexe, expanze, a kontrakce počítá s modifikovanými funkčními hodnotami
► náhodná funkce, velikost úměrná teplotě T
► přičtená k hodnotě uložené ve vrcholu simplexu
► odečtená od hodnoty v nově zkoušené bodě
► je-li nemodifikovaný krok „dolů", je přijat
► úměrně teplotě jsou někdy přijaty i kroky „nahoru"
► při nenulové teplotě se simplex roztáhne na celou dosažitelnou oblast
► postupným schlazením se zachytí v nejhlubším minimu
► nikoli jistě, pouze pravděpodobně
■O0.O
Modifikovaná simplexová metoda
► různé strategie chlazení
► snížení TnaTfl - e po každých m krocích
► snížení na To (1 - k/K) po m krocích k, K jsou počty provedených/plánovaných kroků
► a další...
► restart metody
► některý vrchol simplexu je nahrazen dosavadním nejlepším bodem
► nesmí být uvnitř
PA081: Programování numerických
výpočtů
A. Křenek
Simulované žíhání - shrnutí
PA081: Programování numerických
výpočtů
A. Křenek
► rozšíření standardních metod o „teplotní" faktor
► využívají náhodný generátor
► nalezení globálního minima pouze s jistou pravděpodobností
► při různé inicializaci různé výsledky
► citlivé na rychlost „chlazení"
► vhodné pro funkce bohaté na lokální minima
► standardní metoda se téměř jistě chytí do pasti
mohou pomoci v případech, kdy neznáme chovaní funkce dopředu
► poslední zoufalý pokus, nikoli univerzální řešení
■O0.O