streamalism.org

1. Introduksjon

Målet med denne serien er å forklare ideen om genetiske algoritmer.

Genetiske algoritmer er designet for å løse problemer ved å bruke de samme prosessene som i naturen - de bruker en kombinasjon av seleksjon, rekombinasjon og mutasjon for å utvikle en løsning på et problem.

La oss starte med å forklare konseptet med disse algoritmene ved hjelp av det enkleste binære genetiske algoritmeeksemplet.

2. Hvordan genetiske algoritmer fungerer

Genetiske algoritmer er en del av evolusjonær databehandling, som er et raskt voksende område med kunstig intelligens.

En algoritme starter med en sett med løsninger (representert av enkeltpersoner) kalt befolkning. Løsninger fra en populasjon tas og brukes til å danne en ny befolkning, siden det er en sjanse for at den nye befolkningen vil være bedre enn den gamle.

Enkeltpersoner som er valgt for å danne nye løsninger (avkom) velges i henhold til deres Fitness - jo mer passende de er, jo større sjanser har de for å reprodusere.

3. Binær genetisk algoritme

La oss ta en titt på den grunnleggende prosessen for en enkel genetisk algoritme.

3.1. Initialisering

I initialiseringstrinnet, vi generere en tilfeldig Befolkning som fungerer som en første løsning. Først må vi bestemme hvor stort Befolkning vil være, og hva er den endelige løsningen vi forventer:

SimpleGeneticAlgorithm.runAlgorithm (50, "1011000100000100010000100000100111001000000100000100000000001111");

I eksemplet ovenfor er Befolkning størrelse er 50, og riktig løsning er representert av den binære bitestrengen som vi kan endre når som helst.

I neste trinn skal vi lagre ønsket løsning og lage en tilfeldig Befolkning:

setSolution (løsning); Befolkning myPop = ny befolkning (populationSize, true);

Nå er vi klare til å kjøre hovedsløyfen til programmet.

3.2. Treningssjekk

I hovedsløyfen til programmet skal vi evaluere hver Individuell av treningsfunksjonen (med enkle ord, jo bedre er det Individuell er, jo høyere verdi av treningsfunksjon det får):

while (myPop.getFittest (). getFitness () <getMaxFitness ()) {System.out.println ("Generation:" + generationCount + "Riktige gener funnet:" + myPop.getFittest (). getFitness ()); myPop = evolvePopulation (myPop); generationCount ++; }

La oss begynne med å forklare hvordan vi blir sprekeste Individuell:

public int getFitness (Individual individual) {int fitness = 0; for (int i = 0; i <individual.getDefaultGeneLength () && i <solution.length; i ++) {if (individual.getSingleGene (i) == løsning [i]) {fitness ++; }} returner kondisjon; }

Som vi kan se, sammenligner vi to Individuell objekter bit for bit. Hvis vi ikke finner en perfekt løsning, må vi gå videre til neste trinn, som er en utvikling av Befolkning.

3.3. Avkom

I dette trinnet må vi lage et nytt Befolkning. Først må vi Å velge to foreldre Individuell gjenstander fra en Befolkning, i henhold til deres kondisjon. Vær oppmerksom på at det er fordelaktig å tillate det beste Individuell fra dagens generasjon til å overføre til neste, uendret. Denne strategien kalles en Elitisme:

if (elitism) {newPopulation.getIndividuals (). add (0, pop.getFittest ()); elitismOffset = 1; } annet {elitismOffset = 0; }

For å velge to beste Individuell gjenstander, skal vi bruke turneringsvalgstrategi:

privat Individuell turneringValg (Befolkningspop) {Befolkningsturnering = ny Befolkning (turneringsstørrelse, falsk); for (int i = 0; i <turneringsstørrelse; i ++) {int randomId = (int) (Math.random () * pop.getIndividuals (). størrelse ()); turnering.getIndividuals (). legg til (i, pop.getIndividual (randomId)); } Individuell sterkest = turnering.getFittest (); tilbake sterkest; }

Vinneren av hver turnering (den med den beste egnetheten) blir valgt til neste trinn, det vil si Crossover:

privat Individuell crossover (Individuell indiv1, Individuell indiv2) {Individual newSol = ny Individual (); for (int i = 0; i <newSol.getDefaultGeneLength (); i ++) {if (Math.random () <= uniformRate) {newSol.setSingleGene (i, indiv1.getSingleGene (i)); } annet {newSol.setSingleGene (i, indiv2.getSingleGene (i)); }} returner newSol; }

I crossover bytter vi biter fra hver valgte Individuell på et tilfeldig valgt sted. Hele prosessen kjører i følgende løkke:

for (int i = elitismOffset; i <pop.getIndividuals (). størrelse (); i ++) {Individuell indiv1 = turneringsvalg (pop); Individuell indiv2 = turneringsvalg (pop); Individuell newIndiv = crossover (indiv1, indiv2); newPopulation.getIndividuals (). legg til (i, newIndiv); }

Som vi kan se, etter overgangen plasserer vi nye avkom i et nytt Befolkning. Dette trinnet kalles Godkjennelse.

Endelig kan vi utføre en Mutasjon. Mutasjon brukes til å opprettholde genetisk mangfold fra en generasjon av en Befolkning til neste. Vi brukte litt inversjon type mutasjon, hvor tilfeldige biter ganske enkelt blir invertert:

privat ugyldig mutasjon (Individuell indiv) {for (int i = 0; i <indiv.getDefaultGeneLength (); i ++) {if (Math.random () <= mutationRate) {byte gen = (byte) Math.round (Math. tilfeldig()); indiv.setSingleGene (i, gen); }}}

Alle typer mutasjoner og crossover er pent beskrevet i denne opplæringen.

Vi gjentar deretter trinn fra underavsnitt 3.2 og 3.3, til vi når en avslutningstilstand, for eksempel den beste løsningen.

4. Tips og triks

For å implementere en effektiv genetisk algoritme, må vi stille inn et sett med parametere. Denne delen skal gi deg noen grunnleggende anbefalinger for hvordan du begynner med de mest importerte parametrene:

• Crossover rate - den skal være høy, omtrent 80%-95%
• Mutasjonsrate - den skal være veldig lav, rundt 0.5%-1%.
• Befolkningsstørrelse - god befolkningsstørrelse handler om 20-30for noen problemer er størrelsene 50-100 imidlertid bedre
• Utvalg - grunnleggende valg av roulettehjul kan brukes med begrepet elitisme
• Crossover og mutasjonstype - det avhenger av koding og problemet

Vær oppmerksom på at anbefalinger for tuning ofte er resultater av empiriske studier av genetiske algoritmer, og de kan variere, basert på de foreslåtte problemene.

5. Konklusjon

Denne opplæringen introduserer grunnleggende om genetiske algoritmer. Du kan lære om genetiske algoritmer uten forutgående kunnskap av dette området, med bare grunnleggende dataprogrammeringsferdigheter.

Den komplette kildekoden for kodebitene i denne opplæringen er tilgjengelig i GitHub-prosjektet.

Vær også oppmerksom på at vi bruker Lombok til å generere getters og settere. Du kan sjekke hvordan du konfigurerer det riktig i IDE i denne artikkelen.

For flere eksempler på genetiske algoritmer, sjekk ut alle artiklene i serien vår:

• Hvordan lage en genetisk algoritme? (denne)
• Det reisende selgerproblemet i Java