Genetický algoritmus je adaptivní heuristický vyhledávací algoritmus inspirovaný 'Darwinovou evoluční teorií v přírodě .' Používá se k řešení optimalizačních problémů ve strojovém učení. Je to jeden z důležitých algoritmů, protože pomáhá řešit složité problémy, jejichž řešení by trvalo dlouho.
Genetické algoritmy jsou široce používány v různých aplikacích reálného světa, např. Navrhování elektronických obvodů, prolamování kódu, zpracování obrazu a umělá kreativita.
V tomto tématu si podrobně vysvětlíme Genetický algoritmus, včetně základní terminologie používané v Genetickém algoritmu, jak funguje, výhody a omezení genetického algoritmu atd.
Co je to genetický algoritmus?
Než porozumíme genetickému algoritmu, pojďme nejprve pochopit základní terminologii, abychom lépe porozuměli tomuto algoritmu:
Po výpočtu zdatnosti každého existujícího v populaci je použit selekční proces k určení, která z individualit v populaci se dostane k reprodukci a produkci semene, které bude tvořit nadcházející generaci.
java long to string
Dostupné typy stylů výběru
Nyní tedy můžeme definovat genetický algoritmus jako heuristický vyhledávací algoritmus pro řešení optimalizačních problémů. Je to podmnožina evolučních algoritmů, která se používá ve výpočetní technice. Genetický algoritmus využívá k řešení optimalizačních problémů koncepty genetického a přirozeného výběru.
Jak funguje genetický algoritmus?
Genetický algoritmus pracuje na evolučním generačním cyklu a vytváří vysoce kvalitní řešení. Tyto algoritmy používají různé operace, které buď rozšiřují nebo nahrazují populaci, aby poskytly lepší řešení přizpůsobení.
V zásadě zahrnuje pět fází řešení složitých optimalizačních problémů, které jsou uvedeny níže:
1. Inicializace
Proces genetického algoritmu začíná generováním množiny jedinců, která se nazývá populace. Zde je řešením daného problému každý jednotlivec. Jedinec obsahuje nebo je charakterizován souborem parametrů nazývaných geny. Geny jsou spojeny do řetězce a generují chromozomy, což je řešení problému. Jednou z nejpopulárnějších technik inicializace je použití náhodných binárních řetězců.
2. Zadání fitness
Fitness funkce se používá k určení, jak je jedinec fit? Znamená schopnost jedince konkurovat ostatním jedincům. V každé iteraci jsou jednotlivci hodnoceni na základě jejich fitness funkce. Funkce fitness poskytuje každému jednotlivci skóre fitness. Toto skóre dále určuje pravděpodobnost, že bude vybrán pro reprodukci. Čím vyšší je skóre zdatnosti, tím větší je šance na výběr pro reprodukci.
3. Výběr
Fáze výběru zahrnuje výběr jedinců pro reprodukci potomstva. Všichni vybraní jedinci jsou pak uspořádáni do páru po dvou, aby se zvýšila reprodukce. Poté tito jedinci přenesou své geny na další generaci.
K dispozici jsou tři typy metod výběru, kterými jsou:
- Výběr ruletového kola
- Výběr turnaje
- Výběr na základě pořadí
4. Reprodukce
Po výběrovém procesu dochází v reprodukčním kroku ke stvoření dítěte. V tomto kroku genetický algoritmus používá dva operátory variací, které jsou aplikovány na rodičovskou populaci. Dva operátoři zapojení do reprodukční fáze jsou uvedeni níže:
- Překročení jednoho bodu
- Dvoubodové křížení
- Livrejový crossover
- Křížení dědičných algoritmů
Geny rodičů se mezi sebou vyměňují, dokud není splněn bod křížení. Tito nově vygenerovaní potomci se přidávají do populace. Tento proces se také nazývá křížení. Dostupné typy crossover stylů:
Operátor mutace vloží náhodné geny do potomků (nové dítě), aby byla zachována diverzita v populaci. Lze to provést převrácením některých bitů v chromozomech.
Mutace pomáhá při řešení problému předčasné konvergence a zvyšuje diverzifikaci. Níže uvedený obrázek ukazuje proces mutace:
Dostupné typy mutačních stylů,
5. Ukončení
Po fázi reprodukce se jako základ pro ukončení použije kritérium zastavení. Algoritmus se ukončí po dosažení prahového fitness řešení. Identifikuje konečné řešení jako nejlepší řešení v populaci.
Obecný pracovní postup jednoduchého genetického algoritmu
Výhody genetického algoritmu
- Nejlepší jsou paralelní schopnosti genetických algoritmů.
- Pomáhá při optimalizaci různých problémů, jako jsou diskrétní funkce, problémy s více cíli a spojité funkce.
- Poskytuje řešení problému, které se časem zlepšuje.
- Genetický algoritmus nepotřebuje odvozenou informaci.
Omezení genetických algoritmů
- Genetické algoritmy nejsou efektivní algoritmy pro řešení jednoduchých problémů.
- Nezaručuje kvalitu konečného řešení problému.
- Opakovaný výpočet hodnot zdatnosti může způsobit určité výpočetní problémy.
Rozdíl mezi genetickými algoritmy a tradičními algoritmy
- Vyhledávací prostor je soubor všech možných řešení problému. V tradičním algoritmu je zachována pouze jedna sada řešení, zatímco v genetickém algoritmu lze použít několik sad řešení ve vyhledávacím prostoru.
- Tradiční algoritmy potřebují více informací, aby mohly provést vyhledávání, zatímco genetické algoritmy potřebují pouze jednu objektivní funkci pro výpočet zdatnosti jednotlivce.
- Tradiční algoritmy nemohou fungovat paralelně, zatímco genetické algoritmy mohou fungovat paralelně (výpočet zdatnosti individualit je nezávislý).
- Jeden velký rozdíl v genetických algoritmech spočívá v tom, že dědičné algoritmy pracují přímo na výsledcích hledačů, ale na jejich reprezentacích (nebo vykreslování), často označovaných jako chromozomy.
- Jedním z velkých rozdílů mezi tradičním algoritmem a genetickým algoritmem je to, že nepracuje přímo s kandidátskými řešeními.
- Tradiční algoritmy mohou nakonec generovat pouze jeden výsledek, zatímco genetické algoritmy mohou generovat více optimálních výsledků z různých generací.
- Tradiční algoritmus pravděpodobně negeneruje optimální výsledky, zatímco genetické algoritmy nezaručují generování optimálních globálních výsledků, ale také existuje velká možnost získání optimálního výsledku pro problém, protože používá genetické operátory, jako je Crossover a Mutation.
- Tradiční algoritmy jsou ve své podstatě deterministické, zatímco genetické algoritmy jsou svou povahou pravděpodobnostní a stochastické.