streamalism.org

1. Introduktion

Formålet med denne serie er at forklare ideen om genetiske algoritmer og vise de mest kendte implementeringer.

I denne vejledning vil vi beskrive et meget kraftfuldt Jenetics Java-bibliotek, der kan bruges til at løse forskellige optimeringsproblemer.

Hvis du føler, at du har brug for at lære mere om genetiske algoritmer, anbefaler vi, at du starter med denne artikel.

2. Hvordan fungerer det?

Ifølge sine officielle dokumenter er Jenetics et bibliotek baseret på en evolutionær algoritme skrevet i Java. Evolutionære algoritmer har deres rødder i biologi, da de bruger mekanismer inspireret af biologisk evolution, såsom reproduktion, mutation, rekombination og selektion.

Jenetics implementeres ved hjælp af Java Strøm interface, så det fungerer problemfrit med resten af ​​Java Strøm API.

De vigtigste funktioner er:

• friktionsløs minimering - der er ikke behov for at ændre eller justere fitnessfunktionen vi kan bare ændre konfigurationen af Motor klasse, og vi er klar til at starte vores første ansøgning
• afhængighedsfri - der er ingen runtime-tredjepartsbiblioteker nødvendige for at bruge Jenetics
• Java 8 klar - fuld støtte til Strøm og lambda-udtryk
• flertrådet - evolutionære trin kan udføres parallelt

For at bruge Jenetics skal vi tilføje følgende afhængighed i vores pom.xml:

 io.jenetics jenetics 3.7.0 

Den nyeste version kan findes i Maven Central.

3. Brug sager

For at teste alle funktioner i Jenetics forsøger vi at løse forskellige kendte optimeringsproblemer, startende fra den enkle binære algoritme og slutter med Knapsack-problemet.

3.1. Enkel genetisk algoritme

Lad os antage, at vi har brug for at løse det enkleste binære problem, hvor vi har brug for at optimere positionerne for de 1 bits i kromosomet bestående af 0'er og 1'er. Først skal vi definere fabrikken, der passer til problemet:

Fabrik gtf = Genotype.of (BitChromosome.of (10, 0,5));

Vi oprettede Bitkromosom med en længde på 10 og sandsynligheden for at have 1'er i kromosomet lig med 0,5.

Lad os nu oprette eksekveringsmiljøet:

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

Det eval () metode returnerer bitantal:

privat heltaleval (Genotype gt) {return gt.getChromosome (). som (BitChromosome.class) .bitCount (); }

I det sidste trin starter vi udviklingen og samler resultaterne:

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

Det endelige resultat vil ligne dette:

Før udviklingen: [00000010 | 11111100] Efter udviklingen: [00000000 | 11111111]

Det lykkedes os at optimere placeringen af ​​1'er i genet.

3.2. Delmængde sum problem

En anden brugssag for Jenetics er at løse delmængdeproblemet. Kort fortalt er udfordringen med at optimere, at vi i lyset af et sæt heltal skal finde en ikke-tom delmængde, hvis sum er nul.

Der er foruddefinerede grænseflader i Jenetics for at løse sådanne problemer:

offentlig klasse SubsetSum implementerer Problem {// implementering}

Som vi kan se, implementerer vi Problem, der har tre parametre:

• - argumenttypen for problemets fitnessfunktion, i vores tilfælde en uforanderlig, ordnet, fast størrelse Heltal sekvens ISeq
• - gentypen, som udviklingsmotoren arbejder med, i dette tilfælde tællelig Heltal gener EnumGene
• - resultattypen af ​​fitnessfunktionen her er det en Heltal

For at bruge Problem interface, skal vi tilsidesætte to metoder:

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

I den første definerer vi vores fitnessfunktion, mens den anden er en klasse, der indeholder fabriksmetoder til at oprette almindelige problemkodninger, for eksempel for at finde den bedste delmængde i fast størrelse fra et givet basissæt, som i vores tilfælde.

Nu kan vi gå videre til hoveddelen. I starten er vi nødt til at oprette en delmængde, der skal bruges i problemet:

SubsetSum problem = af (500, 15, ny LCG64ShiftRandom (101010));

Bemærk, at vi bruger LCG64ShiftRandom generator leveret af Jenetics. I det næste trin bygger vi motoren til vores løsning:

I det næste trin bygger vi motoren til vores løsning:

Motor motor = Engine.builder (problem) .minimizing () .maximalPhenotypeAge (5). alterers (nye PartiallyMatchedCrossover (0.4), ny Mutator (0.3)) .build ();

Vi forsøger at minimere resultatet (optimalt bliver resultatet 0) ved at indstille fænotypealderen og ændringer, der bruges til at ændre afkom. I det næste trin kan vi opnå resultatet:

Fænotype resultat = engine.stream () .limit (limit.bySteadyFitness (55)) .collect (EvolutionResult.toBestPhenotype ());

Bemærk, at vi bruger afSteadyFitness () der returnerer et predikat, som vil afkorte udviklingsstrømmen, hvis der ikke kunne findes nogen bedre fænotype efter det givne antal generationer og samler det bedste resultat. Hvis vi bliver heldige, og der er en løsning på det tilfældigt oprettede sæt, ser vi noget der ligner dette:

Hvis vi bliver heldige, og der er en løsning på det tilfældigt oprettede sæt, ser vi noget der ligner dette:

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

Ellers vil summen af ​​delmængde være forskellig fra 0.

3.3. Rygsæk First Fit Problem

Jenetics-biblioteket giver os mulighed for at løse endnu mere sofistikerede problemer, såsom Knapsack-problemet. Kort sagt har vi i dette problem en begrænset plads i vores rygsæk, og vi er nødt til at beslutte, hvilke genstande vi skal sætte inde.

Lad os starte med at definere posens størrelse og antal varer:

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

I det næste trin genererer vi et tilfældigt array, der indeholder Rygsæk objekter (defineret af størrelse og værdi felter), og vi lægger disse varer tilfældigt inde i rygsækken ved hjælp af First Fit-metoden:

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

Dernæst skal vi oprette 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 ();

Der er et par punkter at bemærke her:

• befolkningens størrelse er 500
• afkomene vælges gennem valg af turnering og roulettehjul
• som vi gjorde i det foregående underafsnit, er vi også nødt til at definere omskifterne for det nyoprettede afkom

Der er også et meget vigtigt træk ved Jenetics. Vi kan nemt indsamle alle statistikker og indsigter fra hele simuleringsvarigheden. Vi vil gøre dette ved at bruge EvolutionStatistics klasse:

EvolutionStatistics statistik = EvolutionStatistics.ofNumber ();

Lad os endelig køre simuleringerne:

Fænotype bedst = engine.stream () .limit (bySteadyFitness (7)) .limit (100) .peek (statistik) .collect (toBestPhenotype ());

Bemærk, at vi opdaterer evalueringsstatistikkerne efter hver generation, som er begrænset til 7 stabile generationer og maksimalt 100 generationer i alt. Mere detaljeret er der to mulige scenarier:

• vi opnår 7 stabile generationer, så stopper simuleringen
• vi kan ikke få 7 stabile generationer på mindre end 100 generationer, så simuleringen stopper på grund af den anden begrænse()

Det er vigtigt at have maksimumsgrænser for generationer, ellers stopper simuleringerne muligvis ikke inden for en rimelig tid.

Det endelige resultat indeholder en masse information:

+ ------------------------------------------------- -------------------------- + | Tidsstatistikker | + ------------------------------------------------- -------------------------- + | Valg: sum = 0,039207931000 s; gennemsnit = 0,003267327583 s | | Ændring: sum = 0,065145069000 s; gennemsnit = 0,005428755750 s | | Fitnessberegning: sum = 0,029678433000 s; gennemsnit = 0,002473202750 s | | Samlet udførelse: sum = 0,111383965000 s; gennemsnit = 0,009281997083 s | + ------------------------------------------------- -------------------------- + | Evolutionsstatistikker + ------------------------------------------------- -------------------------- + | Generationer: 12 | | Ændret: sum = 7664; gennemsnit = 638,666666667 | | Dræbt: sum = 0; gennemsnit = 0,000000000 | | Ugyldige: sum = 0; gennemsnit = 0,000000000 | + ------------------------------------------------- -------------------------- + | Befolkningsstatistikker + ------------------------------------------------- -------------------------- + | Alder: max = 10; middelværdi = 1,792167; var = 4.6657748 | | Fitness: | | min = 0,000000000000 | | maks = 716,684883338605 | | gennemsnit = 587,012666759785 | | var = 17309,892287851708 | | std = 131,567063841418 | + ------------------------------------------------- -------------------------- +

Denne særlige tid var vi i stand til at sætte varer med en samlet værdi på 716,68 i det bedste scenario. Vi kan også se de detaljerede statistikker over evolution og tid.

Hvordan tester man?

Det er en ret simpel proces - bare åbn hovedfilen, der er relateret til problemet, og kør først algoritmen. Når vi først har en generel idé, kan vi begynde at lege med parametrene.

4. Konklusion

I denne artikel dækkede vi Jenetics-biblioteksfunktionerne baseret på reelle optimeringsproblemer.

Koden er tilgængelig som et Maven-projekt på GitHub. Bemærk, at vi leverede kodeeksemplerne til flere optimeringsudfordringer, såsom Springsteen Record (ja, den eksisterer!) Og Travelsalgsproblemer.

For alle artikler i serien, inklusive andre eksempler på genetiske algoritmer, skal du tjekke følgende links:

• Sådan designes en genetisk algoritme i Java
• Det rejsende sælgerproblem i Java
• Ant Colony Optimization
• Introduktion til Jenetics-biblioteket (dette)