Evoluční algoritmy jsou schopny přibližně řešit úlohy, jejichž exaktní řešení není v našich výpočetních silách, je extrémně časově náročné anebo vyžaduje lidskou intuici. Tyto algoritmy využívají principů známých z evoluční biologie, zejm. pak Darwinova principu přežití silnějšího.
Namísto toho, aby bylo exaktním nebo randomizovaným algoritmem budováno jedno výsledné řešení problému, je v evolučních algoritmech udržována celá populace kandidujících řešení. Tato řešení jsou posupně šlechtěna, např. po generacích. V každé generaci jsou určitým způsobem vybrána nejlepší řešení a tato řešení jsou pak křížena a mutována.
Tímto principem jsou často nalezena vysoce kvalitní řešení daných problémů – bez nutnosti toho, aby člověk musel vymýšlet specializovaný algoritmus, jak daný problém řešit! Jediné, co algoritmus potřebuje vědět, je, která řešení jsou silnější a která slabší. To je pro celou řadu triviální určit, zatímco vyrobit dobré řešení může být nepřekonatelně obtížné.
V ukázkovém JavaScript appletu níže si můžete vyzkoušet aplikaci genetického algoritmu (jeden z nejznámějších evolučních algoritmů) na problém tzv. minimálního vrcholového pokrytí (minimum vertex cover). Ten můžeme v kontextu mapy Československa interpretovat takto: Ředitelství silnic a dál nic potřebuje zřídit ve větších městech pobočky tak, aby každá větší silnice začínala nebo končila ve městě se zřízenou pobočkou. Je přípustné, aby pobočka byla v obou městech, mezi nimiž silnice vede, ale je zakázáno, aby nějaká silnice nebyla pobočkou pokryta.
Uvedený problém je tzv. NP-úplný, tj. výpočetní čas nezbytný k jeho vyřešení roste exponenciálně s velikostí problému. V případě naší mapky by trvalo až do konce světa, než by bylo optimální řešení nalezeno algoritmem hrubé síly, zkoušejícího všechny kombinace měst. Genetický algoritmus nám však pomůže během chvíle nalézt řešení, které je velmi kvalitní a jen mírně suboptimální.
Spustíte-li algoritmus tlačítkem "Start EA", zobrazí se na mapce v každé generaci nejlepší řešení, které se nachází v populaci. Čím méně modrých měst a oranžových hran, tím je řešení lepší.
| Velikost populace: | |
| Pravděpodobnost křížení: | % |
| Pravděpodobnost mutace: | % |
| Velikost turnaje: | |
Chcete se o evolučních algoritmech dozvědět více či navrhnout algoritmus vlastní? Není nic jednoduššího, než se přihlásit k nám na fakultu a zapsat si předmět BI-ZUM: Základy umělé inteligence!