En blid introduktion til genetisk algoritme

Et billede af et gen

Når du begynder at forske på kunstig intelligent, har du måske hørt om noget, der kaldes 'Genetisk algoritme'. Når du har set dette udtryk, kan du være tilbageholdende med at grave dig ind i det, da det indeholder ordet 'algoritme'. Frygt ej! I denne artikel viser jeg dig enkelheden i genetisk algoritme og forhåbentlig inspirerer dig til at bygge en til din egen.

Hvad er genetisk algoritme?

Genetisk algoritme er dybest set en metode, der stærkt inspireres af processen med naturlig selektion for at finde den bedste løsning på et problem.

I naturen er det kun den stærke, der overlever, processen med at eliminere de svage kaldes naturlig udvælgelse. Genetisk algoritme bruger det samme princip for at eliminere de "svage" løsninger og endelig producere den bedste løsning.

Normalt bruges genetisk algoritme, når du ikke kan vide, hvordan løsningen vil være. For eksempel vil du oprette en bil, der kan navigere gennem forskellige slags terræn. Du kan ikke vide, hvordan den bil ser ud, men du kender bilens mål. I dette tilfælde kan den genetiske algoritme bruges til at generere bilen til kørsel af forskellige terræn, men bilkonstruktionen vil blive besluttet af algoritmen.

Arbejdsprocessen med genetisk algoritme

Som nævnt tidligere er den genetiske algoritme stærkt inspireret af den naturlige selektion, så for at se, hvordan genetisk algoritme fungerer, skal du faktisk undersøge, hvordan den naturlige selektion fungerer.

naturlig udvælgelsesproces (forenklet)

Diagrammet ovenfor illustrerer processen med naturlig udvælgelse. Det er klart, at denne proces involverer 5 hovedtrin. Det indledende trin er selektion, i dette trin vil naturen udvælge individer, der har et stærkt gen fra den oprindelige population, hvorefter de begynder at træde ind i det næste trin, der er parring. Efter at have været igennem parringstrin, producerer de et barn, vi kalder dette trin: "reproduktion". Det specifikke barn muterede derefter for at tilføje en vis variation til genet og flyttede til sidst tilbage i befolkningen.

Processen med genetisk algoritme svarer temmelig til processen ovenfor, den eneste forskellige er, at den tilføjede nogle yderligere detaljer.

genetisk algoritme arbejdsproces

Til at begynde med starter arbejdsprocessen med genetisk algoritme også med at have en indledende population. Den første hovedstadie er at beregne kondition, beregne kondition kan betragtes som en del af udvælgelsesprocessen, da det dybest set bruges til at beregne “score” for hver enkeltperson for at indikere, om det er et stærkt individ eller en svag. Alle de stærke enheder, der derefter er valgt og sendt til et trin kaldet crossover, er dette trin som parringstrinnet i det forrige diagram. På dette trin vælges 2 tilfældige forældre fra listen over stærke enheder for at udføre noget kaldet crossover, som vi vil diskutere senere. Efter at have udført crossover oprettes og muteres et barn for at tilføje en vis variation til genet. Endelig slutter dette barn sig til befolkningen igen, og processen gentages igen.

Hvad pokker er fitness

I genetisk algoritme spiller fitness en vigtig rolle i selektionsstadiet. Fitness er "score" til at vælge en enhed, der får at videregive dens egenskaber. For eksempel, hvis en person har en alvorlig sygdom, vil hans "fitness score" være lav og mindre sandsynlig at have en chance for at få børn, da hans børn også vil arve hans sygdom. Derfor, hvis en opløsnings egnethed er lav, vil du måske ikke ønsker at oprette en anden løsningsbase på den, da resultatet ville være så dårligt som den gamle løsning.

Prøv at forestille dig, at du får et problem, problemet er at finde den bedste rute for rød ridehætte til at rejse til hendes bedstemor. Lad os antage, at hun ønsker at nå sit bedstemorhus på den kortest mulige tid, derfor kan rutens kondition beregnes ved hjælp af den tid det tog hende at rejse. Hvis der er en rute, der har en længde på 400 meter, og det tog hende 10 minutter at rejse, vil dens kondition bestemt bestemt være mindre end konditionen på en rute, der er 500 meter lang, men kun tog hende 8 minutter at rejse som en kondition rute beregner basis for rejsetiden, ikke længden af ​​den. Derfor ville den 500 meter lange rute mere sandsynligt blive valgt til at kombinere med andre ruter.

Valg af den gode!

At vælge den passende løsning er det, den genetiske algoritmes valg af fase handler om. Efter beregning af fitness-score er det næste trin at bruge nogle mystiske metoder til at vælge en liste over løsninger, der senere kan bruges til at producere en bedre løsning.

Selvom du kan oprette din egen måde at vælge passende løsninger, er der nogle berømte metoder, du kan bruge:

  • Fitness-forholdsmæssigt valg
  • Turneringsvalg
  • Valg af trunkering
  • Fitness ensartet valg

Listen ovenfor er ikke en passende liste, du kan finde ud af flere metoder her.

Lad os tage den første metode som et eksempel. I modsætning til dens navn er det egentlige koncept bag denne metode absurd enkel. Egnethedsproportionalt valg AKA roulettehjulvalget er metoden til at vælge "potentielle" løsninger til rekombination.

Forestil dig, hvis der er 10 kugler i en taske, specifikt 5 blå kugler, 3 røde kugler og 2 hvide kugler. Du kan nemt beregne, at hvis du vælger en tilfældig marmor fra tasken, vil du have 5/10 chance for at vælge en blå, 3/10 for rød og 2/10 for hvid. Sådan fungerer fitness-forholdsmæssigt valg, men processen er en smule anderledes.

I egnethedsforholdet vælges først et tilfældigt antal, derefter bruges det til at sammenligne med egnetheden af ​​en tilfældig valgt løsning. Fitnessværdien begrænses normalt til at gå fra 0 til 1. Hvis den tilfældige værdi er mindre end den fitness-score, vælges løsningen. Jo højere en løsning er, jo større er chancen for, at den bliver valgt. For eksempel, hvis et tilfældigt tal går fra 0 til 1, er der 50%, det vil være mindre end 0,5 og 80%, det vil være mindre end 0,8, men det vil sandsynligvis ikke være mindre end 0,2, det betyder, hvis en opløsningen har en 0,8 egnethed, der er 80%, den vælges til rekombination, og opløsning, der har 0,2 egnethed, har kun 20% der skal vælges. Selvom 0.2-fit-løsningen sjældent vælges, men det hjælper også med at variere løsningsegenskaber, da den løsning kan indeholde nogle attributter, der er nødvendige for senere succes.

Udfører crossover

Crossover er det stadie, hvor valgte løsninger kombineres for at danne nye løsninger. Ligesom valgfasen er der også mange teknikker til overgang, og du kan også finde dem her.

I lighed med udvælgelsesstadiet, i crossover-trin, kan du også opfinde dine egne crossover-teknikker, men der er også nogle teknikker, du kan bruge:

  • Enkelpunktsovergang
  • To-punkts crossover
  • Ensartet crossover
  • Tre overordnede crossover

For bedre forståelse skal jeg forklare den ensartede crossover-teknik, som er den teknik, som jeg regner med den mest letteste teknik at implementere.

Den ensartede crossover-metode involverede plukning af en tilfældig del af genet fra 2-opløsningen tilfældigt for at kombinere og skabe en ny (forhåbentlig bedre) løsning.

Det første trin i ensartet crossover er at vælge 2 tilfældige opløsninger fra det sæt af opløsninger, der vælges i det forrige udvælgelsestrin. Derefter vælges hver del af de 2 opløsninger for at tilføje barneløsningsbasen på en variabel kaldet blandingsforholdet. Blandingsforholdet er den ting, der bestemmer chancen for, at der sandsynligvis vælges en løsning for at føje til barneløsningen. For eksempel er der 2 løsninger: A og B, og du vil have, at børneløsningen skal have flere dele, der er taget fra løsning A, du kan øge blandingsforholdet, efter det loop gennem alle dele af løsningen A og B. I hver løkke , opret et nyt tilfældigt tal og sammenlign det med blandingsforholdet, hvis det er mindre end blandingsforholdet, vælg derefter løsningen. En anden del vælger B. Tilsvarende, hvis blandingsforholdet er 0,5, vil A og B have ca. 50% af bliver plukket.

Ensartet crossover med blandingsforhold 0,5

Ovenstående billede viser børneløsningen C dannet ved hjælp af opløsning A og B med blandingsforholdet 0,5 eller 50%. Hver del af begge opløsninger blev besluttet at blive plukket eller ikke baseret på blandingsforholdet, og blandingsforholdet blev sammenlignet med et tilfældigt antal til at bestemme. Det er som at kaste en mønt for at vælge hvor A skal bruges i stedet for B og omvendt.

Muter barnet!

Nej nej nej, vi forvandler ikke vores børn til nogle fyre med metal kløer og lader dem dø på en tilfældig træstamme!

I stedet for at tilføje mutation til et barn er som at hjælpe dem til

Ved at tænke anderledes kan et individ, om han bliver leder af flokken eller en komplet stum røv.

Et eksempel på mutation

Som du kan se, går det røde barn på en anden vej sammenlignet med andre børn. Årsagen til dette er fordi, når det røde barn følger flokken, tilføjede vi en eller anden mutation til ham og derfor hjælper ham med at vælge en anden vej. Naturligvis kan denne forskellige sti også være en blindgyde, men klart, i dette tilfælde fører stien til succes! Det er det sande formål med mutationsstadiet.

For at mutere et barn er der også en række teknikker, som du kan bruge:

  • Bitstrengemutation
  • Flip Bit
  • Ikke-Uniform
  • Uniform

Du kan finde flere af dem her.

For at forstå dette bedre skal jeg demonstrere teknikken "bitstrengmutation".

Forestil dig, at du laver en bot for at undgå genstande foran den. Bot skal undgå alle objekter for at nå den endelige destination, og dens naturlige tilstand bevæger sig fremad. For at undgå objekt vil dets gen være en række 'venstre' og 'højre' strenge, der indikerer, hvordan man bot vil bevæge sig.

"Bitstrengemutationen" bruges normalt til binær streng, da denne metode vipper 1 eller flere tilfældigt valgte bit i genet. For eksempel:

Eksempel på bitstrengemutation

Prøv nu at omdanne 1 og 0 til venstre og højre og tænk på, hvordan boten vil fungere. Da botten kan sætte sig fast, når den stødte på et stort objekt, vil mutationen hjælpe dets afkom med at vælge en ny retning for at bevæge sig og undgå det. Forestil dig i mange generationer, at boten kun drejer til højre, når han møder et objekt og dør, men i den næste generation vendte boten pludselig til venstre, da en højre streng i dens gen blev vendt til venstre, og boten til sidst nåede sin destination. Det er dybest set, hvordan 'bitstrengemutationen' fungerer.

Afslutningen af ​​processen

Efter mutation af barnet, vil det gå sammen med andet muteret barn for at reformere en ny befolkning, og hele processen starter igen.

Så hvornår stopper det? Svaret er ekstremt enkelt, hvornår holder du op med at øve at skrive tastatur med 10 fingre? Når din skrivefærdighed naturligvis er perfekt. Samme ting med genetisk algoritme, processen stopper, hvis en bestemt opløsnings egnethed nåede den ønskede egnethed. For eksempel vil du have, at boten i det forrige eksempel skal nå destinationen med den mindst mulige tid.

Du indstiller fitness-tærsklen til 4 minutter, hvis botens tid til at afslutte er mere end 4 minutter, betyder det, at processen gentages, indtil botens sluttid er mindre end eller svarer til 4 minutter.

Konklusion

Det er slutningen på min artikel, jeg håber, at du efter denne artikel får bedre indsigt i genetisk algoritme har inspireret til at opbygge en af ​​dine egne.

Her er nogle links, som du kan udforske mere om genetisk algoritme:

  • Daniel Shiffman videoer om genetisk algoritme:
  • Mit eksempel til at bruge genetisk algoritme til at gætte en adgangskode
  • tutorialspoint tutorial om genetisk algoritme
  • Goran Muric-video om et eksempel, der bruger genetisk algoritme til at finde sti