streamalism.org

1. Úvod

Cieľom tejto série je: vysvetliť myšlienku genetických algoritmov a ukázať najznámejšie implementácie.

V tomto výučbe to urobíme popísať koncept optimalizácie kolónie mravcov (ACO), za ktorým nasleduje príklad kódu.

2. Ako funguje ACO

ACO je genetický algoritmus inšpirovaný prirodzeným správaním mravca. Aby sme plne porozumeli algoritmu ACO, musíme sa oboznámiť s jeho základnými pojmami:

• mravce používajú feromóny na nájdenie najkratšej cesty medzi domovom a zdrojom potravy
• feromóny sa rýchlo odparujú
• mravce uprednostňujú použitie kratších ciest s hustejším feromónom

Ukážme si jednoduchý príklad ACO použitých v Probléme obchodného cestujúceho. V nasledujúcom prípade musíme nájsť najkratšiu cestu medzi všetkými uzlami v grafe:

Po prirodzenom správaní začnú mravce počas prieskumu objavovať nové cesty. Silnejšia modrá farba označuje cesty, ktoré sa používajú častejšie ako ostatné, zatiaľ čo zelená farba označuje aktuálnu najkratšiu cestu, ktorá sa nachádza:

Vo výsledku dosiahneme najkratšiu cestu medzi všetkými uzlami:

Príjemný nástroj na testovanie ACO založený na grafickom používateľskom rozhraní nájdete tu.

3. Implementácia Java

3.1. Parametre ACO

Poďme diskutovať o hlavných parametroch pre algoritmus ACO deklarovaných v AntColonyOptimization trieda:

súkromné ​​dvojité c = 1,0; súkromné ​​dvojité alfa = 1; súkromná dvojitá beta = 5; súkromné ​​dvojité odparovanie = 0,5; súkromné ​​dvojité Q = 500; súkromný dvojitý antFaktor = 0,8; private double randomFactor = 0,01;

Parameter c označuje pôvodný počet trás na začiatku simulácie. Ďalej alfa kontroluje dôležitosť feromónov, zatiaľ čo beta riadi prioritu vzdialenosti. Všeobecne platí, že beta parameter by mal byť väčší ako alfa pre dosiahnutie najlepších výsledkov.

Ďalej odparovanie Premenná ukazuje percento, koľko sa feromón odparuje pri každej iterácii, zatiaľ čo Q poskytuje informácie o celkovom množstve feromónu, ktoré každý zostal na stope Anta antFaktor nám hovorí, koľko mravcov použijeme na mesto.

Nakoniec musíme mať v našich simuláciách trochu náhodnosti, a tým sa zaoberáme randomFactor.

3.2. Vytvorte mravce

Každý Ant bude môcť navštíviť konkrétne mesto, zapamätať si všetky navštívené mestá a sledovať dĺžku trasy:

public void visitCity (int currentIndex, int city) {trail [currentIndex + 1] = mesto; navštívené [mesto] = pravda; } public boolean navštívil (int i) {návrat navštívil [i]; } public double trailLength (double graph [] []) {double length = graph [trail [trailSize - 1]] [trail [0]]; for (int i = 0; i <trailSize - 1; i ++) {length + = graph [trail [i]] [trail [i + 1]]; } dĺžka návratu; } 

3.3. Nastaviť mravce

Hneď na začiatku musíme inicializovať implementáciu nášho kódu ACO poskytnutím tabuliek chodníkov a mravcov:

graph = generateRandomMatrix (noOfCities); numberOfCities = graph.length; numberOfAnts = (int) (numberOfCities * antFactor); chodníky = nová dvojitá [numberOfCities] [numberOfCities]; pravdepodobnosti = nová dvojka [numberOfCities]; mravce = nový mravec [numberOfAnts]; IntStream.range (0, numberOfAnts) .forEach (i -> ants.add (nový mravec (numberOfCities)));

Ďalej musíme nastaviť mravce matrica začať s náhodným mestom:

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

Pre každú iteráciu slučky vykonáme nasledujúce operácie:

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

3.4. Presuňte mravce

Začnime s moveAnts () metóda. Musíme vyberte ďalšie mesto pre všetkých mravcov, pamätajúc na to, že každý mravec sa snaží ísť po stopách iných mravcov:

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

Najdôležitejšou časťou je správny výber ďalšieho mesta, ktoré chcete navštíviť. Mali by sme zvoliť ďalšie mesto na základe pravdepodobnostnej logiky. Najskôr môžeme skontrolovať, či Ant by mal navštíviť náhodné mesto:

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

Ak sme nevybrali žiadne náhodné mesto, musíme vypočítať pravdepodobnosť výberu ďalšieho mesta, nezabúdajme, že mravce radšej idú po silnejších a kratších chodníkoch. Môžeme to urobiť uložením pravdepodobnosti presunu do každého mesta v poli:

public void spočítaťProbability (Ant ant) ​​{int i = ant.trail [currentIndex]; dvojitý feromón = 0,0; pre (int l = 0; l <numberOfCities; l ++) {if (! ant.visited (l)) {feromón + = Math.pow (chodníky [i] [l], alfa) * Math.pow (1,0 / graf [i] [l], beta); }} pre (int j = 0; j <numberOfCities; j ++) {if (ant.visited (j)) {pravdepodobnosti [j] = 0,0; } else {dvojitý čitateľ = Math.pow (chodníky [i] [j], alfa) * Math.pow (1,0 / graf [i] [j], beta); pravdepodobnosti [j] = čitateľ / feromón; }}} 

Po výpočte pravdepodobností sa môžeme rozhodnúť, do ktorého mesta pôjdeme, pomocou:

double r = random.nextDouble (); dvojitý súčet = 0; for (int i = 0; i = r) {return i; }}

3.5. Aktualizujte trasy

V tomto kroku by sme mali aktualizovať chodníky a ľavý feromón:

public void updateTrails () {for (int i = 0; i <numberOfCities; i ++) {for (int j = 0; j <numberOfCities; j ++) {trails [i] [j] * = odparovanie; }} pre (Ant a: mravce) {dvojitý príspevok = Q / a.trailLength (graf); for (int i = 0; i <numberOfCities - 1; i ++) {trails [a.trail [i]] [a.trail [i + 1]] + = príspevok; } chodníky [a.trail [numberOfCities - 1]] [a.trail [0]] + = príspevok; }}

3.6. Aktualizujte najlepšie riešenie

Toto je posledný krok každej iterácie. Aby sme udržali odkaz na toto riešenie, musíme aktualizovať najlepšie riešenie:

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

Po všetkých iteráciách bude konečný výsledok označovať najlepšiu cestu, ktorú ACO našlo. Upozorňujeme, že so zvyšujúcim sa počtom miest klesá pravdepodobnosť nájdenia najkratšej cesty.

4. Záver

Tento návod predstavuje algoritmus Ant Colony Optimization. Môžete sa dozvedieť viac o genetických algoritmoch bez akýchkoľvek predchádzajúcich vedomostí tejto oblasti, majúc iba základné znalosti programovania v počítači.

Kompletný zdrojový kód úryvkov kódu v tomto tutoriále je k dispozícii v projekte GitHub.

Všetky články v sérii vrátane ďalších príkladov genetických algoritmov nájdete na nasledujúcich odkazoch:

• Ako navrhnúť genetický algoritmus v Jave
• Problém cestovného predajcu v Jave
• Optimalizácia kolónie mravcov (toto)