streamalism.org

1. Uvod

Cilj ove serije je objasniti ideju genetskih algoritama i prikazati najpoznatije implementacije.

U ovom uputstvu ćemo opisati vrlo moćnu Jenetics Java knjižnicu koja se može koristiti za rješavanje različitih problema s optimizacijom.

Ako smatrate da trebate naučiti više o genetskim algoritmima, preporučujemo da započnete s ovim člankom.

2. Kako to djeluje?

Prema službenim dokumentima, Jenetics je knjižnica koja se temelji na evolucijskom algoritmu napisanom na Javi. Evolucijski algoritmi korijene imaju u biologiji, jer koriste mehanizme nadahnute biološkom evolucijom, poput reprodukcije, mutacije, rekombinacije i selekcije.

Jenetics se provodi pomoću Jave Stream sučelje, tako da glatko radi s ostatkom Jave Stream API.

Glavne značajke su:

• minimalizacija bez trenja - nema potrebe za promjenom ili dotjerivanjem funkcije kondicije; možemo samo promijeniti konfiguraciju Motor razreda i spremni smo za početak prve prijave
• bez ovisnosti - ne postoje runtime biblioteke trećih strana potrebne za upotrebu Jenetics-a
• Java 8 spremna - puna podrška za Stream i lambda izrazi
• višenitni - evolucijski koraci mogu se izvoditi paralelno

Da bismo koristili Jenetics, moramo dodati sljedeću ovisnost u našu pom.xml:

 io.jenetics jenetics 3.7.0 

Najnoviju verziju možete pronaći u Maven Central.

3. Koristite slučajeve

Da bismo testirali sve značajke Jenetics, pokušat ćemo riješiti razne poznate probleme optimizacije, počevši od jednostavnog binarnog algoritma i završavajući problemom Knapsack.

3.1. Jednostavni genetski algoritam

Pretpostavimo da trebamo riješiti najjednostavniji binarni problem, gdje moramo optimizirati položaje 1 bita u kromosomu koji se sastoji od 0 i 1. Prvo moramo definirati tvornicu prikladnu za problem:

Tvornica gtf = Genotip.of (BitChromosome.of (10, 0.5));

Stvorili smo BitChromosome s duljinom od 10, a vjerojatnost da u kromosomu budu jednake 0,5.

Sada, kreirajmo okruženje za izvršavanje:

Motor motora = Engine.builder (SimpleGeneticAlgorithm :: eval, gtf) .build ();

The eval () metoda vraća broj bitova:

privatni Integer eval (Genotip gt) {return gt.getChromosome (). as (BitChromosome.class) .bitCount (); }

U posljednjem koraku započinjemo evoluciju i prikupljamo rezultate:

Rezultat genotipa = engine.stream () .limit (500) .collect (EvolutionResult.toBestGenotype ());

Konačni rezultat izgledat će slično ovome:

Prije evolucije: [00000010 | 11111100] Nakon evolucije: [00000000 | 11111111]

Uspjeli smo optimizirati položaj 1 u genu.

3.2. Problem zbroja podskupova

Drugi je slučaj upotrebe Jenetics rješavanje problema zbroja podskupova. Ukratko, izazov za optimizaciju je taj da, s obzirom na skup cijelih brojeva, moramo pronaći neprazan podskup čiji je zbroj nula.

Postoje preddefinirana sučelja u Jeneticsu za rješavanje takvih problema:

javna klasa SubsetSum provodi problem {// implementacija}

Kao što vidimo, implementiramo Problem, koji ima tri parametra:

• - vrsta argumenta funkcije fitnesa problema, u našem slučaju nepromjenjiva, poredana, fiksne veličine Cijeli broj slijed ISeq
• - tip gena s kojim evolucijski motor radi, u ovom je slučaju izbrojiv Cijeli broj geni EnumGene
• - vrsta rezultata funkcije kondicije; ovdje je Cijeli broj

Da biste koristili Problem sučelje, moramo nadjačati dvije metode:

@Preuzmi javnu funkciju fitness () {return podskup -> Math.abs (subset.stream () .mapToInt (Integer :: intValue) .sum ()); } @Preuzmi javni kodek codec () {return codecs.ofSubSet (basicSet, size); }

U prvom definiramo svoju fitnes funkciju, dok je drugi razred koji sadrži tvorničke metode za stvaranje uobičajenih kodiranja problema, na primjer, za pronalaženje najboljeg podskupa fiksne veličine iz zadanog osnovnog skupa, kao u našem slučaju.

Sada možemo prijeći na glavni dio. Na početku moramo stvoriti podskup koji ćemo koristiti u problemu:

Problem podskupine = od (500, 15, novi LCG64ShiftRandom (101010));

Napominjemo da koristimo LCG64ShiftRandom generator osigurava Jenetics. U sljedećem koraku gradimo motor našeg rješenja:

U sljedećem koraku gradimo motor našeg rješenja:

Motor engine = Engine.builder (problem) .minimizing () .maximalPhenotypeAge (5) .alterers (novi PartialMatchedCrossover (0.4), novi Mutator (0.3)) .build ();

Pokušavamo minimizirati rezultat (optimalno će rezultat biti 0) postavljanjem fenotipske dobi i osoba koje mijenjaju potomstvo. U sljedećem koraku možemo dobiti rezultat:

Fenotip rezultat = engine.stream () .limit (limit.bySteadyFitness (55)) .collect (EvolutionResult.toBestPhenotype ());

Napominjemo da koristimo bySteadyFitness () koji vraća predikat, koji će skratiti evolucijski tok ako se nakon datog broja generacija ne pronađe bolji fenotip i prikupi najbolji rezultat. Ako nam se posreći i ako postoji rješenje za nasumično stvoreni skup, vidjet ćemo nešto slično ovome:

Ako nam se posreći i ako postoji rješenje za nasumično stvoreni skup, vidjet ćemo nešto slično ovome:

[85|-76|178|-197|91|-106|-70|-243|-41|-98|94|-213|139|238|219] --> 0

Inače, zbroj podskupa bit će različit od 0.

3.3. Prvi problem u naprtnjači

Biblioteka Jenetics omogućuje nam rješavanje još sofisticiranijih problema, poput problema s knapsackom. Ukratko, u ovom problemu imamo ograničen prostor u svom naprtnjači i moramo odlučiti koje ćemo predmete staviti unutra.

Počnimo s definiranjem veličine vrećice i broja predmeta:

int nItems = 15; dvostruki ksSize = nItemtem * 100,0 / 3,0;

U sljedećem koraku generirat ćemo slučajni niz koji sadrži Predmet ruksaka objekti (definirani veličina i vrijednost polja) i stavit ćemo te predmete nasumično u naprtnjaču, koristeći metodu First Fit:

KnapsackFF ff = novi KnapsackFF (Stream.generate (KnapsackItem :: random) .limit (nItems) .toArray (KnapsackItem [] :: new), ksSize);

Dalje, moramo stvoriti Motor:

Motor motora = Engine.builder (ff, BitChromosome.of (nItems, 0.5)) .populationSize (500) .survivorsSelector (novi TournamentSelector (5)) .offspringSelector (novi RouletteWheelSelector ()) .alterers (novi Mutator (0.115), novi SinglePointCrossover (0,16)) .build ();

Ovdje treba napomenuti nekoliko točaka:

• broj stanovnika je 500
• potomci će se birati kroz odabir turnira i ruleta
• kao što smo to učinili u prethodnom pododjeljku, također moramo definirati izmjenitelje za novostvoreno potomstvo

Postoji i jedna vrlo važna značajka Jenetics. Lako možemo prikupiti sve statistike i uvide tijekom cijelog trajanja simulacije. To ćemo učiniti pomoću Evolucijska statistika razred:

Statistika EvolutionStatistics = EvolutionStatistics.ofNumber ();

Na kraju, pokrenimo simulacije:

Fenotip najbolje = engine.stream () .limit (bySteadyFitness (7)) .limit (100) .peek (statistika) .collect (toBestPhenotype ());

Napominjemo da ažuriramo statistiku procjene nakon svake generacije, koja je ograničena na 7 stalnih generacija i maksimalno 100 generacija ukupno. Detaljnije postoje dva moguća scenarija:

• postižemo 7 stabilnih generacija, a zatim simulacija prestaje
• ne možemo dobiti 7 stabilnih generacija za manje od 100 generacija, pa se simulacija zaustavlja zbog druge ograničiti()

Važno je ograničiti maksimalan broj generacija, inače se simulacije možda neće zaustaviti u razumnom vremenu.

Konačni rezultat sadrži puno podataka:

+ ------------------------------------------------- -------------------------- + | Statistika vremena | + ------------------------------------------------- -------------------------- + | Izbor: zbroj = 0,039207931000 s; srednja vrijednost = 0,003267327583 s | | Promjena: zbroj = 0,065145069000 s; srednja vrijednost = 0,005428755750 s | | Izračun kondicije: zbroj = 0,029678433000 s; srednja vrijednost = 0,002473202750 s | | Cjelokupno izvršenje: zbroj = 0,111383965000 s; srednja vrijednost = 0,009281997083 s | + ------------------------------------------------- -------------------------- + | Statistika evolucije | + ------------------------------------------------- -------------------------- + | Generacije: 12 | | Izmijenjeno: zbroj = 7 664; srednja vrijednost = 638,666666667 | | Ubijeno: zbroj = 0; srednja vrijednost = 0,000000000 | | Invalidi: zbroj = 0; srednja vrijednost = 0,000000000 | + ------------------------------------------------- -------------------------- + | Statistika stanovništva | + ------------------------------------------------- -------------------------- + | Dob: max = 10; srednja vrijednost = 1,792167; var = 4,657748 | | Fitness: | | min = 0,000000000000 | | maks. = 716,684883338605 | | srednja vrijednost = 587,012666759785 | | var = 17309,892287851708 | | std = 131,567063841418 | + ------------------------------------------------- -------------------------- +

Ovog smo puta u najbolji scenarij mogli staviti stavke ukupne vrijednosti 716,68. Također možemo vidjeti detaljne statistike evolucije i vremena.

Kako testirati?

To je prilično jednostavan postupak - samo otvorite glavnu datoteku povezanu s problemom i prvo pokrenite algoritam. Jednom kad imamo opću ideju, možemo se početi igrati s parametrima.

4. Zaključak

U ovom smo članku pokrivali značajke knjižnice Jenetics temeljene na stvarnim problemima optimizacije.

Kôd je dostupan kao Maven projekt na GitHubu. Imajte na umu da smo dali primjere koda za više izazova optimizacije, kao što su Springsteen Record (da, postoji!) I problemi s putničkim prodavačima.

Za sve članke u seriji, uključujući ostale primjere genetskih algoritama, pogledajte sljedeće poveznice:

• Kako dizajnirati genetski algoritam u Javi
• Problem putujućeg trgovca na Javi
• Optimizacija kolonije mrava
• Uvod u Jenetics knjižnicu (ovo)