Hangya telep optimalizálása Java példával

1. Bemutatkozás

Ennek a sorozatnak az a célja, hogy magyarázza el a genetikai algoritmusok gondolatát és mutassa meg a legismertebb megvalósításokat.

Ebben az oktatóanyagban megtesszük ismertesse a hangya telep optimalizálásának koncepcióját (ACO), majd a kódpélda.

2. Hogyan működik az ACO

Az ACO egy genetikai algoritmus, amelyet a hangya természetes viselkedése inspirált. Az ACO algoritmus teljes megértéséhez meg kell ismerkednünk az alapfogalmaival:

  • a hangyák feromonok segítségével találják meg a legrövidebb utat az otthon és az élelmiszerforrás között
  • a feromonok gyorsan elpárolognak
  • a hangyák inkább rövidebb utakat használnak sűrűbb feromonnal

Mutassunk egy egyszerű példát az ACO-ról, amelyet az utazó eladó problémájában használtak. A következő esetben meg kell találnunk a legrövidebb utat a grafikon összes csomópontja között:

A hangyák természetes viselkedést követve új utakat kezdenek felfedezni a feltárás során. Az erősebb kék szín jelzi azokat az utakat, amelyeket gyakrabban használnak, mint a többi, míg a zöld szín az aktuális legrövidebb utat jelzi:

Ennek eredményeként elérjük a legrövidebb utat az összes csomópont között:

Az ACO tesztelésének szép GUI alapú eszköze itt található.

3. Java implementáció

3.1. ACO paraméterek

Beszéljük meg az ACO algoritmus fő paramétereit, amelyeket a AntColonyOptimization osztály:

magán kettős c = 1,0; magán kettős alfa = 1; privát kettős béta = 5; magán kettős bepárlás = 0,5; magán kettős Q = 500; magán kettős antFaktor = 0,8; privát kettős randomFactor = 0,01;

Paraméter c a pálya eredeti számát jelzi a szimuláció kezdetén. Továbbá, alfa ellenőrzi a feromon fontosságát, míg béta vezérli a távolság prioritását. Általában a béta paraméternek nagyobbnak kell lennie, mint alfa a legjobb eredmény elérése érdekében.

Ezután a párolgás változó azt mutatja, hogy a feromon hányszor párolog el minden iterációban, míg Q információt nyújt az egyes nyomvonalon maradt feromon teljes mennyiségéről Hangya, és antFactor megmondja, hány hangyát fogunk használni városonként.

Végül egy kis véletlenszerűségre van szükségünk a szimulációink során, és ezt lefedjük randomFactor.

3.2. Hozz létre hangyákat

Minden egyes Hangya képes lesz meglátogatni egy adott várost, emlékezni az összes meglátogatott városra, és nyomon követni az ösvény hosszát:

public void visitCity (int currentIndex, int város) {nyom [currentIndex + 1] = város; meglátogatott [város] = igaz; } nyilvános logikai látogatás (int i) {visszatérés meglátogatott [i]; } public double trailLength (double graph [] []) {double length = graph [nyom [nyomvonalméret - 1]] [nyomvonal [0]]; for (int i = 0; i <trailSize - 1; i ++) {hossz + = grafikon [nyom [i]] [nyom [i + 1]]; } visszatérési hossz; } 

3.3. Állítsa be a hangyákat

A legelején meg kell inicializálja az ACO kód megvalósítását nyomvonalak és hangyamátrixok biztosításával:

gráf = generálRandomMátrix (noOfCities); numberOfCities = gráf.hossz; numberOfAnts = (int) (numberOfCities * antFactor); nyomvonalak = új kettős [numberOfCities] [numberOfCities]; valószínűségek = új kettős [numberOfCities]; hangyák = új Hangya [numberOfAnts]; IntStream.range (0, numberOfAnts) .forEach (i -> hangyák.add (új Hangya (numberOfCities)));

Ezután meg kell állítsa be a hangyák mátrix véletlenszerű várossal kezdeni:

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

A hurok minden iterációjához a következő műveleteket hajtjuk végre:

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

3.4. Mozgassa a hangyákat

Kezdjük a moveAnts () módszer. Meg kell válassza ki a következő várost az összes hangyának, emlékezve arra, hogy minden hangya megpróbálja követni a többi hangya nyomát:

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

A legfontosabb az, hogy megfelelően kiválasztjuk a következő várost. A következő várost a valószínűség logikája alapján kell kiválasztanunk. Először ellenőrizhetjük, hogy Hangya meg kell látogatnia egy véletlenszerű várost:

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

Ha nem választottunk ki véletlenszerű várost, akkor ki kell számolnunk a következő város kiválasztásához szükséges valószínűségeket, és ne feledjük, hogy a hangyák inkább erősebb és rövidebb utakat követnek. Ezt úgy tehetjük meg, hogy a tömbben tároljuk az egyes városokba való költözés valószínűségét:

public void calcProbability (Ant ant) ​​{int i = ant.trail [currentIndex]; kettős feromon = 0,0; for (int l = 0; l <numberOfCities; l ++) {if (! ant.visited (l)) {feromon + = Math.pow (nyomvonalak [i] [l], alfa) * Math.pow (1.0 / grafikon [i] [l], béta); }} for (int j = 0; j <numberOfCities; j ++) {if (ant.visited (j)) {valószínűségek [j] = 0.0; } else {kettős számláló = Math.pow (nyomvonalak [i] [j], alfa) * Math.pow (1,0 / grafikon [i] [j], béta); valószínűségek [j] = számláló / feromon; }}} 

Miután kiszámítottuk a valószínűségeket, az alábbiak segítségével dönthetünk arról, melyik városba megyünk:

dupla r = random.nextDouble (); dupla összeg = 0; for (int i = 0; i = r) {visszatér i; }}

3.5. Frissítse a nyomvonalakat

Ebben a lépésben frissítenünk kell a pályákat és a bal feromont:

public void updateTrails () {for (int i = 0; i <numberOfCities; i ++) {for (int j = 0; j <numberOfCities; j ++) {nyomvonalak [i] [j] * = párolgás; }} (Ant a: hangyák) {kettős hozzájárulás = Q / a.trailLength (grafikon); for (int i = 0; i <numberOfCities - 1; i ++) {nyomvonalak [a.trail [i]] [a.trail [i + 1]] + = hozzájárulás; } nyomvonalak [a.trail [numberOfCities - 1]] [a.trail [0]] + = hozzájárulás; }}

3.6. Frissítse a legjobb megoldást

Ez az egyes iterációk utolsó lépése. Frissítenünk kell a legjobb megoldást, hogy megőrizzük a hivatkozást:

private void updateBest () {if (bestTourOrder == null) {bestTourOrder = hangyák [0] .trail; bestTourLength = hangyák [0] .trailLength (grafikon); } for (Ant a: hangyák) {if (a.trailLength (gráf) <bestTourLength) {bestTourLength = a.trailLength (gráf); bestTourOrder = a.trail.clone (); }}}

Az összes iteráció után a végeredmény jelzi az ACO által megtalált legjobb utat. Felhívjuk figyelmét, hogy a városok számának növelésével csökken a legrövidebb út megtalálásának valószínűsége.

4. Következtetés

Ez az oktatóanyag bemutatja a Hangya-telep optimalizálás algoritmust. Megismerheti a genetikai algoritmusokat minden előzetes tudás nélkül csak alapvető számítógépes programozási ismeretekkel rendelkezik.

Az oktatóanyag kódrészleteinek teljes forráskódja a GitHub projektben érhető el.

Nézze meg a következő linkeket a sorozat összes cikkéhez, beleértve a genetikai algoritmusok egyéb példáit is:

  • Hogyan lehet genetikai algoritmust megtervezni a Java-ban
  • Az utazó eladó problémája a Java-ban
  • Hangya telep optimalizálása (ez)

$config[zx-auto] not found$config[zx-overlay] not found