Nejčastější dotazy

Genetické algoritmy (GA) jsou metody prohledávání a optimalizace inspirované biologickou evolucí. Udržují populaci kandidátních řešení a zlepšují ji přes generace pomocí tří operátorů: selekce (výběr nejlepších jedinců), křížení (kombinování dvou řešení) a mutace (náhodná úprava řešení). GA jsou obzvláště účinné, když je prohledávací prostor rozsáhlý, složitý nebo špatně popsaný.

Genetické algoritmy jsou vhodné pro optimalizační a vyhledávací problémy, kde je třeba najít nejlepší řešení z velkého množství možností. Příklady zahrnují plánování tras (problém obchodního cestujícího), rozvrhování, inženýrský návrh, optimalizaci funkcí a strategii her. Jsou zvláště užitečné, když funkce fitness není diferencovatelná nebo nemá analytické řešení.

Ne. Tutoriál vysvětluje koncepty krok za krokem s diagramy a interaktivními ukázkami v prohlížeči. Nejsou potřeba žádné programátorské znalosti. Pokud chcete implementovat vlastní GA, základní programátorské dovednosti pomohou, ale pro pochopení látky nejsou nutné.

Gradientní metody sledují sklon funkce fitness a mohou uvíznout v lokálním optimu. Genetické algoritmy prohledávají prostor s celou populací současně a jsou méně náchylné k uvíznutí — jsou však obecně pomalejší a výpočetně náročnější. GA nevyžadují, aby funkce fitness byla diferencovatelná nebo spojitá, což je umožňuje použít na širší třídu problémů.

Nejsou žádná univerzální pravidla, ale empirická doporučení jsou: velikost populace 20–100, pravděpodobnost křížení 80–95 %, pravděpodobnost mutace 0,5–1 %. Správné hodnoty závisí na konkrétním problému a kódování. Kapitola Parametry popisuje možnosti podrobněji a interaktivní demo umožňuje přímé experimentování.

Ne. Genetické algoritmy jsou heuristiky — hledají dobrá řešení, ale nemohou zaručit nalezení globálního optima. Kvalita výsledků velmi závisí na volbě kódování, funkce fitness a parametrů. Pro mnohé reálné problémy je téměř optimální řešení nalezené rychle praktičtější než přesné řešení, jehož výpočet by trval příliš dlouho.

Problém obchodního cestujícího (TSP) hledá nejkratší trasu, která navštíví množinu měst přesně jednou a vrátí se na start. Je to klasický NP-těžký kombinatorický optimalizační problém. TSP je v tutoriálu použit k demonstraci permutačního kódování a ukázce toho, jak GA zvládají kombinatorické problémy. Viz kapitola o TSP.

Text a obrázky v tomto tutoriálu jsou zveřejněny pod licencí Creative Commons Attribution–ShareAlike 4.0 (CC BY-SA 4.0). Můžete je volně sdílet a upravovat za podmínky, že uvedete příslušné autorství a budete šířit úpravy pod stejnou licencí.

Interaktivní JavaScriptové demonstrace lze používat pouze jako součást tohoto webu; jakékoli jiné použití vyžaduje předchozí písemný souhlas. Kontakt: marek@obitko.com.