Design en genetisk algoritme i Java

1. Introduktion

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

Genetiske algoritmer er designet til at løse problemer ved hjælp af de samme processer som i naturen - de bruger en kombination af selektion, rekombination og mutation til at udvikle en løsning på et problem.

Lad os starte med at forklare konceptet med disse algoritmer ved hjælp af det enkleste binære genetiske algoritmeeksempel.

2. Hvordan genetiske algoritmer fungerer

Genetiske algoritmer er en del af evolutionær computing, som er et hurtigt voksende område med kunstig intelligens.

En algoritme starter med en sæt løsninger (repræsenteret af enkeltpersoner) hedder befolkning. Løsninger fra en population tages og bruges til at danne en ny befolkning, da der er en chance for, at den nye befolkning vil være bedre end den gamle.

Enkeltpersoner, der vælges til at danne nye løsninger (afkom) vælges efter deres fitness - jo mere egnede de er, jo flere chancer har de for at reproducere.

3. Binær genetisk algoritme

Lad os se på den grundlæggende proces for en simpel genetisk algoritme.

3.1. Initialisering

I initialiseringstrinet, vi generere en tilfældig Befolkning der fungerer som en første løsning. Først skal vi beslutte, hvor stort Befolkning vil være, og hvad er den endelige løsning, vi forventer:

SimpleGeneticAlgorithm.runAlgorithm (50, "1011000100000100010000100000100111001000000100000100000000001111");

I ovenstående eksempel er Befolkning størrelse er 50, og den korrekte løsning er repræsenteret af den binære bitstreng, som vi kan ændre når som helst.

I det næste trin skal vi gemme vores ønskede løsning og skabe en tilfældig Befolkning:

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

Nu er vi klar til at køre programmets hovedsløjfe.

3.2. Fitnesscheck

I programmets hovedsløjfe skal vi evaluere hver Individuel af fitness-funktionen (med enkle ord, jo bedre er det Individuel er, jo højere værdi af fitnessfunktion det får):

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

Lad os starte med at forklare hvordan vi bliver bedst Individuel:

offentlig int getFitness (individuel person) {int fitness = 0; for (int i = 0; i <individual.getDefaultGeneLength () && i <løsning.længde; i ++) {hvis (individual.getSingleGene (i) == løsning [i]) {fitness ++; }} vende tilbage fitness }

Som vi kan se, sammenligner vi to Individuel objekter bit for bit. Hvis vi ikke kan finde en perfekt løsning, er vi nødt til at gå videre til næste trin, som er en udvikling af Befolkning.

3.3. Afkom

I dette trin er vi nødt til at oprette en ny Befolkning. Først skal vi Vælg to forældre Individuel genstande fra en Befolkning, alt efter deres kondition. Bemærk, at det er fordelagtigt at tillade det bedste Individuel fra den nuværende generation til at overføre til den næste, uændret. Denne strategi kaldes en Elitisme:

hvis (elitisme) {newPopulation.getIndividuals (). tilføj (0, pop.getFittest ()); elitismOffset = 1; } andet {elitismOffset = 0; }

For at vælge de to bedste Individuel genstande, vil vi anvende turneringsudvælgelsesstrategi:

privat individuel turnering Valg (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 (). tilføj (i, pop.getIndividual (randomId)); } Individuel fittest = turnering.getFittest (); vende tilbage mest }

Vinderen af ​​hver turnering (den med den bedste fitness) vælges til næste etape, dvs. Crossover:

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

I crossover bytter vi bits fra hver valgt Individuel på et tilfældigt valgt sted. Hele processen kører inden for følgende sløjfe:

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

Som vi kan se, placerer vi nye afkom i et nyt efter overgangen Befolkning. Dette trin kaldes Accept.

Endelig kan vi udføre en Mutation. Mutation bruges til at opretholde genetisk mangfoldighed fra en generation af a Befolkning til det næste. Vi brugte bit inversion type mutation, hvor tilfældige bits simpelthen inverteres:

privat ugyldig mutation (Individuel indiv) {for (int i = 0; i <indiv.getDefaultGeneLength (); i ++) {if (Math.random () <= mutationRate) {byte gen = (byte) Math.round (Math. tilfældig()); indiv.setSingleGene (i, gen); }}}

Alle typer af mutation og crossover er pænt beskrevet i denne vejledning.

Vi gentager derefter trin fra afsnit 3.2 og 3.3, indtil vi når en opsigelsesbetingelse, for eksempel den bedste løsning.

4. Tips og tricks

For at implementere en effektiv genetisk algoritme, skal vi indstille et sæt parametre. Dette afsnit skal give dig nogle grundlæggende anbefalinger til, hvordan du starter med de mest importerende parametre:

  • Crossover-sats - det skal være højt, ca. 80%-95%
  • Mutationsrate - det skal være meget lavt omkring 0.5%-1%.
  • Befolkningsstørrelse - god befolkningsstørrelse er ca. 20-30dog for nogle problemer er størrelserne 50-100 bedre
  • Udvælgelse - grundlæggende valg af roulettehjul kan bruges med begrebet elitisme
  • Crossover og mutationstype - det afhænger af kodning og problemet

Bemærk, at anbefalinger til tuning ofte er resultater af empiriske undersøgelser af genetiske algoritmer, og de kan variere baseret på de foreslåede problemer.

5. Konklusion

Denne vejledning introducerer det grundlæggende i genetiske algoritmer. Du kan lære om genetiske algoritmer uden nogen tidligere viden af dette område, der kun har grundlæggende computerprogrammeringsfærdigheder.

Den komplette kildekode til kodestykkerne i denne vejledning er tilgængelig i GitHub-projektet.

Bemærk også, at vi bruger Lombok til at generere getters og settere. Du kan kontrollere, hvordan du konfigurerer det korrekt i din IDE i denne artikel.

For yderligere eksempler på genetiske algoritmer, se alle artiklerne i vores serie:

  • Hvordan man designer en genetisk algoritme? (denne)
  • Det rejsende sælgerproblem i Java

$config[zx-auto] not found$config[zx-overlay] not found