streamalism.org

1. Introduktion

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

I denne vejledning vil vi beskrive begrebet optimering af myrkoloni (ACO) efterfulgt af kodeeksemplet.

2. Sådan fungerer ACO

ACO er en genetisk algoritme inspireret af en myres naturlige opførsel. For at forstå ACO-algoritmen fuldt ud er vi nødt til at blive fortrolig med dens grundlæggende begreber:

• myrer bruger feromoner til at finde den korteste vej mellem hjemmet og fødekilden
• feromoner fordamper hurtigt
• myrer foretrækker at bruge kortere stier med tættere feromon

Lad os vise et simpelt eksempel på ACO, der blev brugt i det rejsende sælgerproblem. I det følgende tilfælde skal vi finde den korteste sti mellem alle noder i grafen:

Efter naturlig adfærd begynder myrer at udforske nye stier under udforskningen. Stærkere blå farve angiver de stier, der bruges oftere end de andre, mens grøn farve angiver den nuværende korteste sti, der findes:

Som et resultat opnår vi den korteste vej mellem alle noder:

Det gode GUI-baserede værktøj til ACO-test kan findes her.

3. Java-implementering

3.1. ACO-parametre

Lad os diskutere de vigtigste parametre for ACO-algoritmen, erklæret i AntColonyOptimization klasse:

privat dobbelt c = 1.0; privat dobbelt alfa = 1; privat dobbelt beta = 5; privat dobbelt fordampning = 0,5; privat dobbelt Q = 500; privat dobbelt antFaktor = 0,8; privat dobbelt tilfældig faktor = 0,01;

Parameter c angiver det oprindelige antal stier i starten af ​​simuleringen. Desuden, alfa styrer feromons betydning, mens beta styrer afstandsprioriteten. Generelt er det beta parameter skal være større end alfa for de bedste resultater.

Dernæst fordampning variabel viser procentdelen, hvor meget feromonet fordamper i hver iteration, hvorimod Q giver information om den samlede mængde feromon, der er tilbage på stien af ​​hver Myreog antFaktor fortæller os, hvor mange myrer vi vil bruge pr. by.

Endelig skal vi have lidt tilfældighed i vores simuleringer, og dette er dækket af tilfældig faktor.

3.2. Opret myrer

Hver Myre vil være i stand til at besøge en bestemt by, huske alle besøgte byer og holde styr på sporets længde:

public void visitCity (int currentIndex, int city) {trail [currentIndex + 1] = by; besøgt [by] = sand; } offentlig boolsk besøgte (int i) {retur besøgte [i]; } offentlig dobbelt trailLength (dobbelt graf [] []) {dobbelt længde = graf [trail [trailSize - 1]] [trail [0]]; for (int i = 0; i <trailSize - 1; i ++) {længde + = graf [spor [i]] [spor [i + 1]]; } returlængde; } 

3.3. Opsæt myrer

I starten er vi nødt til det initialisere vores implementering af ACO-kode ved at give stier og myrer matricer:

graf = createRandomMatrix (noOfCities); numberOfCities = graph.length; numberOfAnts = (int) (numberOfCities * antFactor); stier = ny dobbelt [numberOfCities] [numberOfCities]; sandsynligheder = ny dobbelt [numberOfCities]; myrer = ny Ant [numberOfAnts]; IntStream.range (0, numberOfAnts) .forEach (i -> ants.add (new Ant (numberOfCities)));

Derefter skal vi opsæt myrer matrix at starte med en tilfældig by:

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

For hver iteration af sløjfen udfører vi følgende operationer:

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

3.4. Flyt myrer

Lad os starte med moveAnts () metode. Vi er nødt til vælg den næste by for alle myrer, husker at hver myre prøver at følge andre myres spor:

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

Den vigtigste del er at vælge den næste by, du vil besøge korrekt. Vi skal vælge den næste by baseret på sandsynlighedslogikken. Først kan vi kontrollere, om Myre skal besøge en tilfældig by:

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

Hvis vi ikke valgte nogen tilfældig by, er vi nødt til at beregne sandsynligheder for at vælge den næste by og huske at myrer foretrækker at følge stærkere og kortere stier. Vi kan gøre dette ved at gemme sandsynligheden for at flytte til hver by i arrayet:

offentlig ugyldighed calcProbabilities (Ant ant) ​​{int i = ant.trail [currentIndex]; dobbeltferomon = 0,0; for (int l = 0; l <numberOfCities; l ++) {if (! ant.visited (l)) {feromon + = Math.pow (stier [i] [l], alpha) * Math.pow (1.0 / graf [i] [l], beta); }} for (int j = 0; j <numberOfCities; j ++) {if (ant.visited (j)) {sandsynligheder [j] = 0,0; } andet {dobbelt tæller = Math.pow (stier [i] [j], alpha) * Math.pow (1.0 / graf [i] [j], beta); sandsynligheder [j] = tæller / feromon; }}} 

Når vi har beregnet sandsynligheder, kan vi beslutte, hvilken by vi skal gå til ved hjælp af:

dobbelt r = random.nextDouble (); dobbelt total = 0; for (int i = 0; i = r) {return i; }}

3.5. Opdater stier

I dette trin skal vi opdatere stier og venstre feromon:

offentlige ugyldige updateTrails () {for (int i = 0; i <numberOfCities; i ++) {for (int j = 0; j <numberOfCities; j ++) {stier [i] [j] * = fordampning; }} for (Ant a: myrer) {dobbelt bidrag = Q / a.trailLength (graf); for (int i = 0; i <numberOfCities - 1; i ++) {stier [a.trail [i]] [a.trail [i + 1]] + = bidrag; } stier [a.trail [numberOfCities - 1]] [a.trail [0]] + = bidrag; }}

3.6. Opdater den bedste løsning

Dette er det sidste trin i hver iteration. Vi er nødt til at opdatere den bedste løsning for at holde henvisningen til den:

privat ugyldig opdateringBest () {if (bestTourOrder == null) {bestTourOrder = myrer [0] .trail; bestTourLength = myrer [0] .traLength (graf); } for (Ant a: myrer) {if (a.trailLength (graf) <bestTourLength) {bestTourLength = a.trailLength (graf); bestTourOrder = a.trail.clone (); }}}

Efter alle iterationer vil det endelige resultat indikere den bedste vej fundet af ACO. Bemærk, at ved at øge antallet af byer falder sandsynligheden for at finde den korteste vej.

4. Konklusion

Denne vejledning introducerer Ant Colony Optimization algoritmen. Du kan lære om genetiske algoritmer uden nogen tidligere viden af dette område, der kun har grundlæggende computerprogrammeringsfærdigheder.

Den komplette kildekode til kodestykkerne i denne vejledning er tilgængelig i GitHub-projektet.

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 (dette)