Genetické algoritmy (GA) jsou založeny na evolučním přístupu k umělé inteligenci, kde se využívají metody evoluce populace k nalezení optimálního řešení daného problému. Byly navrženy v roce 1975 Johnem Henry Hollandem.
Genetické algoritmy vycházejí z následujících myšlenek:
- Platná řešení problému lze reprezentovat jako geny
- Pomocí křížení lze kombinovat dvě řešení a získat nové platné řešení
- Selektivní výběr se používá k výběru optimálnějších řešení pomocí nějaké fitness funkce
- Mutace se zavádějí, aby destabilizovaly optimalizaci a pomohly nám dostat se z lokálního minima
Pokud chcete implementovat genetický algoritmus, potřebujete následující:
- Najít způsob kódování řešení problému pomocí genů g∈Γ
- Na množině genů Γ definovat fitness funkci fit: Γ→R. Menší hodnoty funkce odpovídají lepším řešením.
- Definovat mechanismus křížení, který kombinuje dva geny a vytváří nové platné řešení crossover: Γ2→Γ.
- Definovat mechanismus mutace mutate: Γ→Γ.
V mnoha případech jsou algoritmy pro křížení a mutace poměrně jednoduché a manipulují s geny jako s číselnými sekvencemi nebo bitovými vektory.
Konkrétní implementace genetického algoritmu se může případ od případu lišit, ale obecná struktura je následující:
- Vyberte počáteční populaci G⊂Γ
- Náhodně vyberte jednu z operací, která bude v tomto kroku provedena: křížení nebo mutace
- Křížení:
- Náhodně vyberte dva geny g1, g2 ∈ G
- Spočítejte křížení g=crossover(g1,g2)
- Pokud fit(g)<fit(g1) nebo fit(g)<fit(g2), nahraďte odpovídající gen v populaci genem g.
- Mutace - náhodně vyberte gen g∈G a nahraďte jej mutate(g)
- Opakujte od kroku 2, dokud nedosáhnete dostatečně malé hodnoty fit, nebo dokud nebude dosažen limit počtu kroků.
Úlohy, které se obvykle řeší pomocí genetických algoritmů, zahrnují:
- Optimalizace rozvrhů
- Optimální balení
- Optimální řezání
- Zrychlení vyčerpávajícího prohledávání
Pokračujte ve studiu v následujících noteboocích:
Přejděte na tento notebook, kde najdete dva příklady použití genetických algoritmů:
- Spravedlivé rozdělení pokladu
- Problém 8 dam
Genetické algoritmy se používají k řešení mnoha problémů, včetně logistiky a vyhledávacích problémů. Tato oblast je inspirována výzkumem, který spojil témata psychologie a informatiky.
"Genetické algoritmy jsou jednoduché na implementaci, ale jejich chování je obtížné pochopit." zdroj Proveďte výzkum a najděte implementaci genetického algoritmu, například pro řešení sudoku, a vysvětlete, jak funguje, formou náčrtu nebo diagramu.
Podívejte se na toto skvělé video, které ukazuje, jak se počítač může naučit hrát Super Mario pomocí neuronových sítí trénovaných genetickými algoritmy. O tom, jak se počítače učí hrát hry, se dozvíme více v další sekci.
Vaším cílem je vyřešit tzv. Diofantickou rovnici - rovnici s celočíselnými kořeny. Například uvažujme rovnici a+2b+3c+4d=30. Musíte najít celočíselné kořeny, které tuto rovnici splňují.
Tento úkol je inspirován tímto článkem.
Tipy:
- Můžete uvažovat kořeny v intervalu [0;30]
- Jako gen zvažte použití seznamu hodnot kořenů
Použijte Diophantine.ipynb jako výchozí bod.