Dizajnirajte genetski algoritam na Javi

1. Uvod

Cilj ove serije je da objasniti ideju genetskih algoritama.

Genetski algoritmi dizajnirani su za rješavanje problema koristeći iste procese kao u prirodi - koriste kombinaciju odabira, rekombinacije i mutacije kako bi razvili rješenje problema.

Počnimo s objašnjenjem koncepta tih algoritama koristeći najjednostavniji primjer binarnog genetskog algoritma.

2. Kako djeluju genetski algoritmi

Genetski algoritmi dio su evolucijskog računanja, što je područje umjetne inteligencije koje brzo raste.

Algoritam započinje s skup rješenja (predstavljen od pojedinci) pozvao populacija. Uzimaju se rješenja iz jedne populacije i koriste se za stvaranje a novo stanovništvo, jer postoji šansa da će nova populacija biti bolja od stare.

Pojedinci odabrani za oblikovanje novih rješenja (potomstvo) odabiru se prema njihovim kondicija - što su prikladnije, to više šanse za reprodukciju imaju.

3. Binarni genetski algoritam

Pogledajmo osnovni postupak za jednostavan genetski algoritam.

3.1. Inicijalizacija

U koraku inicijalizacije, mi generirati slučajno Populacija to služi kao prvo rješenje. Prvo, moramo odlučiti koliko je velik Populacija i što je konačno rješenje koje očekujemo:

SimpleGeneticAlgorithm.runAlgorithm (50, "1011000100000100010000100000100111001000000100000100000000001111");

U gornjem primjeru, Populacija veličina je 50, a ispravno rješenje predstavlja binarni bitni niz koji možemo promijeniti u bilo kojem trenutku.

U sljedećem ćemo koraku spremiti željeno rješenje i stvoriti slučajni slučaj Populacija:

setSolution (rješenje); Populacija myPop = nova populacija (veličina populacije, istina);

Sada smo spremni za pokretanje glavne petlje programa.

3.2. Provjera kondicije

U glavnoj petlji programa idemo procijeniti svaku Pojedinac funkcijom kondicije (jednostavnim riječima, to bolje Pojedinac je, što je veća vrijednost funkcije kondicije):

while (myPop.getFittest (). getFitness () <getMaxFitness ()) {System.out.println ("Generation:" + generationCount + "Pronađeni ispravni geni:" + myPop.getFittest (). getFitness ()); myPop = evolvePopulation (myPop); generationCount ++; }

Krenimo s objašnjenjem kako postajemo najsposobniji Pojedinac:

javni int getFitness (pojedinac) {int fitness = 0; za (int i = 0; i <individual.getDefaultGeneLength () && i <solution.length; i ++) {if (individual.getSingleGene (i) == rješenje [i]) {fitness ++; }} povratak kondicije; }

Kao što možemo primijetiti, uspoređujemo dvije Pojedinac objekti malo po malo. Ako ne možemo pronaći savršeno rješenje, moramo prijeći na sljedeći korak, a to je evolucija Populacija.

3.3. Potomstvo

U ovom koraku moramo stvoriti novi Populacija. Prvo, trebamo Odaberi dvoje roditelja Pojedinac predmeti iz a Populacija, prema njihovoj kondiciji. Imajte na umu da je korisno dopustiti najbolje Pojedinac sa sadašnje generacije da bi se prenijela na sljedeću, nepromijenjena. Ova se strategija naziva Elitizam:

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

Kako bi se odabrale dvije najbolje Pojedinac objekte, primijenit ćemo strategija odabira turnira:

privatni Pojedinačni turnirSelection (Population pop) {Population turnir = new Population (TourSize, false); for (int i = 0; i <размера turnira; i ++) {int randomId = (int) (Math.random () * pop.getIndividuals (). size ()); turnir.getIndividuals (). add (i, pop.getIndividual (randomId)); } Pojedinačno najprikladnije = turnir.getFittest (); povratak najprikladniji; }

Pobjednik svakog turnira (onaj s najboljom kondicijom) odabire se za sljedeću fazu, koja je Crossover:

private Individual crossover (Individual indiv1, Individual indiv2) {Individual newSol = novi Individual (); za (int i = 0; i <newSol.getDefaultGeneLength (); i ++) {if (Math.random () <= uniformRate) {newSol.setSingleGene (i, indiv1.getSingleGene (i)); } else {newSol.setSingleGene (i, indiv2.getSingleGene (i)); }} vrati newSol; }

U križanju zamijenimo bitove od svakog odabranog Pojedinac na slučajno odabranom mjestu. Cijeli se postupak izvodi unutar sljedeće petlje:

for (int i = elitismOffset; i <pop.getIndividuals (). size (); i ++) {Pojedinac indiv1 = selectionSelection (pop); Pojedinačno indiv2 = odabir turnira (pop); Pojedinac newIndiv = križanje (indiv1, indiv2); newPopulation.getIndividuals (). add (i, newIndiv); }

Kao što vidimo, nakon križanja, novo potomstvo smještamo u novo Populacija. Ovaj se korak naziva Prihvaćanje.

Napokon, možemo izvesti a Mutacija. Mutacija se koristi za održavanje genetske raznolikosti jedne generacije a Populacija sljedećem. Koristili smo inverzija bitova vrsta mutacije, gdje se slučajni bitovi jednostavno obrću:

mutacija privatne praznine (Individual indiv) {for (int i = 0; i <indiv.getDefaultGeneLength (); i ++) {if (Math.random () <= mutationRate) {byte gen = (byte) Math.round (Math. slučajni ()); indiv.setSingleGene (i, gen); }}}

Sve vrste Mutacije i Crossovera lijepo su opisane u ovom vodiču.

Zatim ponavljamo korake iz pododjeljka 3.2 i 3.3, sve dok ne postignemo uvjet prestanka, na primjer najbolje rješenje.

4. Savjeti i trikovi

Da bi provesti učinkovit genetski algoritam, moramo podesiti skup parametara. Ovaj odjeljak trebao bi vam dati neke osnovne preporuke kako započeti s najvažnijim parametrima:

  • Stopa križanja - trebao bi biti visok, otprilike 80%-95%
  • Stopa mutacije - trebao bi biti vrlo nizak, okolo 0.5%-1%.
  • Veličina stanovništva - dobra je populacija otprilike 20-30međutim, za neke su probleme veličine 50-100 bolje
  • Izbor - Osnovni, temeljni izbor ruleta može se koristiti s konceptom elitizam
  • Crossover i tip mutacije - ovisi o kodiranju i problemu

Imajte na umu da su preporuke za podešavanje često rezultat empirijskih studija genetskih algoritama i mogu se razlikovati, ovisno o predloženim problemima.

5. Zaključak

Ovaj vodič uvodi osnove genetskih algoritama. Možete naučiti o genetskim algoritmima bez ikakvih predznanja ovog područja, imajući samo osnovne vještine računalnog programiranja.

Kompletni izvorni kod za isječke koda u ovom vodiču dostupan je u projektu GitHub.

Također imajte na umu da Lombok koristimo za generiranje getera i postavljača. U ovom članku možete provjeriti kako ga ispravno konfigurirati u svom IDE-u.

Za daljnje primjere genetskih algoritama pogledajte sve članke naše serije:

  • Kako dizajnirati genetski algoritam? (ovaj)
  • Problem putujućeg trgovca na Javi