Simulované žíhání

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Simulované žíhání (simulované ochlazování, anglicky Simulated annealing, SA) je pravděpodobnostní optimalizační metoda prohledávání stavového prostoru založená na simulaci žíhání oceli. 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. Algoritmus pracuje s pouze s jedním kandidátním řešením. Obyčejný gradientní algoritmus přijímá nové řešení pouze pokud je lepší než řešení stávající. Při simulovaném žíhání jsou s určitou pravděpodobností přijímána i řešení horší. Pravděpodobnost přijetí i horšího řešení je přímo závislá na teplotě. 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.