streamalism.org

1. Uvod

Cilj ove serije je da objasniti ideju genetskih algoritama i prikazati najpoznatije implementacije.

U ovom uputstvu ćemo opisati koncept optimizacije kolonije mrava (ACO), nakon čega slijedi primjer koda.

2. Kako ACO djeluje

ACO je genetski algoritam nadahnut prirodnim ponašanjem mrava. Da bismo u potpunosti razumjeli ACO algoritam, moramo se upoznati s njegovim osnovnim konceptima:

• mravi koriste feromone kako bi pronašli najkraći put između kuće i izvora hrane
• feromoni brzo isparavaju
• mravi radije koriste kraće putove s gušćim feromonom

Pokažimo jednostavan primjer ACO-a koji se koristi u problemu putujućeg trgovca. U sljedećem slučaju trebamo pronaći najkraći put između svih čvorova na grafikonu:

Prateći prirodno ponašanje, mravi će tijekom istraživanja početi istraživati ​​nove putove. Jača plava boja označava staze koje se koriste češće od ostalih, dok zelena boja označava trenutni najkraći put koji je pronađen:

Kao rezultat, postići ćemo najkraći put između svih čvorova:

Lijep alat zasnovan na GUI-u za ACO testiranje možete pronaći ovdje.

3. Implementacija Jave

3.1. ACO parametri

Razmotrimo glavne parametre za ACO algoritam, deklarirane u AntColonyOptimization razred:

privatni dvostruki c = 1,0; privatni dvostruki alfa = 1; privatna dvostruka beta = 5; privatno dvostruko isparavanje = 0,5; privatni dvostruki Q = 500; privatni dvostruki faktor mrava = 0,8; privatni dvostruki randomFactor = 0,01;

Parametar c označava izvorni broj staza na početku simulacije. Nadalje, alfa kontrolira važnost feromona, dok beta kontrolira prioritet udaljenosti. Općenito, beta parametar trebao biti veći od alfa za najbolje rezultate.

Dalje, isparavanje varijabla pokazuje postotak koliko feromon isparava u svakoj iteraciji, dok P pruža informacije o ukupnoj količini feromona koju je svaki ostavio na tragu Mrav, i antFactor govori nam koliko ćemo mrava koristiti po gradu.

Napokon, moramo imati malo slučajnosti u našim simulacijama, a to pokriva randomFactor.

3.2. Stvorite mrave

Svaki Mrav moći će posjetiti određeni grad, sjetiti se svih posjećenih gradova i pratiti dužinu staze:

public void visitCity (int currentIndex, int city) {trail [currentIndex + 1] = city; posjećen [grad] = istina; } javna logička posjeta (int i) {povratak posjećen [i]; } javni dvostruki trailLength (dvostruki graf [] []) {dvostruka duljina = graf [trail [trailSize - 1]] [trail [0]]; for (int i = 0; i <trailSize - 1; i ++) {length + = graph [trail [i]] [trail [i + 1]]; } dužina vraćanja; } 

3.3. Postavljanje mrava

Na samom početku moramo inicijalizirajte našu implementaciju ACO koda pružanjem matrica staza i mrava:

graf = generirajRandomMatrix (noOfCities); numberOfCities = graph.length; numberOfAnts = (int) (numberOfCities * antFactor); staze = novi dvostruki [numberOfCities] [numberOfCities]; vjerojatnosti = novi dvostruki [numberOfCities]; mravi = novi Ant [numberOfAnts]; IntStream.range (0, numberOfAnts) .forEach (i -> mravi.add (novi Ant (numberOfCities)));

Dalje, trebamo postavi mravi matrica za početak sa slučajnim gradom:

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

Za svaku iteraciju petlje izvest ćemo sljedeće operacije:

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

3.4. Premjesti mrave

Počnimo s moveAnts () metoda. Moramo odaberite sljedeći grad za sve mrave, sjećajući se da svaki mrav pokušava slijediti tragove drugih mrava:

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

Najvažnije je pravilno odabrati sljedeći grad koji želite posjetiti. Sljedeći bismo grad trebali odabrati na temelju logike vjerojatnosti. Prvo, možemo provjeriti je li Mrav trebali posjetiti slučajni grad:

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

Ako nismo odabrali nijedan slučajni grad, moramo izračunati vjerojatnosti za odabir sljedećeg grada, sjećajući se da mravi radije slijede jače i kraće staze. To možemo učiniti spremanjem vjerojatnosti preseljenja u svaki grad u nizu:

javna praznina izračunaj vjerojatnosti (Ant ant) ​​{int i = ant.trail [currentIndex]; dvostruki feromon = 0,0; for (int l = 0; l <numberOfCities; l ++) {if (! ant.visited (l)) {pheromone + = Math.pow (staze [i] [l], alfa) * Math.pow (1.0 / graf [i] [l], beta); }} za (int j = 0; j <numberOfCities; j ++) {if (ant.visited (j)) {vjerojatnosti [j] = 0,0; } else {dvostruki brojnik = Math.pow (staze [i] [j], alfa) * Math.pow (1,0 / graf [i] [j], beta); vjerojatnosti [j] = brojnik / feromon; }}} 

Nakon što izračunamo vjerojatnosti, možemo odlučiti u koji grad ćemo ići pomoću:

dvostruko r = random.nextDouble (); dvostruko ukupno = 0; for (int i = 0; i = r) {return i; }}

3.5. Ažuriranje staza

U ovom koraku trebali bismo ažurirati staze i lijevi feromon:

public void updateTrails () {for (int i = 0; i <numberOfCities; i ++) {for (int j = 0; j <numberOfCities; j ++) {trails [i] [j] * = evaporacija; }} za (Ant a: mravi) {dvostruki doprinos = Q / a.trailLength (graf); for (int i = 0; i <numberOfCities - 1; i ++) {trails [a.trail [i]] [a.trail [i + 1]] + = doprinos; } staze [a.trail [numberOfCities - 1]] [a.trail [0]] + = doprinos; }}

3.6. Ažurirajte najbolje rješenje

Ovo je zadnji korak svake iteracije. Moramo ažurirati najbolje rješenje kako bismo zadržali referencu na njega:

private void updateBest () {if (bestTourOrder == null) {bestTourOrder = mravi [0] .trail; bestTourLength = mravi [0] .trailLength (graf); } za (Ant a: mravi) {if (a.trailLength (graf) <bestTourLength) {bestTourLength = a.trailLength (graf); bestTourOrder = a.trail.clone (); }}}

Nakon svih ponavljanja, konačni rezultat ukazat će na najbolji put koji je pronašao ACO. Napominjemo da se povećanjem broja gradova smanjuje vjerojatnost pronalaska najkraćeg puta.

4. Zaključak

Ovaj vodič uvodi algoritam optimizacije kolonije mrava. Možete naučiti o genetskim algoritmima bez ikakvih predznanja ovog područja, imajući samo osnovne vještine računalnog programiranja.

Kompletni izvorni kod za isječke koda u ovom vodiču dostupan je u projektu GitHub.

Za sve članke u seriji, uključujući ostale primjere genetskih algoritama, pogledajte sljedeće poveznice:

• Kako dizajnirati genetski algoritam u Javi
• Problem putujućeg trgovca na Javi
• Optimizacija kolonije mrava (ovo)