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)