streamalism.org

1. Inleiding

Het doel van deze serie is om het idee van genetische algoritmen uitleggen.

Genetische algoritmen zijn ontworpen om problemen op te lossen door dezelfde processen te gebruiken als in de natuur - ze gebruiken een combinatie van selectie, recombinatie en mutatie om een ​​oplossing voor een probleem te ontwikkelen.

Laten we beginnen met het concept van die algoritmen uit te leggen aan de hand van het eenvoudigste voorbeeld van een binair genetisch algoritme.

2. Hoe genetische algoritmen werken

Genetische algoritmen maken deel uit van evolutionair computergebruik, een snelgroeiend gebied van kunstmatige intelligentie.

Een algoritme begint met een reeks oplossingen (vertegenwoordigd door individuen) gebeld bevolking. Oplossingen van één populatie worden genomen en gebruikt om een nieuwe bevolking, aangezien de kans bestaat dat de nieuwe populatie beter zal zijn dan de oude.

Individuen die worden gekozen om nieuwe oplossingen te vormen (nakomelingen) worden geselecteerd op basis van hun fitness - hoe geschikter ze zijn, hoe meer kans ze hebben om zich voort te planten.

3. Binair genetisch algoritme

Laten we eens kijken naar het basisproces voor een eenvoudig genetisch algoritme.

3.1. Initialisatie

In de initialisatiestap, we genereer een willekeurig Bevolking dat dient als een eerste oplossing. Eerst moeten we beslissen hoe groot de Bevolking zal zijn en wat is de uiteindelijke oplossing die we verwachten:

SimpleGeneticAlgorithm.runAlgorithm (50, "1011000100000100010000100000100111001000000100000100000000001111");

In het bovenstaande voorbeeld is de Bevolking grootte is 50, en de juiste oplossing wordt weergegeven door de binaire bitstring die we op elk moment kunnen wijzigen.

In de volgende stap gaan we onze gewenste oplossing opslaan en een random Bevolking:

setSolution (oplossing); Populatie myPop = nieuwe populatie (populatiegrootte, waar);

Nu zijn we klaar om de hoofdlus van het programma uit te voeren.

3.2. Geschiktheidscontrole

In de hoofdlus van het programma gaan we evalueer elk Individueel door de fitnessfunctie (in eenvoudige bewoordingen, hoe beter de Individueel is, de hogere waarde van de fitnessfunctie die het krijgt):

while (myPop.getFittest (). getFitness () <getMaxFitness ()) {System.out.println ("Generation:" + generationCount + "Correcte genen gevonden:" + myPop.getFittest (). getFitness ()); myPop = evolvePopulation (myPop); generationCount ++; }

Laten we beginnen met uitleggen hoe we de sterkste worden Individueel:

public int getFitness (individueel individu) {int fitness = 0; for (int i = 0; i <individual.getDefaultGeneLength () && i <solution.length; i ++) {if (individual.getSingleGene (i) == oplossing [i]) {fitness ++; }} fitness teruggeven; }

Zoals we kunnen zien, vergelijken we er twee Individueel objecten beetje bij beetje. Als we geen perfecte oplossing kunnen vinden, moeten we doorgaan naar de volgende stap, die een evolutie is van de Bevolking.

3.3. Nakomelingen

In deze stap moeten we een nieuw Bevolking. Ten eerste moeten we Selecteer twee ouders Individueel objecten van een Bevolking, volgens hun geschiktheid. Houd er rekening mee dat het gunstig is om het beste toe te laten Individueel van de huidige generatie om over te dragen naar de volgende, ongewijzigd. Deze strategie wordt een Elitarisme:

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

Om de twee beste te selecteren Individueel objecten gaan we toepassen toernooiselectiestrategie:

privé Individueel toernooiSelectie (populatie populatie) {Populatie toernooi = nieuwe populatie (toernooi grootte, false); voor (int i = 0; i <toernooiSize; i ++) {int randomId = (int) (Math.random () * pop.getIndividuals (). size ()); toernooi.getIndividuals (). add (i, pop.getIndividual (randomId)); } Individuele fitheid = toernooi.getFittest (); terug fitste; }

De winnaar van elk toernooi (degene met de beste conditie) wordt geselecteerd voor de volgende fase, namelijk Crossover:

privé Individuele crossover (Individual indiv1, Individual indiv2) {Individual newSol = new Individual (); voor (int i = 0; i <newSol.getDefaultGeneLength (); i ++) {if (Math.random () <= uniformRate) {newSol.setSingleGene (i, indiv1.getSingleGene (i)); } anders {newSol.setSingleGene (i, indiv2.getSingleGene (i)); }} retourneer newSol; }

In de crossover wisselen we bits van elk gekozen Individueel op een willekeurig gekozen plek. Het hele proces verloopt in de volgende lus:

for (int i = elitismOffset; i <pop.getIndividuals (). size (); i ++) {Individual indiv1 = toernooiSelectie (pop); Individueel indiv2 = toernooiSelectie (pop); Individuele newIndiv = crossover (indiv1, indiv2); newPopulation.getIndividuals (). add (i, newIndiv); }

Zoals we kunnen zien, plaatsen we na de cross-over nieuwe nakomelingen in een nieuwe Bevolking. Deze stap wordt de Aanvaarding.

Ten slotte kunnen we een Mutatie. Mutatie wordt gebruikt om genetische diversiteit te behouden van één generatie van a Bevolking naar de volgende. We gebruikten de bit inversie type mutatie, waarbij willekeurige bits eenvoudig worden omgekeerd:

private void mutate (Individual indiv) {for (int i = 0; i <indiv.getDefaultGeneLength (); i ++) {if (Math.random () <= mutationRate) {byte gen = (byte) Math.round (Math. willekeurig()); indiv.setSingleGene (i, gen); }}}

Alle soorten Mutaties en Crossover worden mooi beschreven in deze tutorial.

We herhalen vervolgens de stappen uit de paragrafen 3.2 en 3.3, totdat we een beëindigingsvoorwaarde hebben bereikt, bijvoorbeeld de beste oplossing.

4. Tips en trucs

Om zo te een efficiënt genetisch algoritme implementeren, we moeten een set parameters afstemmen. Deze sectie zou u enkele basisaanbevelingen moeten geven om te beginnen met de meest importerende parameters:

• Crossover-snelheid - het zou hoog moeten zijn, ongeveer 80%-95%
• Mutatiesnelheid - het zou erg laag moeten zijn, rond 0.5%-1%.
• Grootte van de bevolking - goede populatieomvang is ongeveer 20-30voor sommige problemen zijn de maten 50-100 echter beter
• Selectie - eenvoudig roulette wiel selectie kan worden gebruikt met het concept van elitarisme
• Crossover en mutatietype - het hangt af van de codering en het probleem

Houd er rekening mee dat aanbevelingen voor afstemming vaak het resultaat zijn van empirisch onderzoek naar genetische algoritmen, en dat ze kunnen variëren op basis van de voorgestelde problemen.

5. Conclusie

Deze tutorial introduceert grondbeginselen van genetische algoritmen. U kunt leren over genetische algoritmen zonder enige voorkennis van dit gebied, met alleen basisvaardigheden voor computerprogrammering.

De volledige broncode voor de codefragmenten in deze zelfstudie is beschikbaar in het GitHub-project.

Houd er ook rekening mee dat we Lombok gebruiken om getters en setters te genereren. In dit artikel kunt u controleren hoe u het correct configureert in uw IDE.

Bekijk alle artikelen van onze serie voor meer voorbeelden van genetische algoritmen:

• Hoe ontwerp je een genetisch algoritme? (deze)
• Het handelsreizigersprobleem in Java