Co je simulované žíhání?

Simulované žíhání je počítačová technika, která dokáže najít dobrá - i když ne nutně optimální - řešení problému. Je pojmenována proto, že napodobuje metalurgický proces žíhání. V kovech je žíhání procesem čištění zahřátím kovu a následným ochlazením. Počítačový program „vyčistí“ prostor řešení, dokud nezůstanou všechna řešení, která jsou nejlepší nebo téměř nejlepší.

Uživatel simulovaného žíhacího programu musí specifikovat dva kritické faktory: počáteční teplotu nebo procento horších řešení, která lze prozkoumat; a rychlost chlazení, což je rychlost, při které je toto procento sníženo. Nízká počáteční teplota často skončí s výsledkem daleko vzdáleným od optima. Zahájení při velmi vysoké teplotě může vést k tomu, že hledání zabere mnohem více času, než je nutné. Podobně bude příliš vysoká rychlost chlazení generovat špatné výsledky, zatímco velmi nízká rychlost chlazení povede k programu, který běží velmi dlouhou dobu.

Stav „vysoké teploty“ pro simulovaný žíhací program je nastavení, které mu umožňuje prohlížet širokou škálu řešení, včetně mnoha, která jsou horší než řešení, která již našla. Počítač smí prohlížet mnoho řešení, která jsou horší než současné řešení, aby se vyhnuly místním minimům, které jsou podstatně horší než ty nejlepší. Jako příklad si můžeme představit začátek na vrcholu kopce nebo hory s cílem dosáhnout základny. Po cestě se mohou vyskytnout vpusti nebo propasti. Pokud počítač nemůže jít do kopce dostatečně daleko, aby se dostal ven, uvízne, i když není nikde blízko základny.

Jak daleko může program jít, je určeno procentem horších řešení, které může program zkoumat. S postupem času se nalézají postupně lepší řešení a snižuje se riziko hlubokých propastů, takže procento horších řešení, která může počítač prozkoumat, se snižuje. Snížení této frakce se označuje jako „chlazení“. Když teplota dosáhne přednastaveného zlomku - který nemusí být 0 - vyhledávání končí.

Důvodem použití simulovaného žíhání nebo jiných technik umělé inteligence je zkrácení času potřebného k nalezení téměř optimálního řešení na zvládnutelné množství. U mnoha problémů by vyčerpávající hledání - testování každého možného řešení proti každému jinému možnému řešení - mohlo trvat měsíce nebo roky. Nejznámější alternativou simulovaného žíhání jsou genetické algoritmy. Mezi další populární algoritmy vyhledávání umělé inteligence patří optimalizace kolonií mravenců, optimalizace rojů částic, nejbližší soused a bayesovští klasifikátoři.