Simulované žíhá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 provádíme i změny k horšímu, velké hlavně zpočátku, 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 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ě a nepřímo na velikosti zhoršení. V průběhu výpočtu algoritmu je teplota postupně snižována na základě rychlosti konvergence (přibližování se cíli). Pokud algoritmus konverguje rychle (hodnocení stavů rychle klesá), snižuje se teplota také rychle a algoritmu je tak bráněno pokračovat do hůře hodnoceného stavu. Konverguje-li algoritmus pomalu (hodnocení stavů moc neklesá), zpomalí se snižování teploty, aby se případně podařilo vyprostit z lokálního minima.

Pokud nejsme spokojeni s výsledkem, tak teplotu lze i zvyšovat. Potom pravděpodobnost, že bude algoritmus pokračovat do hůře hodnoceného stavu také stoupá, jestliže se algoritmu nedaří (neustálým pokračováním do co nejlépe hodnocených stavů) přibližovat se cíli.

Algoritmus nezaručuje nalezení globálního minima. Pro zlepšení výsledků algoritmus můžeme pustit několikrát z různých, například náhodných, počátečních stavů.