streamalism.org

1. Uvod

U ovom uputstvu naučit ćemo o algoritmu simuliranog žarenja i prikazat ćemo primjer implementacije na temelju problema putujućeg prodavača (TSP).

2. Simulirano žarenje

Algoritam simuliranog žarenja heuristika je rješavanja problema s velikim prostorom pretraživanja.

Inspiracija i naziv potječu od žarenja u metalurgiji; to je tehnika koja uključuje zagrijavanje i kontrolirano hlađenje materijala.

Općenito, simulirano žarenje smanjuje vjerojatnost prihvaćanja lošijih rješenja jer istražuje prostor otopine i snižava temperaturu sustava. Sljedeća animacija prikazuje mehanizam pronalaska najboljeg rješenja s algoritmom Simulirano žarenje:

Kao što možemo primijetiti, algoritam koristi širi raspon rješenja s visokom temperaturom sustava, tražeći globalni optimum. Dok smanjuje temperaturu, domet pretraživanja postaje sve manji, sve dok ne pronađe globalni optimum.

Algoritam ima nekoliko parametara za rad:

• broj iteracija - zaustavni uvjet za simulacije
• početna temperatura - početna energija sustava
• parametar brzine hlađenja - postotak za koji smanjujemo temperaturu sustava
• minimalna temperatura - neobavezni uvjet zaustavljanja
• vrijeme simulacije - neobavezni uvjet zaustavljanja

Vrijednosti tih parametara moraju se pažljivo odabrati - jer mogu imati značajan utjecaj na izvedbu postupka.

3. Problem putničkog trgovca

Problem putničkog trgovca (TSP) najpoznatiji je problem optimizacije informatike u modernom svijetu.

Jednostavnim riječima, problem je pronaći optimalnu rutu između čvorova na grafu. Ukupna udaljenost putovanja može biti jedan od kriterija optimizacije. Za više detalja o TSP-u pogledajte ovdje.

4. Java model

Da bismo riješili problem TSP-a, trebat će nam, naime, dvije klase modela Grad i Putovati. U prvom ćemo pohraniti koordinate čvorova u grafikon:

@Data javna klasa Grad {private int x; privatni int y; javni City () {this.x = (int) (Math.random () * 500); this.y = (int) (Math.random () * 500); } javna dvostruka distanceToCity (City city) {int x = Math.abs (getX () - city.getX ()); int y = Math.abs (getY () - city.getY ()); vrati Math.sqrt (Math.pow (x, 2) + Math.pow (y, 2)); }}

Konstruktor za Grad klasa omogućuje nam stvaranje slučajnih lokacija gradova. The distanceToCity (..) logika je odgovorna za izračune u pogledu udaljenosti između gradova.

Sljedeći je kôd odgovoran za modeliranje obilaska trgovačkog putnika. Počnimo s generiranjem početnog redoslijeda gradova u putovanjima:

javna praznina generirajInitialTravel () {if (travel.isEmpty ()) new Putovanje (10); Collections.shuffle (travel); }

Osim generiranja početnog naloga, potrebne su nam metode zamjene slučajnih dvaju gradova u putnom nalogu. Koristit ćemo ga za traženje boljih rješenja unutar algoritma Simulirano žarenje:

javna void swapCities () {int a = generirajRandomIndex (); int b = generirajRandomIndex (); previousTravel = putovanje; Grad x = travel.get (a); Grad y = travel.get (b); travel.set (a, y); travel.set (b, x); }

Nadalje, trebamo metodu za vraćanje zamjene koja je generirala u prethodnom koraku, ako novo rješenje neće prihvatiti naš algoritam:

javna praznina revertSwap () {travel = previousTravel; }

Posljednja metoda koju želimo pokriti je izračunavanje ukupne udaljenosti putovanja, koja će se koristiti kao kriterij optimizacije:

javni int getDistance () {int udaljenost = 0; for (int index = 0; index <travel.size (); index ++) {Početak grada = getCity (indeks); Odredište grada; if (indeks + 1 <travel.size ()) {odredište = getCity (indeks + 1); } else {odredište = getCity (0); } udaljenost + = start.distanceToCity (odredište); } povratna udaljenost; }

Sada ćemo se usredotočiti na glavni dio, implementaciju simuliranog žarenja.

5. Simulirana provedba žarenja

U sljedećoj provedbi simuliranog žarenja riješit ćemo problem TSP-a. Samo kratki podsjetnik, cilj je pronaći najkraću udaljenost za putovanje svim gradovima.

Da bismo započeli postupak, moramo navesti tri glavna parametra, naime početna temperatura, numberOfIterations i brzina hlađenja:

javno dvostruko simuliranje žarenja (dvostruka početna temperatura, int brojOfIteracije, dvostruka brzina hlađenja) {dvostruko t = početna temperatura; travel.generateInitialTravel (); dvostruko najboljeDistanca = travel.getDistance (); Travel currentSolution = putovanje; // ...}

Prije početka simulacije generiramo početni (slučajni) redoslijed gradova i izračunavamo ukupnu udaljenost za putovanje. Kako je ovo prva izračunata udaljenost, spremamo je u bestDistance varijabla, zajedno s currentSolution.

U sljedećem koraku započinjemo glavnu petlju simulacija:

za (int i = 0; i 0,1) {// ...} ostalo {nastaviti; }}

Petlja će trajati broj iteracija koje smo naveli. Štoviše, dodali smo uvjet da zaustavimo simulaciju ako će temperatura biti niža ili jednaka 0,1. Omogućit će nam vrijeme simulacija, jer s niskim temperaturama razlike u optimizaciji gotovo nisu vidljive.

Pogledajmo glavnu logiku algoritma simuliranog žarenja:

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

U svakom koraku simulacije nasumce zamijenimo dva grada po redoslijedu putovanja.

Nadalje, izračunavamo currentDistance. Ako se novo izračunati currentDistance je niža od bestDistance, spremamo je kao najbolju.

Inače, provjeravamo je li Boltzmannova funkcija raspodjele vjerojatnosti niža od slučajno odabrane vrijednosti u rasponu od 0-1. Ako je odgovor da, vraćamo zamjenu gradova. Ako ne, zadržavamo novi poredak gradova, jer nam može pomoći da izbjegnemo lokalne minimume.

Napokon, u svakom koraku simulacije smanjujemo predviđenu temperaturu Rok hlađenja:

t * = brzina hlađenja;

Nakon simulacije vraćamo najbolje rješenje koje smo pronašli pomoću simuliranog žarenja.

Imajte na umu nekoliko savjeta kako odabrati najbolje simulacijske parametre:

• za male prostore s otopinama bolje je sniziti početnu temperaturu i povećati brzinu hlađenja, jer će smanjiti vrijeme simulacije, bez gubitka na kvaliteti
• za veće prostore s otopinama odaberite veću početnu temperaturu i malu brzinu hlađenja, jer će biti više lokalnih minimuma
• uvijek osigurajte dovoljno vremena za simulaciju od visoke do niske temperature sustava

Ne zaboravite potrošiti neko vrijeme na ugađanje algoritma s manjom instancom problema, prije nego što započnete glavne simulacije, jer će to poboljšati konačne rezultate. Ugađanje algoritma simuliranog žarenja prikazano je, na primjer, u ovom članku.

6. Zaključak

U ovom smo brzom vodiču mogli saznati više o algoritmu simuliranog žarenja i riješili smo problem putničkog trgovca. Nadamo se da će ovo pokazati koliko je praktičan ovaj jednostavan algoritam, kada se primjenjuje na određene vrste problema s optimizacijom.

Potpuna provedba ovog članka može se naći na GitHubu.