streamalism.org

1. Introduksjon

Målet med denne serien er å forklare ideen om genetiske algoritmer og vise de mest kjente implementeringene.

I denne opplæringen vil vi beskrive begrepet optimalisering av maurkolonien (ACO), etterfulgt av kodeeksemplet.

2. Hvordan ACO fungerer

ACO er en genetisk algoritme inspirert av en maurs naturlige oppførsel. For å forstå ACO-algoritmen, må vi bli kjent med dens grunnleggende konsepter:

• maur bruker feromoner for å finne den korteste veien mellom hjem og matkilde
• feromoner fordamper raskt
• maur foretrekker å bruke kortere stier med tettere feromon

La oss vise et enkelt eksempel på ACO brukt i den reisende selgerproblemet. I det følgende tilfellet må vi finne den korteste banen mellom alle noder i grafen:

Etter naturlig oppførsel vil maur begynne å utforske nye stier under utforskningen. Sterkere blå farge indikerer banene som brukes oftere enn de andre, mens grønn farge indikerer den nåværende korteste banen som er funnet:

Som et resultat oppnår vi den korteste veien mellom alle noder:

Det fine GUI-baserte verktøyet for ACO-testing finner du her.

3. Java-implementering

3.1. ACO-parametere

La oss diskutere hovedparametrene for ACO-algoritmen, erklært i AntColonyOptimization klasse:

privat dobbel c = 1.0; privat dobbelt alfa = 1; privat dobbel beta = 5; privat dobbel fordampning = 0,5; privat dobbel Q = 500; privat dobbel antFactor = 0,8; privat dobbel randomFactor = 0,01;

Parameter c indikerer det opprinnelige antallet stier, ved starten av simuleringen. Dessuten, alfa kontrollerer feromons betydning, mens beta kontrollerer avstandsprioriteten. Generelt sett beta parameteren skal være større enn alfa for best resultat.

Neste, den fordampning variabel viser prosentvis hvor mye feromonet fordamper i hver iterasjon, mens Spørsmål gir informasjon om den totale mengden feromon som er igjen på stien av hver Maur, og antFactor forteller oss hvor mange maur vi vil bruke per by.

Til slutt må vi ha litt tilfeldighet i simuleringene våre, og dette dekkes av randomFactor.

3.2. Lag maur

Hver Maur vil kunne besøke en bestemt by, huske alle besøkte byer og holde oversikt over løypelengden:

public void visitCity (int currentIndex, int city) {trail [currentIndex + 1] = by; besøkt [by] = sant; } offentlig boolsk besøk (int i) {retur besøkt [i]; } offentlig dobbel trailLength (dobbel graf [] []) {dobbel lengde = graf [trail [trailSize - 1]] [trail [0]]; for (int i = 0; i <trailSize - 1; i ++) {lengde + = graf [sti [i]] [sti [i + 1]]; } returlengde; } 

3.3. Installasjonsmyrer

Helt i begynnelsen må vi initialisere implementeringen av ACO-koden ved å tilby stier og maurmatriser:

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

Deretter må vi sette opp maur matrise å starte med en tilfeldig 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 iterasjon av løkken utfører vi følgende operasjoner:

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

3.4. Flytt maur

La oss starte med moveAnts () metode. Vi må velg neste by for alle maurene, huske at hver maur prøver å følge andre maurs løyper:

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

Den viktigste delen er å velge neste by du skal besøke. Vi bør velge neste by basert på sannsynlighetslogikken. Først kan vi sjekke om Maur bør besøke en tilfeldig 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 noen tilfeldig by, må vi beregne sannsynligheten for å velge neste by, og huske at maur foretrekker å følge sterkere og kortere stier. Vi kan gjøre dette ved å lagre sannsynligheten for å flytte til hver by i matrisen:

offentlig tomrom 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], alfa) * Math.pow (1.0 / graf [i] [l], beta); }} for (int j = 0; j <numberOfCities; j ++) {if (ant.visited (j)) {sannsynligheter [j] = 0.0; } annet {dobbel teller = Math.pow (stier [i] [j], alfa) * Math.pow (1.0 / graf [i] [j], beta); sannsynligheter [j] = teller / feromon; }}} 

Etter at vi har beregnet sannsynligheter, kan vi bestemme hvilken by vi skal gå til ved å bruke:

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

3.5. Oppdater stier

I dette trinnet bør vi oppdatere stier og venstre feromon:

public void updateTrails () {for (int i = 0; i <numberOfCities; i ++) {for (int j = 0; j <numberOfCities; j ++) {stier [i] [j] * = fordampning; }} for (Ant a: ants) {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. Oppdater den beste løsningen

Dette er det siste trinnet i hver iterasjon. Vi må oppdatere den beste løsningen for å beholde referansen til den:

privat tomrom updateBest () {if (bestTourOrder == null) {bestTourOrder = maur [0] .trail; bestTourLength = maur [0] .traLength (graf); } for (Ant a: ants) {if (a.trailLength (graph) <bestTourLength) {bestTourLength = a.trailLength (graph); bestTourOrder = a.trail.clone (); }}}

Etter alle iterasjoner vil det endelige resultatet indikere den beste banen ACO har funnet. Vær oppmerksom på at sannsynligheten for å finne den korteste veien reduseres ved å øke antall byer.

4. Konklusjon

Denne opplæringen introduserer Ant Colony Optimization-algoritmen. Du kan lære om genetiske algoritmer uten forutgående kunnskap av dette området, med bare grunnleggende dataprogrammeringsferdigheter.

Den komplette kildekoden for kodebitene i denne opplæringen er tilgjengelig i GitHub-prosjektet.

For alle artikler i serien, inkludert andre eksempler på genetiske algoritmer, sjekk ut følgende lenker:

• Hvordan lage en genetisk algoritme i Java
• Det reisende selgerproblemet i Java
• Ant Colony Optimization (dette)