streamalism.org

1. Inleiding

Het doel van deze serie is om het idee van genetische algoritmen uit te leggen en de meest bekende implementaties te tonen.

In deze tutorial zullen we beschrijven een zeer krachtige Jenetics Java-bibliotheek die kan worden gebruikt voor het oplossen van verschillende optimalisatieproblemen.

Als u denkt dat u meer over genetische algoritmen moet leren, raden we u aan om met dit artikel te beginnen.

2. Hoe werkt het?

Volgens de officiële documenten is Jenetics een bibliotheek die is gebaseerd op een evolutionair algoritme geschreven in Java. Evolutionaire algoritmen hebben hun wortels in de biologie, aangezien ze mechanismen gebruiken die zijn geïnspireerd door biologische evolutie, zoals reproductie, mutatie, recombinatie en selectie.

Jenetics wordt geïmplementeerd met behulp van Java Stroom interface, dus het werkt soepel met de rest van de Java Stroom API.

De belangrijkste kenmerken zijn:

• wrijvingsloze minimalisatie - het is niet nodig om de fitnessfunctie te wijzigen of aan te passen; we kunnen gewoon de configuratie van het Motor klas en we zijn klaar om onze eerste applicatie te starten
• afhankelijkheid gratis - er zijn geen runtime-bibliotheken van derden nodig om Jenetics te gebruiken
• Klaar voor Java 8 - volledige ondersteuning voor Stroom en lambda-uitdrukkingen
• meerdradig - evolutionaire stappen kunnen parallel worden uitgevoerd

Om Jenetics te gebruiken, moeten we de volgende afhankelijkheid toevoegen aan onze pom.xml:

 io.jenetics jenetics 3.7.0 

De nieuwste versie is te vinden in Maven Central.

3. Gebruik gevallen

Om alle functies van Jenetics te testen, zullen we proberen verschillende bekende optimalisatieproblemen op te lossen, beginnend bij het eenvoudige binaire algoritme en eindigend met het Knapzak-probleem.

3.1. Eenvoudig genetisch algoritme

Laten we aannemen dat we het eenvoudigste binaire probleem moeten oplossen, waarbij we de posities van de 1-bits in het chromosoom, bestaande uit nullen en enen, moeten optimaliseren. Eerst moeten we de fabriek definiëren die geschikt is voor het probleem:

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

We hebben het BitChromosome met een lengte van 10, en de kans op 1-en in het chromosoom gelijk aan 0,5.

Laten we nu de uitvoeringsomgeving maken:

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

De eval () methode geeft het aantal bits terug:

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

In de laatste stap starten we de evolutie en verzamelen we de resultaten:

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

Het uiteindelijke resultaat ziet er ongeveer zo uit:

Voor de evolutie: [00000010 | 11111100] Na de evolutie: [00000000 | 11111111]

We zijn erin geslaagd om de positie van 1'en in het gen te optimaliseren.

3.2. Subset Som Probleem

Een andere use case voor Jenetics is het oplossen van het probleem van de som van de subsets. Kort gezegd, de uitdaging om te optimaliseren is dat we, gegeven een reeks gehele getallen, een niet-lege subset moeten vinden waarvan de som nul is.

Er zijn voorgedefinieerde interfaces in Jenetics om dergelijke problemen op te lossen:

public class SubsetSum implementeert Problem { // implementatie }

Zoals we kunnen zien, implementeren we het Probleem, dat drie parameters heeft:

• - het argumenttype van de probleemfitnessfunctie, in ons geval een onveranderlijke, geordende, vaste grootte Geheel getal volgorde ISeq
• - het gentype waarmee de evolutie-engine werkt, in dit geval telbaar Geheel getal genen EnumGene
• - het resultaattype van de fitnessfunctie; hier is het een Geheel getal

Om de Probleem interface, moeten we twee methoden overschrijven:

@Override openbare functie fitness () {return subset -> Math.abs (subset.stream () .mapToInt (Integer :: intValue) .sum ()); } @Override openbare codec codec () {retour codecs.ofSubSet (basicSet, grootte); }

In de eerste definiëren we onze fitnessfunctie, terwijl de tweede een klasse is die fabrieksmethoden bevat voor het maken van veelvoorkomende probleemcoderingen, bijvoorbeeld om de beste subset met vaste grootte te vinden uit een bepaalde basisset, zoals in ons geval.

Nu kunnen we doorgaan naar het hoofdgedeelte. In het begin moeten we een subset maken om in de opgave te gebruiken:

SubsetSum probleem = van (500, 15, nieuwe LCG64ShiftRandom (101010));

Houd er rekening mee dat we de LCG64ShiftRandom generator geleverd door Jenetics. In de volgende stap bouwen we aan de motor van onze oplossing:

In de volgende stap bouwen we aan de motor van onze oplossing:

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

We proberen het resultaat te minimaliseren (optimaal is het resultaat 0) door de leeftijd van het fenotype in te stellen en de gebruikte alteratoren om het nageslacht te veranderen. In de volgende stap kunnen we het resultaat verkrijgen:

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

Houd er rekening mee dat we doorSteadyFitness () dat een predikaat retourneert, dat de evolutiestroom afkapt als er geen beter fenotype kan worden gevonden na het opgegeven aantal generaties en het beste resultaat oplevert. Als we geluk hebben, en er is een oplossing voor de willekeurig gemaakte set, zullen we iets soortgelijks zien:

Als we geluk hebben, en er is een oplossing voor de willekeurig gemaakte set, zullen we iets soortgelijks zien:

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

Anders is de som van de subset anders dan 0.

3.3. Knapzak First Fit Probleem

De Jenetics-bibliotheek stelt ons in staat om nog meer geavanceerde problemen op te lossen, zoals het Knapzak-probleem. Kort gezegd, bij dit probleem hebben we een beperkte ruimte in onze knapzak en moeten we beslissen welke items we erin willen stoppen.

Laten we beginnen met het definiëren van de zakgrootte en het aantal items:

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

In de volgende stap genereren we een willekeurige array met KnapzakItem objecten (gedefinieerd door grootte en waarde velden) en we plaatsen die items willekeurig in de knapzak, met behulp van de First Fit-methode:

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

Vervolgens moeten we het Motor:

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

Er zijn een paar punten om op te merken:

• populatiegrootte is 500
• het nageslacht wordt gekozen via de selecties van het toernooi en het roulettewiel
• zoals we in de vorige paragraaf hebben gedaan, moeten we ook de alteratoren voor de nieuw gecreëerde nakomelingen definiëren

Er is ook een heel belangrijk kenmerk van Jenetics. We kunnen eenvoudig alle statistieken en inzichten van de hele simulatieduur verzamelen. We gaan dit doen door de Evolution Statistieken klasse:

EvolutionStatistics-statistieken = EvolutionStatistics.ofNumber ();

Laten we tot slot de simulaties uitvoeren:

Beste fenotype = engine.stream () .limit (bySteadyFitness (7)) .limit (100) .peek (statistieken) .collect (toBestPhenotype ());

Houd er rekening mee dat we de evaluatiestatistieken na elke generatie bijwerken, die beperkt is tot 7 stabiele generaties en in totaal maximaal 100 generaties. Meer in detail zijn er twee mogelijke scenario's:

• we bereiken 7 gestage generaties, dan stopt de simulatie
• we kunnen geen 7 stabiele generaties krijgen in minder dan 100 generaties, dus de simulatie stopt vanwege de tweede limiet()

Het is belangrijk om een ​​maximale generatielimiet te hebben, anders stoppen de simulaties mogelijk niet binnen een redelijke tijd.

Het eindresultaat bevat veel informatie:

+ ------------------------------------------------- -------------------------- + | Tijdstatistieken | + ------------------------------------------------- -------------------------- + | Selectie: som = 0,039207931000 s; gemiddelde = 0,003267327583 s | | Wijzigen: som = 0,065145069000 s; gemiddelde = 0,005428755750 s | | Fitnessberekening: som = 0,029678433000 s; gemiddelde = 0,002473202750 s | | Totale uitvoering: som = 0,111383965000 s; gemiddelde = 0,009281997083 s | + ------------------------------------------------- -------------------------- + | Evolutiestatistieken | + ------------------------------------------------- -------------------------- + | Generaties: 12 | | Gewijzigd: som = 7664; gemiddelde = 638,666666667 | | Gedood: som = 0; gemiddelde = 0,000000000 | | Ongeldig: som = 0; gemiddelde = 0,000000000 | + ------------------------------------------------- -------------------------- + | Bevolkingsstatistieken | + ------------------------------------------------- -------------------------- + | Leeftijd: max = 10; gemiddelde = 1.792167; var = 4,657748 | | Geschiktheid: | | min = 0,000000000000 | | max = 716,684883338605 | | gemiddelde = 587,012666759785 | | var = 17309,892287851708 | | std = 131,567063841418 | + ------------------------------------------------- -------------------------- +

Deze keer konden we items met een totale waarde van 716,68 in het beste scenario plaatsen. We kunnen ook de gedetailleerde statistieken van evolutie en tijd zien.

Hoe te testen?

Het is een vrij eenvoudig proces - open gewoon het hoofdbestand met betrekking tot het probleem en voer eerst het algoritme uit. Als we eenmaal een algemeen idee hebben, kunnen we beginnen met spelen met de parameters.

4. Conclusie

In dit artikel hebben we de functies van de Jenetics-bibliotheek besproken op basis van echte optimalisatieproblemen.

De code is beschikbaar als een Maven-project op GitHub. Houd er rekening mee dat we de codevoorbeelden hebben gegeven voor meer optimalisatie-uitdagingen, zoals het Springsteen-record (ja, het bestaat!) En zakenreizigersproblemen.

Bekijk de volgende links voor alle artikelen in de serie, inclusief andere voorbeelden van genetische algoritmen:

• Hoe een genetisch algoritme in Java te ontwerpen
• Het handelsreizigersprobleem in Java
• Optimalisatie van de mierenkolonie
• Inleiding tot de Jenetics-bibliotheek (dit)