PA081: Programování numerických
výpočtů
A. Křenek
Fyzikální
PA081: Programování numerických výpočtů
Algoritmus
Simplexová metoda
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~é
► 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~é
► 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 Eo do Et
Pi = mm{e   w ,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
► 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ě
Modifikovaná simplexová metoda
Fyzikální
► různé strategie chlazení
► snížení T na T(l - e po každých m krocích
► snížení na Tb(l - k/K) po m krocích
k, K jsou počty provedených/plánovaných kroků
► a další...
Algoritmus
Simplexová metoda
► restart metody
► některý vrchol simplexu je nahrazen dosavadním nejlepším bodem
► nesmí být uvnitř
7/8
Simulované žíhání - shrnutí
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í
Fyzikální
Algoritmus
Simplexová metoda
8/8