Inleiding tot genetische algoritmen bij machinaal leren

introduction genetic algorithms machine learning

beste muziekdownloader-app voor Android

Deze zelfstudie over genetische algoritmen legt in detail uit wat genetische algoritmen zijn en hun rol in machine learning ​

In de Vorige tutorial leerden we over kunstmatige neurale netwerkmodellen - meerlagige perceptron, backpropagation, radiale bias en Kohonen zelforganiserende kaarten, inclusief hun architectuur.

We zullen ons concentreren op genetische algoritmen die veel eerder kwamen dan neurale netwerken, maar nu is GA overgenomen door NN. Hoewel GA nog steeds toepassingen in het echte leven heeft, zoals optimalisatieproblemen zoals planning, games spelen, robotica, hardware-ontwerp, problemen met handelsreizigers, enz.

Genetische algoritmen zijn algoritmen die zijn gebaseerd op het evolutionaire idee van natuurlijke selectie en genetica. GA's zijn adaptieve heuristische zoekalgoritmen, d.w.z. de algoritmen volgen een iteratief patroon dat met de tijd verandert. Het is een soort bekrachtigingsleren waarbij de feedback nodig is zonder het juiste pad te volgen. De feedback kan zowel positief als negatief zijn.

​ Lees de complete serie Machine Learning-trainingen door

Wat je leert:

• Waarom genetische algoritmen gebruiken
  • Biologische achtergrond van genetische algoritmen
• Wat zijn genetische algoritmen
  • Correlatie van een chromosoom met GA
  • Belangrijke terminologie in GA
  • Een eenvoudig genetisch algoritme
  • Roulettewiel selectiemethode
  • Andere selectiemethoden
  • Crossover
  • Mutatie
  • Wanneer het genetische algoritme moet stoppen
• Voordelen en nadelen van genetisch algoritme
• Toepassingen van genetische algoritmen
• Gevolgtrekking
  • Aanbevolen literatuur

Waarom genetische algoritmen gebruiken

GA's zijn robuustere algoritmen die kunnen worden gebruikt voor verschillende optimalisatieproblemen. Deze algoritmen wijken niet gemakkelijk af in de aanwezigheid van ruis, in tegenstelling tot andere AI-algoritmen. GA's kunnen worden gebruikt bij het zoeken naar grote ruimte of multimodale ruimte.

Biologische achtergrond van genetische algoritmen

Genetica is afgeleid van het Griekse woord 'genesis' dat groeien betekent. De genetica bepaalt de erfelijkheidsfactoren, overeenkomsten en verschillen tussen de nakomelingen in het evolutieproces. Genetische algoritmen zijn ook afgeleid van natuurlijke evolutie.

Enkele terminologieën in een biologisch chromosoom

• Chromosomen: Alle genetische informatie van een soort is opgeslagen chromosomen.
• Genen: De chromosomen zijn onderverdeeld in verschillende delen die genen worden genoemd.
• Allelen: De genen identificeren het kenmerk van een individu. De mogelijkheid van een combinatie van genen om eigenschappen te vormen, wordt allelen genoemd. Een gen kan verschillende allelen hebben.
• Genetische verzameling: Alle mogelijke combinaties van genen die allemaal allelen zijn in een populatiepool, worden genenpool genoemd.
• Genoom: De set genen van een soort wordt een genoom genoemd.
• Locus: Elk gen heeft een positie in een genoom dat locus wordt genoemd.
• Genotype: Een volledige combinatie van genen in een individu wordt het genotype genoemd.
• Fenotype: Een reeks genotypen in gedecodeerde vorm wordt het fenotype genoemd.

Wat zijn genetische algoritmen

De genetische algoritmen stimuleren het proces zoals in natuurlijke systemen voor evolutie. Charles Darwin verklaarde de evolutietheorie dat in de natuurlijke evolutie biologische wezens evolueren volgens het principe van 'survival of the fittest'. De GA-zoekopdracht is bedoeld om de theorie van 'survival of the fittest' aan te moedigen.

De GA's voeren een willekeurige zoekopdracht uit om optimalisatieproblemen op te lossen. De GA gebruikt technieken die de eerdere historische informatie gebruiken om hun zoektocht te richten op optimalisatie in de nieuwe zoekruimte.

Correlatie van een chromosoom met GA

Het menselijk lichaam heeft chromosomen die zijn gemaakt van genen. Een set van alle genen van een specifieke soort wordt het genoom genoemd. Bij levende wezens worden de genomen opgeslagen in verschillende chromosomen, terwijl in GA alle genen op hetzelfde chromosoom worden opgeslagen.

Vergelijking tussen natuurlijke evolutie en genetische algoritme-terminologie

Belangrijke terminologie in GA

• Bevolking: Het is een groep individuen. De populatie omvat het aantal geteste personen, zoekruimte-informatie en de fenotypeparameters. Over het algemeen wordt de populatie willekeurig geïnitialiseerd.
• Individuen: Individuen zijn een enkele oplossing in de bevolking. Een individu heeft een reeks parameters die genen worden genoemd. Genen gecombineerd om chromosomen te vormen.
• Genen: Genen zijn bouwstenen van genetische algoritmen. Een chromosoom bestaat uit genen. De genen kunnen de oplossing voor het probleem bepalen. Ze worden weergegeven door een bit (0 of 1) reeks van willekeurige lengte.
• Fitness: De conditie vertelt de waarde van het fenotype van het probleem. De fitnessfunctie vertelt hoe dicht de oplossing bij de optimale oplossing ligt. De fitnessfunctie wordt op veel manieren bepaald, zoals de som van alle parameters die verband houden met het probleem - Euclidische afstand, enz. Er is geen regel om de fitnessfunctie te evalueren.

Een eenvoudig genetisch algoritme

Een eenvoudige GA heeft een populatie van individuele chromosomen. Deze chromosomen vertegenwoordigen mogelijke oplossingen. Reproductie-operators worden toegepast op deze sets chromosomen om mutaties en recombinatie uit te voeren. Het is dus belangrijk om geschikte reproductieoperatoren te vinden, aangezien het gedrag van GA hiervan afhankelijk is.

Een eenvoudig genetisch algoritme is als volgt:

# 1) Begin met de willekeurig gecreëerde populatie.

#twee) Bereken de fitnessfunctie van elk chromosoom.

# 3) Herhaal de stappen totdat er n nakomelingen zijn gemaakt. De nakomelingen worden gemaakt zoals hieronder weergegeven.

• Selecteer een paar chromosomen uit de populatie.
• Crossover het paar met kans p_com nakomelingen te vormen.
• Muteer de crossover met waarschijnlijkheid p_m​

# 4) Vervang de oorspronkelijke populatie door de nieuwe populatie en ga naar stap 2.

Laten we eens kijken naar de stappen die in dit iteratieproces zijn gevolgd. De eerste populatie chromosomen wordt gegenereerd. De oorspronkelijke populatie moet voldoende genen bevatten zodat elke oplossing kan worden gegenereerd. De eerste populatiepool wordt willekeurig gegenereerd.

• Selectie: Afhankelijk van de fitnessfunctie wordt de beste set genen geselecteerd. De string met de beste fitnessfunctie wordt gekozen.
• Reproductie: Nieuwe nakomelingen worden gegenereerd door recombinatie en mutatie.
• Evaluatie: De nieuwe gegenereerde chromosomen worden beoordeeld op hun fitheid.
• Vervanging: In deze stap wordt de oude populatie vervangen door de nieuw gegenereerde populatie.

Roulettewiel selectiemethode

Selectie van het roulettewiel is de selectiemethode die veel wordt gebruikt.

Het selectieproces is kort, zoals hieronder wordt weergegeven:

Bij deze methode wordt er lineair gezocht via het roulettewiel. De sleuven in het wiel worden gewogen op basis van de individuele fitnesswaarde. De streefwaarde wordt willekeurig bepaald op basis van het aandeel van de som van de fitheid in de populatie.

De populatie wordt vervolgens doorzocht totdat de streefwaarde is bereikt. Deze methode garandeert niet de sterkste van de individuen, maar heeft een kans om de sterkste te zijn.

Laten we eens kijken naar de stappen die betrokken zijn bij de selectie van het roulettewiel.

De verwachte waarde van een individu = individuele fitheid / fitheid van de populatie. De wielsleuven worden aan individuen toegewezen op basis van hun conditie. Het wiel wordt N keer rondgedraaid, waarbij N het totale aantal individuen in de populatie is. Wanneer een rotatie voorbij is, wordt de geselecteerde persoon in een pool van ouders geplaatst.

1. Stel dat de totale verwachte waarde van een aantal individuen in de populatie S.
2. Herhaal stap 3-5 n keer.
3. Selecteer een geheel getal s tussen 0 en S.
4. Loop door individuen in de populatie, tel de verwachte waarden bij elkaar op totdat de som groter is dan s.
5. De persoon wiens verwachte waarde de som boven de limiet s zet, wordt geselecteerd.

Nadelen van roulettewielkeuze:

1. Als de conditie erg verschilt, wordt de omtrek van het roulettewiel maximaal ingenomen door het chromosoom met de hoogste fitnessfunctie, zodat de anderen weinig kans hebben om geselecteerd te worden.
2. Het is lawaaierig.
3. De evolutie hangt af van de variantie in de fitheid van de populatie.

Andere selectiemethoden

Er zijn veel andere selectiemethoden die worden gebruikt in de 'Selectie' stap van het genetische algoritme.

We zullen de 2 andere veelgebruikte methoden bespreken:

# 1) Rangselectie: Bij deze methode krijgt elk chromosoom een ​​fitnesswaarde uit de ranking. De slechtste conditie is 1 en de beste conditie is N. Het is een langzame convergentiemethode. Bij deze methode blijft de diversiteit behouden, wat leidt tot een succesvolle zoektocht.

Potentiële ouders worden geselecteerd en vervolgens wordt een toernooi gehouden om te beslissen wie van de individuen een ouder zal zijn.

# 2) Toernooiselectie: Bij deze methode wordt een selectieve drukstrategie toegepast op de bevolking. De beste persoon is degene met de hoogste conditie. Deze persoon is de winnaar van de toernooicompetitie onder Nu-individuen in de populatie.

De toernooipopulatie wordt samen met de winnaar weer in de poule toegevoegd om nieuwe nakomelingen te genereren. Het verschil in de fitnesswaarden van de winnaar en individuen in de paringspool zorgt voor een selectieve druk voor optimale resultaten.

Crossover

Het is een proces waarbij twee individuen worden genomen en er een kind uit wordt voortgebracht. Het reproductieproces na selectie maakt klonen van de goede steken. De crossover-operator wordt over de snaren toegepast om een ​​beter nageslacht te produceren.

De implementatie van de crossover-operator is als volgt:

1. Twee individuen worden willekeurig uit de populatie geselecteerd om nakomelingen te produceren.
2. Een cross-site wordt willekeurig geselecteerd langs de lengte van de string.
3. De waarden op de site worden omgewisseld.

De crossover die wordt uitgevoerd, kan een single-point crossover, tweepunts crossover, multipoint crossover, etc. zijn. De single point crossover heeft één crossover-site, terwijl een tweepunts crossover-site 2 sites heeft waar de waarden worden uitgewisseld.

We kunnen dit zien in het onderstaande voorbeeld:

Single Point Crossover

Tweepunts crossover

Crossover-waarschijnlijkheid

P._cis crossover-waarschijnlijkheid de term die beschrijft hoe vaak de crossover zal worden uitgevoerd. 0% waarschijnlijkheid betekent dat de nieuwe chromosomen een exacte kopie zijn van de oude chromosomen, terwijl 100% waarschijnlijkheid betekent dat alle nieuwe chromosomen worden gemaakt door crossover.

Mutatie

Mutatie wordt gedaan na Crossover. Terwijl crossover zich alleen richt op de huidige oplossing, doorzoekt de mutatiebewerking de hele zoekruimte. Deze methode is om de verloren genetische informatie terug te krijgen en de genetische informatie te verspreiden.

Deze operator helpt de genetische diversiteit in de populatie te behouden. Het helpt lokale minima te voorkomen en voorkomt het genereren van nutteloze oplossingen van welke populatie dan ook.

De mutatie wordt op veel manieren uitgevoerd, zoals het omkeren van de waarde van elk gen met een kleine kans of het uitvoeren van mutaties alleen als het de kwaliteit van de oplossing verbetert.

Enkele van de manieren van mutatie zijn:

• Flippen: Veranderen van 0 naar 1 of 1 naar 0.
• Verwisselen: Er worden twee willekeurige posities gekozen en de waarden worden uitgewisseld.
• Omkeren: Een willekeurige positie wordt gekozen en de bits ernaast worden omgekeerd.

Laten we van elk een paar voorbeelden bekijken:

Flippen

Uitwisselen

Omkeren

Mutatiekans

P._mis mutatiekans een term die bepaalt hoe vaak de chromosomen worden gemuteerd. Als de mutatiekans 100% is, betekent dit dat het hele chromosoom is veranderd. Als een mutatie niet wordt uitgevoerd, worden direct na de cross-over nieuwe nakomelingen gegenereerd.

Een voorbeeld van een algemeen genetisch algoritme Mutatiekans: P._mis mutatiekans een term die bepaalt hoe vaak de chromosomen worden gemuteerd. Als de mutatiekans 100% is, betekent dit dat het hele chromosoom is veranderd.

Als een mutatie niet wordt uitgevoerd, worden de nieuwe nakomelingen direct na de cross-over gegenereerd. De initiële populatie chromosomen wordt gegeven als A, B, C, D. De populatieomvang is 4.

De fitnessfunctie wordt genomen als een aantal enen in de string.

De som van fitness is 12, wat betekent dat de gemiddelde fitnessfunctie ~ 12/4 = 3 zou zijn

Crossover-waarschijnlijkheid = 0,7

Mutatiekans = 0,001

# 1) Als B en C zijn geselecteerd, wordt de crossover niet uitgevoerd omdat de fitnesswaarde van C lager is dan de gemiddelde fitheid.

#twee) B is gemuteerd => B: 11101110 -> B^​: 01101110 om de diversiteit van de bevolking te behouden

# 3) B en D zijn geselecteerd, de crossover wordt uitgevoerd.

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

# 4) Als E is gemuteerd, dan

E: 10110100 -> E^​: 10110000

Overeenkomstige chromosomen worden weergegeven in de onderstaande tabel. De volgorde wordt willekeurig geplaatst.

Hoewel de sterkste persoon met fitnesswaarde 6 verloren gaat, neemt de algehele gemiddelde fitheid van de populatie toe en zou deze zijn: 14/4 = 3,5

Wanneer het genetische algoritme moet stoppen

Een genetisch algoritme wordt gestopt wanneer aan een aantal onderstaande voorwaarden wordt voldaan:

# 1) Beste individuele convergentie: Wanneer het minimale fitnessniveau onder de convergentiewaarde zakt, wordt het algoritme gestopt. Het leidt tot snellere convergentie.

# 2) Slechtste individuele convergentie: Wanneer de minst geschikte individuen in de populatie een minimale fitnesswaarde bereiken die onder de convergentie ligt, wordt het algoritme gestopt. Bij deze methode wordt de minimale fitnessnorm in de populatie gehandhaafd. Het betekent dat de beste persoon niet gegarandeerd is, maar dat er een minimale fitnesswaarde aanwezig is.

# 3) Som van fitness: Als bij deze methode de som van de fitness kleiner is dan of gelijk is aan de convergentiewaarde, wordt het zoeken gestopt. Het garandeert dat de hele bevolking binnen het fitnessbereik valt.

# 4) Mediane fitheid: Bij deze methode zal ten minste de helft van de individuen in de populatie beter zijn dan of gelijk zijn aan de convergentiewaarde.

Sommige convergentiecriteria of stopcondities kunnen zijn:

• Wanneer een bepaald aantal generaties is geëvolueerd.
• Wanneer de opgegeven tijd om het algoritme uit te voeren, is bereikt.
• Wanneer de fitnesswaarde van de populatie niet verder verandert met iteraties.

Voordelen en nadelen van genetisch algoritme

Voordelen van een genetisch algoritme zijn:

1. Het heeft een grotere oplossingsruimte.
2. Het is gemakkelijker om het globale optimum te ontdekken.
3. Parallelliteit: Meerdere GA's kunnen samen worden uitgevoerd met dezelfde CPU zonder elkaar te storen. Ze lopen parallel in isolatie.

Beperkingen van GA:

1. De identificatie van de fitnessfunctie is een beperking.
2. De convergentie van de algoritmen kan te snel of te langzaam zijn.
3. Er is een beperking bij het selecteren van de parameters zoals crossover, mutatiekans, populatieomvang enz.

Toepassingen van genetische algoritmen

GA is effectief om hoog dimensionale problemen op te lossen. Een GA wordt effectief gebruikt wanneer de zoekruimte erg groot is, er geen wiskundige probleemoplossende technieken beschikbaar zijn en andere traditionele zoekalgoritmen niet werken.

Enkele toepassingen waar GA wordt gebruikt:

• Optimalisatieprobleem: Een van de beste voorbeelden van de optimalisatieproblemen is het probleem van de reisverkoper die GA gebruikt. Andere optimalisatieproblemen zoals taakplanning en GA's voor optimalisatie van de geluidskwaliteit worden veel gebruikt.
• Immuunsysteem model: GA's worden gebruikt om verschillende aspecten van het immuunsysteem te modelleren voor individuele gen- en multi-genfamilies gedurende de evolutionaire tijd.
• Machine leren: GA's zijn gebruikt om problemen met classificatie en voorspelling op te lossen, regels voor leren en classificatie te creëren ​

Gevolgtrekking

Genetische algoritmen zijn gebaseerd op de methode van natuurlijke evolutie. Deze algoritmen verschillen van de andere classificatie-algoritmen omdat ze gecodeerde parameters gebruiken (0 of 1), er zijn meerdere aantallen individuen in een populatie en ze gebruiken de probabilistische methode voor convergentie.

Met het proces van cross-over en mutatie komen de GA's bij opeenvolgende generaties samen. De uitvoering van een GA-algoritme garandeert niet altijd een succesvolle oplossing. De genetische algoritmen zijn zeer efficiënt in optimalisatie - problemen met de taakplanning.

Ik hoop dat deze tutorial je kennis over het concept van genetische algoritmen zou hebben verrijkt !!

​ Bezoek hier voor de exclusieve Machine Learning-serie

Aanbevolen literatuur

• Modelgebaseerd testen met behulp van genetisch algoritme
• Datamining versus machine learning versus kunstmatige intelligentie versus diep leren
• Zelfstudie voor machine learning: inleiding tot ML en de toepassingen ervan
• Soorten machine learning: begeleid versus onbewaakt leren
• Een complete gids voor kunstmatig neuraal netwerk bij machinaal leren
• 11 populairste softwaretools voor machine learning in 2021
• Top 13 BESTE Machine Learning-bedrijven (bijgewerkte lijst voor 2021)
• Wat is Support Vector Machine (SVM) bij machine learning