Úvod do genetických algoritmů ve strojovém učení

introduction genetic algorithms machine learning

jak udělat hromadu v Javě

Tento výukový program Genetický algoritmus podrobně vysvětluje, co jsou genetické algoritmy a jejich role ve strojovém učení :

V Předchozí tutoriál , jsme se dozvěděli o modelech umělých neuronových sítí - vícevrstvý Perceptron, Backpropagation, Radial Bias & Kohonen Self Organizing Maps včetně jejich architektury.

Zaměříme se na genetické algoritmy, které přišly dříve, než Neural Networks, ale nyní GA převzala NN. Přestože GA stále má aplikace v reálném životě, jako jsou problémy s optimalizací, jako je plánování, hraní her, robotika, design hardwaru, problémy obchodního cestujícího atd.

Genetické algoritmy jsou algoritmy, které jsou založeny na evoluční myšlence přirozeného výběru a genetiky. GA jsou adaptivní heuristické vyhledávací algoritmy, tj. Algoritmy sledují iterativní vzorec, který se mění s časem. Jedná se o typ posilovacího učení, kdy je zpětná vazba nezbytná, aniž by byla uvedena správná cesta, po které se má vydat. Zpětná vazba může být pozitivní nebo negativní.

=> Přečtěte si celou sérii školení o strojovém učení

Co se naučíte:

• Proč používat genetické algoritmy
  • Biologické pozadí genetických algoritmů
• Co jsou genetické algoritmy
  • Korelace chromozomu s GA
  • Důležitá terminologie v GA
  • Jednoduchý genetický algoritmus
  • Metoda výběru ruletového kola
  • Další metody výběru
  • Crossover
  • Mutace
  • Kdy zastavit genetický algoritmus
• Výhody a nevýhody genetického algoritmu
• Aplikace genetických algoritmů
• Závěr
  • Doporučené čtení

Proč používat genetické algoritmy

GA jsou robustnější algoritmy, které lze použít pro různé optimalizační problémy. Na rozdíl od jiných algoritmů AI se tyto algoritmy v přítomnosti šumu snadno neodchylují. GA lze použít při hledání velkého prostoru nebo multimodálního prostoru.

Biologické pozadí genetických algoritmů

Genetika je odvozena z řeckého slova „genesis“, což znamená růst. Genetika rozhoduje o faktorech dědičnosti, podobnosti a rozdílech mezi potomky v procesu evoluce. Genetické algoritmy jsou také odvozeny z přirozeného vývoje.

Některé terminologie v biologickém chromozomu

• Chromozomy: Veškerá genetická informace o druhu jsou uložené chromozomy.
• Geny: Chromozomy jsou rozděleny do několika částí zvaných geny.
• Alely: Geny identifikují charakteristiku jedince. Možnost kombinace genů pro vytvoření vlastnosti se nazývá Alleles. Gen může mít různé alely.
• Gene Pool: Všechny možné kombinace genů, které jsou všechny alelami v populačním fondu, se nazývají genové fondy.
• Genom: Soubor genů druhu se nazývá genom.
• Místo: Každý gen má pozici v genomu, který se nazývá lokus.
• Genotyp: Plná kombinace genů u jedince se nazývá genotyp.
• Fenotyp: Soubor genotypů v dekódované formě se nazývá fenotyp.

Co jsou genetické algoritmy

Genetické algoritmy stimulují proces jako v přirozených systémech evoluce. Charles Darwin uvedl evoluční teorii, že v přirozené evoluci se biologické bytosti vyvíjejí podle principu „přežití nejschopnějších“. Hledání GA je navrženo tak, aby podporovalo teorii „přežití nejschopnějších“.

GA provedou náhodné hledání, aby vyřešily problémy s optimalizací. GA používá techniky, které používají předchozí historické informace k nasměrování svého hledání k optimalizaci v novém vyhledávacím prostoru.

Korelace chromozomu s GA

Lidské tělo má chromozomy, které jsou vyrobeny z genů. Soubor všech genů konkrétního druhu se nazývá genom. U živých bytostí jsou genomy uloženy v různých chromozomech, zatímco v GA jsou všechny geny uloženy ve stejném chromozomu.

Srovnání mezi přirozenou evolucí a terminologií genetického algoritmu

Důležitá terminologie v GA

• Počet obyvatel: Je to skupina jednotlivců. Populace zahrnuje počet testovaných jedinců, informace o prostoru vyhledávání a parametry fenotypu. Obecně je populace náhodně inicializována.
• Jednotlivci: Jednotlivci jsou v populaci jediným řešením. Jedinec má soubor parametrů zvaných geny. Geny se spojily za vzniku chromozomů.
• Geny: Geny jsou stavebními kameny genetických algoritmů. Chromozom je tvořen geny. Geny mohou určovat řešení problému. Jsou reprezentovány bitovým (0 nebo 1) řetězcem s náhodnou délkou.
• Zdatnost: Fitness určuje hodnotu fenotypu problému. Funkce fitness říká, jak blízko je řešení k optimálnímu řešení. Fitness funkce se určuje mnoha způsoby, jako je součet všech parametrů souvisejících s problémem - euklidovská vzdálenost atd. Neexistuje žádné pravidlo pro hodnocení fitness funkce.

Jednoduchý genetický algoritmus

Jednoduchý GA má populaci jednotlivých chromozomů. Tyto chromozomy představují možná řešení. Reprodukční operátoři jsou aplikováni přes tyto sady chromozomů k provedení mutací a rekombinace. Je proto důležité najít vhodné operátory reprodukce, protože chování GA je na něm závislé.

Jednoduchý genetický algoritmus je následující:

# 1) Začněte s náhodně vytvořenou populací.

#dva) Vypočítejte fitness funkci každého chromozomu.

# 3) Opakujte kroky, dokud se nevytvoří n potomků. Potomci jsou vytvořeni, jak je znázorněno níže.

• Vyberte pár chromozomů z populace.
• Crossover dvojice s pravděpodobností str_Ctvořit potomky.
• Mutovat výhybku s pravděpodobností str_m.

# 4) Nahraďte původní populaci novou populací a přejděte ke kroku 2.

Podívejme se na kroky, které následují v tomto procesu iterace. Generuje se počáteční populace chromozomů. Počáteční populace by měla obsahovat dostatek genů, aby bylo možné generovat jakékoli řešení. První skupina populace je generována náhodně.

• Výběr: Nejlepší sada genů je vybrána v závislosti na funkci fitness. Je vybrána struna s nejlepší fitness funkcí.
• Reprodukce: Nová potomstva jsou generována rekombinací a mutací.
• Hodnocení: Nové generované chromozomy jsou hodnoceny z hlediska jejich vhodnosti.
• Výměna, nahrazení: V tomto kroku je stará populace nahrazena nově generovanou populací.

Metoda výběru ruletového kola

Výběr ruletového kola je široce používaná metoda výběru.

Proces výběru je krátký, jak je znázorněno níže:

V této metodě se provádí lineární vyhledávání ruletovým kolem. Štěrbiny v kole jsou zváženy podle individuální hodnoty fitness. Cílová hodnota je stanovena náhodně podle podílu součtu kondice v populaci.

Populace je poté prohledávána, dokud není dosaženo cílové hodnoty. Tato metoda nezaručuje nejschopnější jednotlivce, ale je pravděpodobné, že bude nejschopnější.

Podívejme se na kroky spojené s výběrem ruletového kola.

Očekávaná hodnota jednotlivce = individuální zdatnost / zdatnost populace. Sloty kol jsou přiřazeny jednotlivcům na základě jejich fyzické zdatnosti. Kolo se otáčí Nkrát, kde N je celkový počet jedinců v populaci. Po skončení jedné rotace je vybraný jedinec zařazen do skupiny rodičů.

1. Nechť je celková očekávaná hodnota počtu jedinců v populaci S.
2. Opakujte kroky 3-5 nkrát.
3. Vyberte celé číslo s mezi 0 a S.
4. Procházejte jednotlivci v populaci a sečtěte očekávané hodnoty, dokud není součet větší než s.
5. Je vybrán jedinec, jehož očekávaná hodnota dává součet nad limit s.

Nevýhody výběru ruletového kola:

1. Pokud se kondice velmi liší, bude obvod kola rulety maximálně využíván chromozomem s nejvyšší kondicí, takže ostatní mají velmi malou šanci na výběr.
2. Je to hlučné.
3. Vývoj závisí na rozptylu ve zdatnosti populace.

Další metody výběru

Existuje mnoho dalších metod výběru použitých v 'Výběr' krok genetického algoritmu.

Budeme diskutovat o 2 dalších široce používaných metodách:

# 1) Výběr umístění: V této metodě je každému chromozomu dána hodnota fitness z hodnocení. Nejhorší kondice je 1 a nejlepší kondice je N. Je to metoda pomalé konvergence. V této metodě je zachována rozmanitost vedoucí k úspěšnému hledání.

Vyberou se potenciální rodiče a poté se koná turnaj, který rozhodne o tom, kdo z rodičů bude rodičem.

# 2) Výběr turnaje: V této metodě se na populaci aplikuje strategie selektivního tlaku. Nejlepší jedinec je ten s nejvyšší kondicí. Tento jedinec je vítězem turnajové soutěže mezi jednotlivci Nu v populaci.

Populace turnaje spolu s vítězem se znovu přidává do skupiny, aby se vytvořili nové potomky. Rozdíl ve fitness hodnotách vítěze a jednotlivců v páření poskytuje selektivní tlak pro dosažení optimálních výsledků.

Crossover

Jedná se o proces, kdy se berou 2 jednotlivci a produkuje z nich dítě. Proces reprodukce po výběru vytváří klony dobrých bodnutí. Operátor přechodu je aplikován přes řetězce, aby se vytvořil lepší potomek.

Implementace operátoru přechodu je následující:

1. Z populace jsou náhodně vybráni dva jedinci k produkci potomků.
2. Cross-site je vybrán náhodně po délce řetězce.
3. Hodnoty na webu jsou zaměněny.

Provedené křížení může být jednobodové křížení, dvoubodové křížení, vícebodové křížení atd. Jednobodové křížení má jedno místo křížení, zatímco dvoubodové křížení má 2 místa, kde jsou hodnoty zaměněny.

Vidíme to v níže uvedeném příkladu:

Crossover jednoho bodu

Dvoubodový výhybka

Pravděpodobnost výhybky

P_C, pravděpodobnost křížení je termín, který popisuje, jak často bude křížení provedeno. 0% pravděpodobnost znamená, že nové chromozomy budou přesnou kopií starých chromozomů, zatímco 100% pravděpodobnost znamená, že všechny nové chromozomy budou vytvořeny křížením.

Mutace

Mutace se provádí po přechodu. Zatímco crossover se zaměřuje pouze na aktuální řešení, operace mutace prohledá celý vyhledávací prostor. Tato metoda má obnovit ztracenou genetickou informaci a distribuovat ji.

Tento operátor pomáhá udržovat genetickou rozmanitost v populaci. Pomáhá předcházet místním minimům a brání generování zbytečných řešení od jakékoli populace.

Mutace se provádí mnoha způsoby, například převrácením hodnoty každého genu s malou pravděpodobností nebo mutací provést pouze v případě, že to zlepší kvalitu řešení.

Některé ze způsobů mutace jsou:

• Převrácení: Změna z 0 na 1 nebo z 1 na 0.
• Záměna: Jsou vybrány dvě náhodné polohy a hodnoty jsou zaměňovány.
• Couvání: Je vybrána náhodná pozice a bity vedle ní jsou obráceny.

Podívejme se na několik příkladů každého z nich:

Převrácení

Zaměňovat

Couvání

Pravděpodobnost mutace

P_m, pravděpodobnost mutace je termín, který rozhoduje o tom, jak často budou chromozomy mutovány. Pokud je pravděpodobnost mutace 100%, znamená to, že je změněn celý chromozom. Pokud se mutace neprovede, generují se noví potomci přímo po křížení.

Příklad obecného genetického algoritmu Pravděpodobnost mutace: P_m, pravděpodobnost mutace je termín, který rozhoduje o tom, jak často budou chromozomy mutovány. Pokud je pravděpodobnost mutace 100%, znamená to, že je změněn celý chromozom.

Pokud se mutace neprovede, pak se nový potomek generuje přímo po křížení. Počáteční populace chromozomů je uvedena jako A, B, C, D. Velikost populace je 4.

Funkce fitness je v řetězci brána jako číslo 1.

Součet zdatnosti je 12, což znamená, že průměrná zdatnost by byla ~ 12/4 = 3

Pravděpodobnost křížení = 0,7

Pravděpodobnost mutace = 0,001

# 1) Pokud jsou vybrány B a C, crossover se neprovede, protože hodnota fitness C je pod průměrnou fitness.

#dva) B je mutovaný => B: 11101110 -> B^'': 01101110 k zachování populační rozmanitosti

# 3) Jsou vybrány B a D, provede se křížení.

B: 11101110 E: 10110100 -> D: 00110100 F: 01101110

# 4) Pokud je E mutovaný, pak

E: 10110100 -> E^'': 10110000

Odpovídající chromozomy jsou uvedeny v následující tabulce. Objednávka je zadána náhodně.

Ačkoli je nejzdatnější jedinec s hodnotou fitness 6 ztracen, celková průměrná zdatnost populace se zvyšuje a bude: 14/4 = 3,5

Kdy zastavit genetický algoritmus

Genetický algoritmus je zastaven, pokud jsou splněny níže uvedené podmínky:

# 1) Nejlepší individuální konvergence: Když minimální úroveň fitness klesne pod hodnotu konvergence, algoritmus se zastaví. Vede to k rychlejší konvergenci.

# 2) Nejhorší individuální konvergence: Když nejméně zdatní jedinci v populaci dosáhnou minimální hodnoty kondice pod konvergencí, pak je algoritmus zastaven. V této metodě je v populaci udržován minimální fitness standard. To znamená, že nejlepší jedinec není zaručen, ale budou přítomni jednotlivci s minimální hodnotou kondice.

# 3) Součet fitness: Pokud je v této metodě součet zdatnosti menší nebo roven hodnotě konvergence, je vyhledávání zastaveno. Zaručuje, že celá populace je ve fitness rozsahu.

# 4) Median Fitness: V této metodě bude alespoň polovina jednotlivců v populaci lepší nebo rovna hodnotě konvergence.

Některá kritéria konvergence nebo podmínky zastavení mohou být:

• Když se vyvinul určitý počet generací.
• Po splnění zadaného času pro spuštění algoritmu.
• Když se fitness hodnota populace s iteracemi dále nemění.

Výhody a nevýhody genetického algoritmu

Výhody genetického algoritmu jsou:

1. Má širší prostor pro řešení.
2. Je snazší objevit globální optimum.
3. Rovnoběžnost: Více GA může běžet společně s použitím stejného CPU bez vzájemného rušení. Běží paralelně v izolaci.

Omezení GA:

1. Identifikace fitness funkce je omezení.
2. Konvergence algoritmů může být příliš rychlá nebo příliš pomalá.
3. Existuje omezení výběru parametrů, jako je crossover, pravděpodobnost mutace, velikost populace atd.

Aplikace genetických algoritmů

GA je efektivní při řešení vysoce dimenzionálních problémů. GA se efektivně používá, když je vyhledávací prostor velmi velký, nejsou k dispozici žádné matematické techniky řešení problémů a jiné tradiční vyhledávací algoritmy nefungují.

Některé aplikace, kde se používá GA:

• Problém s optimalizací: Jedním z nejlepších příkladů optimalizačních problémů je problém obchodního cestujícího, který využívá GA. Široce se používají další optimalizační problémy, jako je plánování úloh, GA optimalizace kvality zvuku.
• Model imunitního systému: GA se používají k modelování různých aspektů imunitního systému pro jednotlivé genové a multigenové rodiny během evolučního času.
• Strojové učení: GA byly použity k řešení problémů souvisejících s klasifikací, predikcí, vytvářením pravidel pro učení a klasifikaci .

Závěr

Genetické algoritmy jsou založeny na metodě přirozeného vývoje. Tyto algoritmy se liší od ostatních klasifikačních algoritmů, protože používají kódované parametry (0 nebo 1), v populaci je několik počtů osob a pro konvergenci používají pravděpodobnostní metodu.

S procesem křížení a mutace se GA sbíhají v následujících generacích. Provedení algoritmu GA nezaručuje vždy úspěšné řešení. Genetické algoritmy jsou vysoce účinné při optimalizaci - problémech s plánováním úloh.

Doufám, že tento výukový program by obohatil vaše znalosti o konceptu genetických algoritmů !!

=> Navštivte zde exkluzivní sérii strojového učení

Doporučené čtení

• Modelové testování pomocí genetického algoritmu
• Data Mining vs. Machine Learning vs. Artificial Intelligence vs. Deep Learning
• Výukový program pro strojové učení: Úvod do ML a jeho aplikací
• Druhy strojového učení: Supervised Vs Unsupervised Learning
• Kompletní průvodce umělou neuronovou sítí ve strojovém učení
• 11 nejpopulárnějších softwarových nástrojů pro strojové učení v roce 2021
• Top 13 NEJLEPŠÍCH společností pro strojové učení (aktualizovaný seznam 2021)
• Co je podpora vektorového stroje (SVM) ve strojovém učení