streamalism.org

1. Inleiding

Het doel van deze serie is om leg het idee van genetische algoritmen uit en laat de meest bekende implementaties zien.

In deze tutorial zullen we beschrijven het concept van de optimalisatie van de mierenkolonie (ACO), gevolgd door het codevoorbeeld.

2. Hoe ACO werkt

ACO is een genetisch algoritme dat is geïnspireerd op het natuurlijke gedrag van een mier. Om het ACO-algoritme volledig te begrijpen, moeten we vertrouwd raken met de basisconcepten:

• mieren gebruiken feromonen om de kortste weg tussen huis en voedselbron te vinden
• feromonen verdampen snel
• mieren geven er de voorkeur aan om kortere paden te gebruiken met een dichter feromoon

Laten we een eenvoudig voorbeeld van ACO laten zien dat wordt gebruikt in het handelsreizigersprobleem. In het volgende geval moeten we het kortste pad tussen alle knooppunten in de grafiek vinden:

Door natuurlijk gedrag te volgen, zullen mieren tijdens de verkenning nieuwe paden gaan verkennen. Een sterkere blauwe kleur geeft de paden aan die vaker worden gebruikt dan de andere, terwijl de groene kleur het huidige kortste pad aangeeft dat wordt gevonden:

Als resultaat bereiken we het kortste pad tussen alle knooppunten:

De mooie GUI-gebaseerde tool voor ACO-testen is hier te vinden.

3. Java-implementatie

3.1. ACO-parameters

Laten we de belangrijkste parameters voor het ACO-algoritme bespreken, gedeclareerd in het AntColony Optimalisatie klasse:

privé dubbel c = 1,0; privé dubbele alpha = 1; private dubbele bèta = 5; privé dubbele verdamping = 0,5; privé dubbele Q = 500; privé dubbele antFactor = 0,8; privé dubbele randomFactor = 0,01;

Parameter c geeft het oorspronkelijke aantal sporen aan, aan het begin van de simulatie. Verder alpha regelt het belang van feromonen, terwijl bèta regelt de afstandsprioriteit. In het algemeen is de bèta parameter moet groter zijn dan alpha voor de beste resultaten.

Vervolgens de verdamping variabele toont het percentage hoeveel het feromoon in elke iteratie verdampt, terwijl Q geeft informatie over de totale hoeveelheid feromoon die door elk op het spoor achterblijft Mier, en antFactor vertelt ons hoeveel mieren we per stad zullen gebruiken.

Ten slotte hebben we een beetje willekeur nodig in onze simulaties, en dit wordt gedekt door randomFactor.

3.2. Maak mieren

Elk Mier zal in staat zijn om een ​​specifieke stad te bezoeken, alle bezochte steden te onthouden en de lengte van het parcours bij te houden:

public void visitCity (int currentIndex, int city) {trail [currentIndex + 1] = stad; bezocht [stad] = waar; } openbare boolean bezocht (int i) {terugkeer bezocht [i]; } openbare dubbele trailLength (dubbele grafiek [] []) {dubbele lengte = grafiek [spoor [trailSize - 1]] [spoor [0]]; voor (int i = 0; i <trailSize - 1; i ++) {lengte + = grafiek [spoor [i]] [spoor [i + 1]]; } retour lengte; } 

3.3. Stel mieren in

In het allereerste begin moeten we dat doen initialiseer onze ACO-code-implementatie door middel van paden en mierenmatrices:

graph = genererenRandomMatrix (noOfCities); numberOfCities = graph.length; numberOfAnts = (int) (numberOfCities * antFactor); trails = nieuwe dubbele [numberOfCities] [numberOfCities]; kansen = nieuwe dubbele [numberOfCities]; ants = nieuwe Ant [numberOfAnts]; IntStream.range (0, numberOfAnts) .forEach (i -> ants.add (nieuwe Ant (numberOfCities)));

Vervolgens moeten we stel het mieren Matrix om te beginnen met een willekeurige stad:

openbare void setupAnts () {IntStream.range (0, numberOfAnts) .forEach (i -> {ants.forEach (ant -> {ant.clear (); ant.visitCity (-1, random.nextInt (numberOfCities)); });}); currentIndex = 0; }

Voor elke iteratie van de lus voeren we de volgende bewerkingen uit:

IntStream.range (0, maxIteraties) .forEach (i -> {moveAnts (); updateTrails (); updateBest ();});

3.4. Verplaats mieren

Laten we beginnen met de moveAnts () methode. We moeten kies de volgende stad voor alle mieren, onthouden dat elke mier de sporen van andere mieren probeert te volgen:

public void moveAnts () {IntStream.range (currentIndex, numberOfCities - 1) .forEach (i -> {ants.forEach (ant -> {ant.visitCity (currentIndex, selectNextCity (ant));}); currentIndex ++;}) ; }

Het belangrijkste is om op de juiste manier de volgende stad te selecteren om te bezoeken. We moeten de volgende stad selecteren op basis van de waarschijnlijkheidslogica. Ten eerste kunnen we controleren of Mier zou een willekeurige stad moeten bezoeken:

int t = random.nextInt (numberOfCities - currentIndex); if (random.nextDouble () i == t &&! ant.visited (i)) .findFirst (); if (cityIndex.isPresent ()) {return cityIndex.getAsInt (); }}

Als we geen willekeurige stad hebben geselecteerd, moeten we de kansen berekenen om de volgende stad te selecteren, waarbij we onthouden dat mieren er de voorkeur aan geven sterkere en kortere paden te volgen. We kunnen dit doen door de kans om naar elke stad te verhuizen in de array op te slaan:

openbare ongeldige berekenProbabilities (Ant ant) ​​{int i = ant.trail [currentIndex]; dubbel feromoon = 0,0; for (int l = 0; l <numberOfCities; l ++) {if (! ant.visited (l)) {feromoon + = Math.pow (trails [i] [l], alpha) * Math.pow (1.0 / grafiek [i] [l], bèta); }} for (int j = 0; j <numberOfCities; j ++) {if (ant.visited (j)) {kansen [j] = 0,0; } else {dubbele teller = Math.pow (sporen [i] [j], alfa) * Math.pow (1.0 / grafiek [i] [j], bèta); waarschijnlijkheden [j] = teller / feromoon; }}} 

Nadat we de kansen hebben berekend, kunnen we beslissen naar welke stad we gaan door gebruik te maken van:

dubbele r = random.nextDouble (); dubbel totaal = 0; for (int i = 0; i = r) {return i; }}

3.5. Werk routes bij

In deze stap moeten we trails en het linker feromoon bijwerken:

public void updateTrails () {for (int i = 0; i <numberOfCities; i ++) {for (int j = 0; j <numberOfCities; j ++) {trails [i] [j] * = verdamping; }} for (Ant a: ants) {dubbele bijdrage = Q / a.trailLength (grafiek); for (int i = 0; i <numberOfCities - 1; i ++) {trails [a.trail [i]] [a.trail [i + 1]] + = bijdrage; } trails [a.trail [numberOfCities - 1]] [a.trail [0]] + = bijdrage; }}

3.6. Werk de beste oplossing bij

Dit is de laatste stap van elke iteratie. We moeten de beste oplossing bijwerken om de verwijzing ernaar te behouden:

private void updateBest () {if (bestTourOrder == null) {bestTourOrder = ants [0] .trail; bestTourLength = ants [0] .trailLength (grafiek); } for (Ant a: ants) {if (a.trailLength (graph) <bestTourLength) {bestTourLength = a.trailLength (graph); bestTourOrder = a.trail.clone (); }}}

Na alle iteraties geeft het eindresultaat het beste pad aan dat door ACO is gevonden. Houd er rekening mee dat door het aantal steden te vergroten, de kans op het vinden van de kortste weg afneemt.

4. Conclusie

Deze tutorial introduceert het algoritme voor optimalisatie van de mierenkolonie. 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.

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
• Mierenkolonie-optimalisatie (dit)