Tervezzen genetikai algoritmust Java-ban

1. Bemutatkozás

Ennek a sorozatnak az a célja, hogy magyarázza el a genetikai algoritmusok gondolatát.

A genetikai algoritmusokat a problémák megoldására tervezték ugyanazokkal a folyamatokkal, mint a természetben - a szelekció, a rekombináció és a mutáció kombinációját használják a probléma megoldásának fejlesztésére.

Kezdjük azzal, hogy elmagyarázzuk ezen algoritmusok fogalmát a legegyszerűbb bináris genetikai algoritmus példával.

2. Hogyan működnek a genetikai algoritmusok

A genetikai algoritmusok az evolúciós számítás részei, amely a mesterséges intelligencia gyorsan növekvő területe.

Egy algoritmus a-val kezdődik megoldások halmaza (képviseli: egyének) hívott népesség. Egy populációból származó megoldásokat veszünk és használunk a új népesség, mivel van esély arra, hogy az új népesség jobb legyen, mint a régi.

Azok a személyek, akiket új megoldások kialakítására választottak (utódok) azoknak megfelelően vannak kiválasztva fitnesz - minél alkalmasabbak, annál nagyobb az esélyük a szaporodásra.

3. Bináris genetikai algoritmus

Vessünk egy pillantást az egyszerű genetikai algoritmus alapvető folyamatára.

3.1. Inicializálás

Az inicializálási lépésben mi generál egy véletlenszerűt Népesség amely első megoldásként szolgál. Először el kell döntenünk, hogy mekkora a Népesség lesz és mi a végső megoldás, amire számítunk:

SimpleGeneticAlgorithm.runAlgorithm (50, "10110001000001000100001000001001110010000001000001000000000000001111");

A fenti példában a Népesség méret 50, és a helyes megoldást a bináris bit húr képviseli, amelyet bármikor megváltoztathatunk.

A következő lépésben menteni fogjuk a kívánt megoldást és létrehozunk egy véletlenszerűt Népesség:

setSolution (megoldás); Populáció myPop = new Population (populációméret, igaz);

Most már készen állunk a program fő ciklusának futtatására.

3.2. Fitness ellenőrzés

A program fő ciklusában erre megyünk értékelje mindegyiket Egyedi a fitnesz funkcióval (egyszerű szavakkal, annál jobb a Egyedi azaz a fitnesz funkció magasabb értéke):

while (myPop.getFittest (). getFitness () <getMaxFitness ()) {System.out.println ("Generation:" + generationCount + "Helyes gének találhatók:" + myPop.getFittest (). getFitness ()); myPop = evolvePopulation (myPop); generationCount ++; }

Kezdjük a magyarázattal hogyan kapjuk meg a legjobban Egyedi:

public int getFitness (Egyéni egyén) {int fitnesz = 0; for (int i = 0; i <individual.getDefaultGeneLength () && i <megoldás.length; i ++) {if (individual.getSingleGene (i) == megoldás [i]) {fitnesz ++; }} visszatér fitnesz; }

Amint megfigyelhetjük, kettőt hasonlítunk össze Egyedi tárgyak apránként. Ha nem találunk tökéletes megoldást, akkor folytatnunk kell a következő lépést, amely a Népesség.

3.3. Utódok

Ebben a lépésben létre kell hoznunk egy újat Népesség. Először is meg kell Válassza a lehetőséget két szülő Egyedi tárgyak a Népesség, alkalmasságuknak megfelelően. Felhívjuk figyelmét, hogy előnyös a legjobbat megengedni Egyedi a jelenlegi generációtól, hogy változatlanul átvigyék a következőre. Ezt a stratégiát an-nak hívják Elitizmus:

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

Két legjobb kiválasztása érdekében Egyedi tárgyakat, alkalmazni fogjuk verseny kiválasztási stratégia:

privát Egyéni versenySelection (Population pop) {Népességi verseny = new Population (tournamentSize, false); mert (int i = 0; i <tournamentSize; i ++) {int randomId = (int) (Math.random () * pop.getIndividuals (). size ()); tournament.getIndividuals (). add (i, pop.getIndividual (randomId)); } Individual fittest = verseny.getFittest (); visszatérő fittest; }

Az egyes versenyek győztesét (a legjobb kondíciójúakat) kiválasztják a következő szakaszra, azaz Crossover:

magánszemély crossover (Egyéni indiv1, Egyéni indiv2) {Egyéni newSol = új Egyéni (); for (int i = 0; i <newSol.getDefaultGeneLength (); i ++) {if (Math.random () <= uniformRate) {newSol.setSingleGene (i, indiv1.getSingleGene (i)); } else {newSol.setSingleGene (i, indiv2.getSingleGene (i)); }} return newSol; }

A crossover-ben biteket cserélünk mindegyik kiválasztottról Egyedi véletlenszerűen kiválasztott helyen. Az egész folyamat a következő cikluson belül fut:

for (int i = elitismOffset; i <pop.getIndividuals (). size (); i ++) {Individual indiv1 = tournamentSelection (pop); Egyéni indiv2 = tournamentSelection (pop); Individual newIndiv = crossover (indiv1, indiv2); newPopulation.getIndividuals (). add (i, newIndiv); }

Mint láthatjuk, a keresztezés után új utódokat helyezünk egy újba Népesség. Ezt a lépést nevezzük Elfogadás.

Végül elvégezhetjük a Mutáció. A mutációt a genetikai sokféleség fenntartására használják a Népesség a következőhöz. Használtuk a bit inverzió a mutáció típusa, ahol a véletlenszerű biteket egyszerűen megfordítják:

privát void mutáció (Individual indiv) {for (int i = 0; i <indiv.getDefaultGeneLength (); i ++) {if (Math.random () <= mutationRate) {byte gene = (byte) Math.round (Math. véletlen()); indiv.setSingleGene (i, gén); }}}

A mutáció és a crossover minden típusát jól ismertetjük ebben az oktatóanyagban.

Ezután megismételjük a 3.2 és 3.3 alpontok lépéseit, amíg elérjük a felmondási feltételt, például a legjobb megoldást.

4. Tippek és trükkök

Azért, hogy hatékony genetikai algoritmus megvalósítása, beállítanunk kell egy paraméterkészletet. Ebben a szakaszban néhány alapvető javaslatot kell megadnia, hogyan kezdje a legtöbb importáló paramétert:

  • Crossover arány - magasnak kell lennie, kb 80%-95%
  • Mutációs ráta - nagyon alacsonynak kell lennie, körülötte 0.5%-1%.
  • Népesség - a jó népességszám kb 20-30néhány probléma esetén azonban az 50-100-as méret jobb
  • Kiválasztás - alap rulett kerék kiválasztása fogalmával használható elitizmus
  • Crossover és mutáció típusa - a kódolástól és a problémától függ

Felhívjuk figyelmét, hogy a hangolásra vonatkozó ajánlások gyakran a genetikai algoritmusokkal kapcsolatos empirikus vizsgálatok eredményei, és a javasolt problémák alapján változhatnak.

5. Következtetés

Ez az oktatóanyag bemutatja a genetikai algoritmusok alapjait. Megismerheti a genetikai algoritmusokat minden előzetes tudás nélkül csak alapvető számítógépes programozási ismeretekkel rendelkezik.

Az oktatóanyag kódrészleteinek teljes forráskódja a GitHub projektben érhető el.

Felhívjuk figyelmét arra is, hogy a Lombokot használjuk getterek és beállítók előállításához. Ebben a cikkben ellenőrizheti, hogyan kell helyesen konfigurálni az IDE-jében.

A genetikai algoritmusok további példáit nézze meg sorozatunk összes cikkét:

  • Hogyan tervezzünk genetikai algoritmust? (ezt)
  • Az utazó eladó problémája a Java-ban