streamalism.org

1. Introduksjon

Målet med denne serien er å forklare ideen om genetiske algoritmer og vise de mest kjente implementeringene.

I denne opplæringen vil vi beskrive et veldig kraftig Jenetics Java-bibliotek som kan brukes til å løse ulike optimaliseringsproblemer.

Hvis du føler at du trenger å lære mer om genetiske algoritmer, anbefaler vi å starte med denne artikkelen.

2. Hvordan fungerer det?

I følge de offisielle dokumentene er Jenetics et bibliotek basert på en evolusjonær algoritme skrevet på Java. Evolusjonære algoritmer har sine røtter i biologi, da de bruker mekanismer inspirert av biologisk evolusjon, som reproduksjon, mutasjon, rekombinasjon og seleksjon.

Jenetics er implementert ved hjelp av Java Strøm grensesnitt, slik at det fungerer greit med resten av Java Strøm API.

Hovedtrekkene er:

• friksjonsfri minimering - det er ikke nødvendig å endre eller justere treningsfunksjonen; vi kan bare endre konfigurasjonen av Motor klasse og vi er klare til å starte vår første søknad
• avhengighetsfri - det er ingen runtime tredjepartsbiblioteker som trengs for å bruke Jenetics
• Java 8 klar - full støtte for Strøm og lambdauttrykk
• flertrådet - evolusjonære trinn kan utføres parallelt

For å kunne bruke Jenetics, må vi legge til følgende avhengighet i vår pom.xml:

 io.jenetics jenetics 3.7.0 

Den siste versjonen finner du i Maven Central.

3. Bruk saker

For å teste alle funksjonene i Jenetics, vil vi prøve å løse forskjellige kjente optimaliseringsproblemer, med utgangspunkt i den enkle binære algoritmen og slutter med Knapsack-problemet.

3.1. Enkel genetisk algoritme

La oss anta at vi trenger å løse det enkleste binære problemet, der vi trenger å optimalisere posisjonene til 1 bitene i kromosomet bestående av 0 og 1. Først må vi definere fabrikken som passer for problemet:

Fabrikk gtf = Genotype.of (BitChromosome.of (10, 0.5));

Vi opprettet Bitkromosom med en lengde på 10, og sannsynligheten for å ha 1 i kromosomet lik 0,5.

La oss nå lage kjøringsmiljøet:

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

De eval () metoden returnerer bitantallet:

private Integer eval (Genotype gt) {return gt.getChromosome (). as (BitChromosome.class) .bitCount (); }

I det siste trinnet starter vi evolusjonen og samler resultatene:

Genotype-resultat = engine.stream () .limit (500) .collect (EvolutionResult.toBestGenotype ());

Det endelige resultatet vil se ut som dette:

Før evolusjonen: [00000010 | 11111100] Etter evolusjonen: [00000000 | 11111111]

Vi klarte å optimalisere posisjonen til 1 i genet.

3.2. Delsett Sum-problem

En annen brukssak for Jenetics er å løse delmengdesummen. Kort fortalt er utfordringen med å optimalisere at gitt et sett med heltall, må vi finne en ikke-tom delmengde som har null.

Det er forhåndsdefinerte grensesnitt i Jenetics for å løse slike problemer:

offentlig klasse SubsetSum implementerer Problem { // gjennomføring }

Som vi kan se, implementerer vi Problem, som har tre parametere:

• - argumenttypen for problemets treningsfunksjon, i vårt tilfelle en uforanderlig, ordnet, fast størrelse Heltall sekvens ISeq
• - gentypen evolusjonsmotoren jobber med, i dette tilfellet, tellbar Heltall gener EnumGene
• - resultatet av treningsfunksjonen; her er det en Heltall

For å bruke Problem grensesnitt, må vi overstyre to metoder:

@Override public Function fitness () {return subset -> Math.abs (subset.stream () .mapToInt (Integer :: intValue) .sum ()); } @ Override public Codec codec () {return codecs.ofSubSet (basicSet, size); }

I den første definerer vi treningsfunksjonen vår, mens den andre er en klasse som inneholder fabrikkmetoder for å lage vanlige problemkodinger, for eksempel for å finne den beste delmengden i fast størrelse fra et gitt basissett, som i vårt tilfelle.

Nå kan vi gå videre til hoveddelen. I begynnelsen må vi lage et delsett som skal brukes i problemet:

SubsetSum problem = of (500, 15, new LCG64ShiftRandom (101010));

Vær oppmerksom på at vi bruker LCG64ShiftRandom generator levert av Jenetics. I neste trinn bygger vi motoren til løsningen vår:

I neste trinn bygger vi motoren til løsningen vår:

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

Vi prøver å minimere resultatet (optimalt blir resultatet 0) ved å sette fenotypen alder og alterers brukes til å endre avkom. I neste trinn kan vi oppnå resultatet:

Fenotype resultat = engine.stream () .limit (limit.bySteadyFitness (55)) .collect (EvolutionResult.toBestPhenotype ());

Vær oppmerksom på at vi bruker avSteadyFitness () som returnerer et predikat, som vil trunke evolusjonsstrømmen hvis ingen bedre fenotype kunne bli funnet etter det gitte antall generasjoner og samle det beste resultatet. Hvis vi blir heldige, og det er en løsning på det tilfeldig opprettede settet, ser vi noe som ligner på dette:

Hvis vi blir heldige, og det er en løsning på det tilfeldig opprettede settet, ser vi noe som ligner på dette:

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

Ellers vil summen av delmengde være forskjellig fra 0.

3.3. Ryggsekk First Fit Problem

Jenetics-biblioteket lar oss løse enda mer sofistikerte problemer, for eksempel Knapsack-problemet. Kort sagt, i dette problemet har vi begrenset plass i ryggsekken, og vi må bestemme hvilke ting vi skal legge inn.

La oss begynne med å definere posens størrelse og antall artikler:

int nItems = 15; dobbelt ksSize = nItems * 100.0 / 3.0;

I neste trinn genererer vi et tilfeldig utvalg som inneholder Ryggsekk objekter (definert av størrelse og verdi felt) og vi vil plassere disse elementene tilfeldig i ryggsekken ved hjelp av First Fit-metoden:

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

Deretter må vi lage Motor:

Engine engine = Engine.builder (ff, BitChromosome.of (nItems, 0.5)) .populationSize (500) .survivorsSelector (new TournamentSelector (5)) .offspringSelector (new RouletteWheelSelector ()). Alterers (new Mutator (0.115), new SinglePointCrossover (0.16)) .build ();

Det er noen få punkter å merke seg her:

• befolkningsstørrelsen er 500
• avkommet vil bli valgt gjennom valg av turnering og roulettehjul
• som vi gjorde i forrige underavsnitt, må vi også definere omformerne for det nyopprettede avkom

Det er også en veldig viktig egenskap ved Jenetics. Vi kan enkelt samle all statistikk og innsikt fra hele simuleringsvarigheten. Vi skal gjøre dette ved å bruke EvolutionStatistics klasse:

EvolutionStatistics statistikk = EvolutionStatistics.ofNumber ();

Til slutt, la oss kjøre simuleringene:

Fenotype best = engine.stream () .limit (bySteadyFitness (7)) .limit (100) .peek (statistikk) .collect (toBestPhenotype ());

Vær oppmerksom på at vi oppdaterer evalueringsstatistikken etter hver generasjon, som er begrenset til 7 jevn generasjon og maksimalt 100 generasjoner totalt. Mer detaljert er det to mulige scenarier:

• vi oppnår 7 jevne generasjoner, så stopper simuleringen
• vi kan ikke få 7 stødige generasjoner på mindre enn 100 generasjoner, så simuleringen stopper på grunn av den andre grense()

Det er viktig å ha maksimal generasjonsgrense, ellers kan det hende at simuleringene ikke stopper på rimelig tid.

Det endelige resultatet inneholder mye informasjon:

+ ------------------------------------------------- -------------------------- + | Tidsstatistikk | + ------------------------------------------------- -------------------------- + | Utvalg: sum = 0,039207931000 s; gjennomsnitt = 0,003267327583 s | | Endring: sum = 0,065145069000 s; gjennomsnitt = 0,005428755750 s | | Treningsberegning: sum = 0,029678433000 s; gjennomsnitt = 0,002473202750 s | | Samlet utførelse: sum = 0,111383965000 s; gjennomsnitt = 0,009281997083 s | + ------------------------------------------------- -------------------------- + | Evolusjonsstatistikk | + ------------------------------------------------- -------------------------- + | Generasjoner: 12 | | Endret: sum = 7664; gjennomsnitt = 638,666666667 | | Drepte: sum = 0; gjennomsnitt = 0,000000000 | | Ugyldige: sum = 0; gjennomsnitt = 0,000000000 | + ------------------------------------------------- -------------------------- + | Befolkningsstatistikk + ------------------------------------------------- -------------------------- + | Alder: maks = 10; gjennomsnitt = 1,792167; var = 4,657748 | | Trening: | | min = 0,000000000000 | | maks = 716,684883338605 | | gjennomsnitt = 587,012666759785 | | var = 17309,892287851708 | | std = 131,567063841418 | + ------------------------------------------------- -------------------------- +

Denne spesielle tiden klarte vi å sette varer med en totalverdi på 716,68 i det beste scenariet. Vi kan også se detaljert statistikk over evolusjon og tid.

Hvordan teste?

Det er en ganske enkel prosess - bare åpne hovedfilen relatert til problemet og kjør først algoritmen. Når vi har en generell ide, kan vi begynne å spille med parametrene.

4. Konklusjon

I denne artikkelen dekket vi Jenetics-biblioteksfunksjonene basert på reelle optimaliseringsproblemer.

Koden er tilgjengelig som et Maven-prosjekt på GitHub. Vær oppmerksom på at vi ga kodeeksemplene for flere optimaliseringsutfordringer, for eksempel problemer med Springsteen Record (ja, den eksisterer!) Og Travelling.

For alle artikler i serien, inkludert andre eksempler på genetiske algoritmer, sjekk ut følgende lenker:

• Hvordan lage en genetisk algoritme i Java
• Det reisende selgerproblemet i Java
• Ant Colony Optimization
• Introduksjon til Jenetics-biblioteket (dette)