Úvod do genetických algoritmov v strojovom učení

introduction genetic algorithms machine learning

čo je najlepšie mp3 downloader pre Android

Tento výukový program Genetický algoritmus podrobne vysvetľuje, čo sú genetické algoritmy a ich úloha v strojovom učení. :

V Predchádzajúci návod , dozvedeli sme sa o modeloch umelej neurónovej siete - viacvrstvový Perceptron, Backpropagation, Radial Bias & Kohonen Self Organizing Maps vrátane ich architektúry.

Zameriame sa na genetické algoritmy, ktoré prišli predtým, ako na neurónové siete, teraz však GA prevzala NN. Aj keď GA má stále aplikácie v reálnom živote, ako napríklad problémy s optimalizáciou, ako je plánovanie, hranie hier, robotika, dizajn hardvéru, problémy s cestujúcim predavačom atď.

Genetické algoritmy sú algoritmy, ktoré sú založené na evolučnej myšlienke prírodného výberu a genetiky. GA sú adaptívne heuristické vyhľadávacie algoritmy, t. J. Algoritmy sa riadia iteračným vzorom, ktorý sa časom mení. Je to typ posilňovacieho učenia, pri ktorom je potrebná spätná väzba bez toho, aby bola uvedená správna cesta, po ktorej treba ísť. Spätná väzba môže byť pozitívna alebo negatívna.

=> Prečítajte si celú sériu školení o strojovom učení

Čo sa dozviete:

• Prečo používať genetické algoritmy
  • Biologické pozadie genetických algoritmov
• Čo sú genetické algoritmy
  • Korelácia chromozómu s GA
  • Dôležitá terminológia v GA
  • Jednoduchý genetický algoritmus
  • Metóda výberu ruletového kolesa
  • Ďalšie metódy výberu
  • Crossover
  • Mutácia
  • Kedy zastaviť genetický algoritmus
• Výhody a nevýhody genetického algoritmu
• Aplikácie genetických algoritmov
• Záver
  • Odporúčané čítanie

Prečo používať genetické algoritmy

GA sú robustnejšie algoritmy, ktoré sa dajú použiť na rôzne optimalizačné problémy. Tieto algoritmy sa za prítomnosti šumu ľahko neodchyľujú, na rozdiel od iných algoritmov AI. GA sa dajú použiť pri hľadaní veľkého alebo multimodálneho priestoru.

Biologické pozadie genetických algoritmov

Genetika je odvodená z gréckeho slova „genesis“, čo znamená rásť. O faktoroch dedičnosti, podobnostiach a rozdieloch medzi potomkami v procese evolúcie rozhoduje genetika. Genetické algoritmy sú tiež odvodené z prirodzeného vývoja.

Niektoré terminológie v biologickom chromozóme

• Chromozómy: Všetky genetické informácie o druhu sú uložené chromozómy.
• Gény: Chromozómy sú rozdelené do niekoľkých častí, ktoré sa nazývajú gény.
• Alely: Gény identifikujú charakteristiku jednotlivca. Možnosť kombinácie génov na vytvorenie vlastnosti sa nazýva Alleles. Gén môže mať rôzne alely.
• Génový bazén: Všetky možné kombinácie génov, ktoré sú všetky alelami v populačnom súbore, sa nazývajú genofond.
• Genóm: Súbor génov druhu sa nazýva genóm.
• Zameranie: Každý gén má pozíciu v genóme, ktorá sa nazýva lokus.
• Genotyp: Úplná kombinácia génov u jednotlivca sa nazýva genotyp.
• Fenotyp: Súbor genotypov v dekódovanej podobe sa nazýva fenotyp.

Čo sú genetické algoritmy

Genetické algoritmy stimulujú proces evolúcie ako v prírodných systémoch. Charles Darwin uviedol teóriu evolúcie, podľa ktorej sa v prírodnom vývoji biologické bytosti vyvíjajú podľa princípu „prežitia najsilnejších“. Cieľom hľadania GA je podporiť teóriu „prežitia najschopnejších“.

GA vykonávajú náhodné vyhľadávanie na riešenie problémov s optimalizáciou. GA používa techniky, ktoré využívajú predchádzajúce historické informácie na nasmerovanie svojho vyhľadávania k optimalizácii v novom vyhľadávacom priestore.

Korelácia chromozómu s GA

Ľudské telo má chromozómy, ktoré sú vyrobené z génov. Súbor všetkých génov konkrétneho druhu sa nazýva genóm. U živých bytostí sú genómy uložené v rôznych chromozómoch, zatiaľ čo v prípade GA sú všetky gény uložené v rovnakom chromozóme.

Porovnanie medzi prírodnou evolúciou a terminológiou genetického algoritmu

Dôležitá terminológia v GA

• Populácia: Je to skupina jednotlivcov. Populácia zahŕňa počet testovaných jedincov, informácie o vyhľadávacom priestore a parametre fenotypu. Všeobecne je populácia náhodne inicializovaná.
• Jednotlivci: Jednotlivci sú jediným riešením v populácii. Jednotlivec má súbor parametrov nazývaných gény. Gény sa spojili a vytvorili chromozómy.
• Gény: Gény sú stavebnými kameňmi genetických algoritmov. Chromozóm je tvorený génmi. Riešenie problému môžu určovať gény. Predstavuje ich bitový (0 alebo 1) reťazec náhodnej dĺžky.
• Fitnes: Fitness vyjadruje hodnotu fenotypu problému. Funkcia fitness hovorí, ako blízko je riešenie k optimálnemu riešeniu. Funkcia fitness sa určuje mnohými spôsobmi, napríklad ako súčet všetkých parametrov súvisiacich s problémom - euklidovská vzdialenosť atď. Neexistuje pravidlo na hodnotenie funkcie fitness.

Jednoduchý genetický algoritmus

Jednoduchý GA má populáciu jednotlivých chromozómov. Tieto chromozómy predstavujú možné riešenia. Na vykonávanie týchto mutácií a rekombinácie sa na tieto sady chromozómov používajú operátory reprodukcie. Je preto dôležité nájsť vhodných operátorov reprodukcie, pretože správanie GA od neho závisí.

Jednoduchý genetický algoritmus je nasledovný:

# 1) Začnite s náhodne vytvoreným počtom obyvateľov.

#dva) Vypočítajte fitnesovú funkciu každého chromozómu.

# 3) Kroky opakujte, kým sa nevytvorí n potomkov. Potomkovia sa vytvárajú, ako je to znázornené nižšie.

• Vyberte pár chromozómov z populácie.
• Prekročenie dvojice s pravdepodobnosťou p_ctvoriť potomkov.
• Mutujte výhybku s pravdepodobnosťou str_m.

# 4) Nahraďte pôvodnú populáciu novou populáciou a prejdite na krok 2.

Pozrime sa na kroky, ktoré nasledovali v tomto iteračnom procese. Generuje sa počiatočná populácia chromozómov. Počiatočná populácia by mala obsahovať dostatok génov, aby bolo možné vytvoriť akékoľvek riešenie. Prvá skupina obyvateľstva sa generuje náhodne.

• Výber: Najlepšia skupina génov sa vyberie v závislosti od funkcie fitnes. Vyberá sa struna s najlepšou funkciou fitness.
• Rozmnožovanie: Nové potomstvo sa generuje rekombináciou a mutáciou.
• Hodnotenie: Vygenerované nové chromozómy sa hodnotia z hľadiska ich vhodnosti.
• Výmena: V tomto kroku sa stará populácia nahradí novo generovanou populáciou.

Metóda výberu ruletového kolesa

Výber rulety je metóda výberu, ktorá sa často používa.

Proces výberu je krátky, ako je uvedené nižšie:

Pri tejto metóde sa lineárne prehľadáva ruletovým kolesom. Sloty v kolese sa vážia podľa individuálnej hodnoty zdatnosti. Cieľová hodnota je stanovená náhodne podľa pomeru súčtu kondície v populácii.

Populácia sa potom prehľadáva, kým sa nedosiahne cieľová hodnota. Táto metóda nezaručuje najschopnejších jednotlivcov, ale je pravdepodobné, že budú najschopnejší.

Pozrime sa na kroky spojené s výberom ruletového kolesa.

Očakávaná hodnota jednotlivca = Individuálna zdatnosť / zdatnosť populácie. Otvory pre kolesá sú priradené jednotlivcom na základe ich fyzickej zdatnosti. Koleso sa otáča N-krát, pričom N je celkový počet jedincov v populácii. Po skončení jednej rotácie je vybraný jedinec zaradený do skupiny rodičov.

1. Nech je celková očakávaná hodnota počtu jednotlivcov v populácii S.
2. Opakujte kroky 3 - 5 n-krát.
3. Vyberte celé číslo s od 0 do S.
4. Slučkujte jednotlivcov v populácii, sčítajte očakávané hodnoty, kým nie je súčet väčší ako s.
5. Vyberie sa jednotlivec, ktorého očakávaná hodnota dáva súčet nad limit s.

Nevýhody výberu rulety:

1. Pokiaľ sa zdatnosť veľmi líši, potom bude obvod rulety maximálne využívaný chromozómom s najvyššou zdatnosťou, takže ostatní majú veľmi malú šancu na výber.
2. Je to hlučné.
3. Vývoj závisí od rozdielov vo zdatnosti populácie.

Ďalšie metódy výberu

Existuje mnoho ďalších metód výberu použitých v „Výber“ krok genetického algoritmu.

Budeme diskutovať o ďalších 2 široko používaných metódach:

# 1) Výber poradia: Pri tejto metóde sa každému chromozómu pridelí hodnota fitness z hodnotenia. Najhoršia kondícia je 1 a najlepšia kondícia N. Je to metóda pomalej konvergencie. Pri tejto metóde sa zachováva rozmanitosť, ktorá vedie k úspešnému vyhľadávaniu.

Vyberú sa potenciálni rodičia a potom sa uskutoční turnaj, v ktorom sa rozhodne, ktorí z jednotlivcov budú rodičmi.

# 2) Výber turnaja: Pri tejto metóde sa na populáciu uplatňuje stratégia selektívneho tlaku. Najlepší jedinec je človek s najvyššou kondíciou. Tento jednotlivec je víťazom turnajovej súťaže medzi jednotlivcami Nu v populácii.

Populácia turnaja spolu s víťazom sa opäť pridáva do skupiny s cieľom generovať nových potomkov. Rozdiel v hodnotách zdatnosti víťaza a jednotlivcov v bazéne poskytuje selektívny tlak na dosiahnutie optimálnych výsledkov.

Crossover

Jedná sa o proces, ktorý berie 2 jednotlivcov a plodí z nich dieťa. Proces reprodukcie po výbere robí z klonov dobré bodnutie. Krížový operátor sa aplikuje cez struny na vytvorenie lepšieho potomka.

Implementácia operátora crossover je nasledovná:

1. Z populácie na výber potomkov sú náhodne vybraní dvaja jedinci.
2. Pozdĺž reťazca je náhodne vybraný cross-site.
3. Hodnoty na webe sú zamieňané.

Vykonané kríženie môže byť jednobodové kríženie, dvojbodové kríženie, viacbodové kríženie atď. Jednobodové kríženie má jedno miesto kríženia, zatiaľ čo dvojbodové kríženie má 2 miesta, kde sú hodnoty zamenené.

Vidíme to na príklade nižšie:

Crossover s jedným bodom

Dvojbodový výhybka

Pravdepodobnosť výhybky

P_c, pravdepodobnosť kríženia je termín, ktorý popisuje, ako často sa bude kríženie vykonávať. 0% pravdepodobnosť znamená, že nové chromozómy budú presnou kópiou starých chromozómov, zatiaľ čo 100% pravdepodobnosť znamená, že všetky nové chromozómy sa vytvárajú krížením.

Mutácia

Mutácia sa vykonáva po crossoveri. Zatiaľ čo crossover sa zameriava iba na súčasné riešenie, operácia mutácie prehľadá celý vyhľadávací priestor. Táto metóda spočíva v získaní stratenej genetickej informácie a jej distribúcii.

Tento operátor pomáha udržiavať genetickú rozmanitosť v populácii. Pomáha predchádzať miestnym minimám a generuje zbytočné riešenia od akejkoľvek populácie.

Mutácia sa vykonáva mnohými spôsobmi, napríklad invertovaním hodnoty každého génu s malou pravdepodobnosťou alebo mutáciou iba vtedy, ak to zlepší kvalitu roztoku.

Niektoré zo spôsobov mutácie sú:

• Prehodenie: Zmena z 0 na 1 alebo z 1 na 0.
• Zámena: Vyberú sa dve náhodné polohy a hodnoty sa zamenia.
• Cúvanie: Vyberie sa náhodná pozícia a bity vedľa nej sa obrátia.

Pozrime sa na niekoľko príkladov každého z nich:

Flipping

Zamieňanie

Cúvanie

Pravdepodobnosť mutácie

P_m, pravdepodobnosť mutácie je pojem, ktorý rozhoduje o tom, ako často budú chromozómy mutované. Ak je pravdepodobnosť mutácie 100%, znamená to, že sa zmenil celý chromozóm. Ak sa mutácia neuskutoční, generujú sa nové potomstvo priamo po krížení.

Príklad všeobecného genetického algoritmu Pravdepodobnosť mutácie: P_m, pravdepodobnosť mutácie je pojem, ktorý rozhoduje o tom, ako často budú chromozómy mutované. Ak je pravdepodobnosť mutácie 100%, znamená to, že sa zmenil celý chromozóm.

Ak sa mutácia neuskutoční, potom sa nové potomstvo generuje priamo po krížení. Počiatočná populácia chromozómov je uvedená ako A, B, C, D. Veľkosť populácie je 4.

Funkcia fitnes sa v reťazci považuje za číslo 1.

Súčet fitnes je 12, čo znamená, že priemerná fitnesová funkcia by bola ~ 12/4 = 3

Pravdepodobnosť kríženia = 0,7

Pravdepodobnosť mutácie = 0,001

# 1) Ak sú vybraté B a C, crossover sa nevykoná, pretože hodnota fitnes C je pod priemernou fitnes.

#dva) B je mutovaný => B: 11101110 -> B^„: 01101110 na zachovanie rozmanitosti populácie

# 3) B a D sú vybrané, vykoná sa kríženie.

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

# 4) Ak je E mutovaný, potom

E: 10110100 -> E^„: 10110000

Zodpovedajúce chromozómy sú uvedené v nasledujúcej tabuľke. Objednávka sa zadáva náhodne.

Aj keď je najzdatnejší jedinec s hodnotou fitnes 6 stratený, celková priemerná zdatnosť populácie sa zvyšuje a bude: 14/4 = 3,5

Kedy zastaviť genetický algoritmus

Genetický algoritmus je zastavený, ak sú splnené niektoré z podmienok uvedených nižšie:

# 1) Najlepšia individuálna konvergencia: Keď minimálna úroveň zdatnosti klesne pod hodnotu konvergencie, algoritmus sa zastaví. Vedie to k rýchlejšej konvergencii.

# 2) Najhoršia individuálna konvergencia: Keď najmenej zdatní jedinci v populácii dosiahnu minimálnu hodnotu kondície pod konvergenciou, algoritmus sa zastaví. Pri tejto metóde sa v populácii zachováva minimálny fitness štandard. To znamená, že najlepší jedinec nie je zaručený, ale budú prítomní jednotlivci s minimálnou hodnotou kondície.

# 3) Súčet fitnes: Ak je v tejto metóde súčet vhodnosti menší alebo rovný hodnote konvergencie, potom sa vyhľadávanie zastaví. Zaručuje to, že celá populácia je vo fitnes rozsahu.

# 4) Medián fitnes: V tejto metóde bude najmenej polovica jednotlivcov v populácii lepšia alebo rovnaká ako hodnota konvergencie.

Niektoré konvergenčné kritériá alebo podmienky zastavenia môžu byť:

• Keď sa vyvinul určený počet generácií.
• Keď je zadaný čas na spustenie algoritmu splnený.
• Keď sa fitness hodnota populácie s iteráciami ďalej nezmení.

Výhody a nevýhody genetického algoritmu

Výhody genetického algoritmu sú:

1. Má širší priestor na riešenie.
2. Je ľahšie objaviť globálne optimum.
3. Paralelizmus: Viaceré GA môžu bežať spolu s rovnakým procesorom bez toho, aby sa navzájom rušili. Prebiehajú paralelne izolovane.

Obmedzenia GA:

1. Identifikácia fitnes funkcie je obmedzením.
2. Konvergencia algoritmov môže byť príliš rýchla alebo príliš pomalá.
3. Existuje obmedzenie výberu parametrov, ako je kríženie, pravdepodobnosť mutácie, veľkosť populácie atď.

Aplikácie genetických algoritmov

GA je efektívny pri riešení vysokodimenzionálnych problémov. GA sa efektívne používa, keď je vyhľadávací priestor veľmi veľký, nie sú k dispozícii žiadne matematické techniky riešenia problémov a iné tradičné vyhľadávacie algoritmy nefungujú.

Niektoré aplikácie, kde sa používa GA:

• Problém s optimalizáciou: Jedným z najlepších príkladov problémov s optimalizáciou je problém obchodníka s cestami, ktorý využíva GA. Široko sa používajú ďalšie optimalizačné problémy, ako napríklad plánovanie úloh, optimalizácia kvality zvuku GA.
• Model imunitného systému: GA sa používajú na modelovanie rôznych aspektov imunitného systému pre jednotlivé génové a multigénové rodiny počas evolučného času.
• Strojové učenie: GA sa používajú na riešenie problémov súvisiacich s klasifikáciou, predikciou, tvorbou pravidiel pre učenie a klasifikáciu .

Záver

Genetické algoritmy sú založené na metóde prirodzeného vývoja. Tieto algoritmy sa líšia od ostatných klasifikačných algoritmov, pretože používajú kódované parametre (0 alebo 1), v populácii je viac osôb a na konvergenciu používajú pravdepodobnostnú metódu.

S procesom kríženia a mutácie sa GA zbližujú v nasledujúcich generáciách. Vykonanie algoritmu GA nezaručuje vždy úspešné riešenie. Genetické algoritmy sú vysoko efektívne pri optimalizácii - problémoch s plánovaním úloh.

Dúfam, že vám tento návod obohatil vedomosti o koncepte genetických algoritmov !!

=> Navštívte tu exkluzívnu sériu strojového učenia

Odporúčané čítanie

• Modelové testovanie pomocou genetického algoritmu
• Data Mining vs. Machine Learning vs. Artificial Intelligence vs. Deep Learning
• Výukový program pre strojové učenie: Úvod do ML a jeho aplikácií
• Typy strojového učenia: Supervízované vs.
• Kompletný sprievodca umelou neurónovou sieťou v strojovom učení
• 11 najpopulárnejších softvérových nástrojov pre strojové učenie v roku 2021
• Top 13 NAJ spoločností v oblasti strojového učenia (aktualizovaný zoznam 2021)
• Čo je podpora vektorového stroja (SVM) v strojovom učení