Simulované žíhání
Simulované žíhání (Simulated Annealing, SA) je inspirováno procesem žíhání kovu – postupným ochlazováním a ustálením na stabilní konfiguraci. V optimalizaci to znamená, že algoritmus občas přijme i horší řešení, aby unikl lokálním minimům, a postupně snižuje tuto pravděpodobnost.
- Efektivní u problémů s mnoha lokálními minimy.
- Jednoduchá implementace a pochopitelný princip.
- Nevyžaduje složitou paměťovou strukturu.
- Funguje dobře při jemném dolaďování řešení.
Zajímavosti a praktická využití
- Používá se v dopravních systémech a rozvrhování výroby.
- Oblíbené u systémů plánování rozvozu s omezeným časem výpočtu.
- Základ pro hybridní adaptivní algoritmy (např. s ALNS).
Omezení a limity
Kvalita výsledků závisí na dobře nastaveném „rozvrhu chlazení“ – pokud je ochlazování příliš rychlé, algoritmus zamrzne ve špatném řešení. Pokud příliš pomalé, prodlužuje výpočetní čas. SA je také náchylné k přílišným oscilacím v prvních fázích.
Shrnutí
Simulované žíhání je elegantní a výkonný nástroj pro prohledávání složitých prostorů řešení. Umožňuje najít vyvážené řešení mezi náhodností a strukturou a je výborným vstupem do metaheuristického myšlení.
Zdroje:
[1] Doležal, J., & Fiala, P. (2012). Operační výzkum: Příklady a úlohy. Praha: Oeconomica.
[2] Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671–680.
[3] Toth, P., & Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications. SIAM.
Důležité odkazy
Kontakt
List Title
- kvetapapouskova@gmail.com
- Univerzitní 22, 306 14 Plzeň