streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban megismerhetjük a Szimulált annealing algoritmust, és bemutatjuk a megvalósító példát a Traveling Salesman Problem (TSP) alapján.

2. Szimulált hőkezelés

A szimulált annealing algoritmus heurisztikus a problémák megoldására nagy keresési területtel.

Az ihlet és a név a kohászatban történt megolvasztásból származott; ez egy technika, amely magában foglalja az anyag melegítését és szabályozott hűtését.

Általánosságban elmondható, hogy a szimulált hőkezelés csökkenti a rosszabb megoldások elfogadásának valószínűségét, mivel feltárja a megoldási teret és csökkenti a rendszer hőmérsékletét. Az alábbi animáció bemutatja a legjobb megoldás megtalálásának mechanizmusát a szimulált annealing algoritmus segítségével:

Amint megfigyelhetjük, az algoritmus szélesebb megoldástartományt alkalmaz a rendszer magas hőmérsékletén, a globális optimum keresésére. A hőmérséklet csökkentése közben a keresési tartomány egyre kisebb, amíg meg nem találja a globális optimumot.

Az algoritmusnak néhány paramétere van:

• iterációk száma - a szimulációk leállási feltétele
• kezdeti hőmérséklet - a rendszer induló energiája
• hűtési sebesség paraméter - az a százalék, amellyel csökkentjük a rendszer hőmérsékletét
• minimális hőmérséklet - opcionális megállási feltétel
• szimulációs idő - opcionális megállási feltétel

Ezeknek a paramétereknek az értékeit gondosan kell kiválasztani - mivel ezek jelentősen befolyásolhatják a folyamat teljesítményét.

3. Utazó eladó problémája

A Traveling Salesman Problem (TSP) a legismertebb informatikai optimalizálási probléma a modern világban.

Egyszerű szavakkal, problémát jelent a grafikon csomópontjai közötti optimális útvonal megtalálása. A teljes utazási távolság lehet az egyik optimalizálási kritérium. A TSP-vel kapcsolatos további részletekért tekintse meg itt.

4. Java modell

A TSP probléma megoldásához két modellosztályra lesz szükségünk, nevezetesen Város és Utazás. Az elsőben a csomópontok koordinátáit tároljuk a grafikonon:

@Data nyilvános osztály City {private int x; magán int y; nyilvános város () {this.x = (int) (Math.random () * 500); ez.y = (int) (Math.random () * 500); } nyilvános kettős távolságToCity (városi város) {int x = Math.abs (getX () - város.getX ()); int y = Math.abs (getY () - város.getY ()); return Math.sqrt (Math.pow (x, 2) + Math.pow (y, 2)); }}

A kivitelező Város osztály lehetővé teszi számunkra, hogy véletlenszerű helyeket hozzunk létre a városokban. A distanceToCity (..) a logika felelős a városok közötti távolság kiszámításáért.

A következő kód felelős az utazó eladó túra modellezéséért. Kezdjük a városok kezdeti sorrendjének létrehozásával az utazás során:

public void generatorInitialTravel () {if (travel.isEmpty ()) new Travel (10); Gyűjtemények.sorsolás (utazás); }

A kezdeti sorrend előállítása mellett szükségünk van a véletlenszerű két város utazási sorrendben történő felcserélésére szolgáló módszerekre. Használni fogjuk a jobb megoldások keresésére a Szimulált Égesztés algoritmusban:

public void swapCities () {int a = generálRandomIndex (); int b = generálRandomIndex (); előzőTravel = utazás; X város = travel.get (a); Y város = utazás.get (b); utazás.halmaz (a, y); utazás.készlet (b, x); }

Továbbá szükségünk van egy módszerre az előző lépésben generált csere generálásának visszavonására, ha algoritmusunk nem fogadja el az új megoldást:

public void revertSwap () {utazás = előzőTravel; }

Az utolsó módszer, amelyet meg akarunk tenni, a teljes utazási távolság kiszámítása, amelyet optimalizálási kritériumként használunk:

public int getDistance () {int távolság = 0; for (int index = 0; index <utazás.méret (); index ++) {Város kezdő = getCity (index); Város rendeltetési helye; if (index + 1 <utazás.méret ()) {cél = getCity (index + 1); } else {cél = getCity (0); } távolság + = kezdő.távolságToCity (cél); } visszatérési távolság; }

Most összpontosítsunk a fő részre, a Szimulált Annealing algoritmus megvalósítására.

5. Szimulált hőkezelési megvalósítás

A következő Szimulált annealing megvalósításban megoldjuk a TSP problémát. Csak egy rövid emlékeztető, a cél az, hogy megtalálja a legrövidebb távolságot az összes város megtételéhez.

A folyamat elindításához három fő paramétert kell megadnunk, nevezetesen startTemperature, numberOfIterations és hűtési sebesség:

nyilvános kettős szimulációAnnealing (kettős indítási hőmérséklet, int számOfIterációk, kettős hűtési sebesség) {double t = kezdő hőmérséklet; travel.generateInitialTravel (); double bestDistance = utazás.getDistance (); Utazás currentSolution = utazás; // ...}

A szimuláció megkezdése előtt generáljuk a városok kezdeti (véletlenszerű) sorrendjét, és kiszámoljuk az utazás teljes távolságát. Mivel ez az első számított távolság, ezért a távolságon belül elmentjük bestDistance változó, a currentSolution.

A következő lépésben elindítunk egy fő szimulációs ciklust:

mert (int i = 0; i 0.1) {// ...} else {folytatás; }}

A ciklus megtartja az általunk megadott iterációk számát. Ezenkívül feltettünk egy feltételt a szimuláció leállítására, ha a hőmérséklet alacsonyabb vagy egyenlő, mint 0,1. Ez lehetővé teszi számunkra a szimulációk idejének megtakarítását, mivel alacsony hőmérsékleten az optimalizálási különbségek szinte nem látszanak.

Nézzük meg a Szimulált annealing algoritmus fő logikáját:

currentSolution.swapCities (); double currentDistance = currentSolution.getDistance (); if (currentDistance <bestDistance) {bestDistance = currentDistance; } else if (Math.exp ((bestDistance - currentDistance) / t) <Math.random ()) {currentSolution.revertSwap (); }

A szimuláció minden lépésében véletlenszerűen cserélünk két várost utazási sorrendben.

Továbbá kiszámoljuk a currentDistance. Ha az újonnan kiszámított currentDistance alacsonyabb, mint bestDistance, a legjobbként mentjük el.

Ellenkező esetben ellenőrizzük, hogy a valószínűségeloszlás Boltzmann-függvénye alacsonyabb-e, mint a véletlenszerűen kiválasztott érték, 0 és 0 közötti tartományban. Ha igen, akkor visszavonjuk a városok cseréjét. Ha nem, akkor megtartjuk a városok új rendjét, mivel ez segíthet elkerülni a helyi minimumokat.

Végül a szimuláció minden lépésében csökkentjük a hőmérsékletet hűtési ráta:

t * = hűtési sebesség;

A szimuláció után visszaküldjük a legjobb megoldást, amelyet a Szimulált hőkezelés segítségével találtunk.

Kérjük, vegye figyelembe a néhány tippet a legjobb szimulációs paraméterek kiválasztásához:

• kicsi megoldási terek esetén jobb csökkenteni a kezdő hőmérsékletet és növelni a hűtési sebességet, mivel ez csökkenti a szimulációs időt a minőség romlása nélkül
• nagyobb megoldási terek esetén kérjük, válassza a magasabb kezdő hőmérsékletet és a kis hűtési sebességet, mivel több helyi minimum lesz
• mindig elegendő időt biztosítson a szimulációhoz a rendszer magas és alacsony hőmérséklete között

Ne felejtsen el eltölteni egy kis időt az algoritmus hangolásával a kisebb problémapéldánnyal, mielőtt elkezdené a fő szimulációkat, mivel ez javítani fogja a végeredményeket. A szimulált annealing algoritmus hangolását például ebben a cikkben mutattuk be.

6. Következtetés

Ebben a gyors bemutatóban megismerhettük a Szimulált Kihúzás algoritmust és megoldottuk az utazó eladó problémáját. Remélhetőleg ez megmutatja, mennyire hasznos ez az egyszerű algoritmus, ha bizonyos típusú optimalizálási problémákra alkalmazzák.

A cikk teljes megvalósítása a GitHub oldalon található.