streamalism.org

1. Úvod

V tomto výučbe sa dozvieme o algoritme simulovaného žíhania a ukážeme si príklad implementácie založenej na probléme Traveling Salesman Problem (TSP).

2. Simulované žíhanie

Algoritmus Simulované žíhanie je heuristikou riešenia problémov s veľkým vyhľadávacím priestorom.

Inšpirácia a názov pochádzajú zo žíhania v metalurgii; je to technika, ktorá zahŕňa zahrievanie a riadené chladenie materiálu.

Simulované žíhanie vo všeobecnosti znižuje pravdepodobnosť prijatia horších riešení, pretože skúma priestor riešenia a znižuje teplotu systému. Nasledujúca animácia ukazuje mechanizmus hľadania najlepšieho riešenia pomocou algoritmu simulovaného žíhania:

Ako môžeme pozorovať, algoritmus využíva širší rozsah riešení s vysokou teplotou systému a hľadá globálne optimum. Pri znižovaní teploty sa rozsah hľadania zmenšuje, až kým nenájde globálne optimum.

Algoritmus má niekoľko parametrov, s ktorými je možné pracovať:

• počet iterácií - stav zastavenia pre simulácie
• počiatočná teplota - počiatočná energia systému
• parameter chladiacej rýchlosti - percento, o ktoré znížime teplotu systému
• minimálna teplota - voliteľný stav zastavenia
• simulačný čas - voliteľná podmienka zastavenia

Hodnoty týchto parametrov musia byť starostlivo vybrané - pretože môžu mať podstatný vplyv na výkonnosť procesu.

3. Problém s cestujúcim predavačom

Problém cestovného predajcu (TSP) je najznámejší problém s optimalizáciou počítačovej vedy v modernom svete.

Jednoducho povedané, v grafe je problém nájsť optimálnu cestu medzi uzlami. Celková cestovná vzdialenosť môže byť jedným z optimalizačných kritérií. Viac informácií o TSP nájdete tu.

4. Java model

Na vyriešenie problému TSP budeme potrebovať dve modelové triedy, a to Mesto a Cestovanie. V prvom uložíme súradnice uzlov do grafu:

@ Data public class City {private int x; súkromné ​​int y; public City () {this.x = (int) (Math.random () * 500); this.y = (int) (Math.random () * 500); } public double distanceToCity (City city) {int x = Math.abs (getX () - city.getX ()); int y = Math.abs (getY () - city.getY ()); návrat Math.sqrt (Math.pow (x, 2) + Math.pow (y, 2)); }}

Konštruktér spoločnosti Mesto trieda nám umožňuje vytvárať náhodné polohy miest. The distanceToCity (..) logika je zodpovedná za výpočty týkajúce sa vzdialenosti medzi mestami.

Nasledujúci kód je zodpovedný za modelovanie cesty obchodného cestujúceho. Začnime s generovaním počiatočného poradia miest v cestovaní:

public void generateInitialTravel () {if (travel.isEmpty ()) new Travel (10); Zbierky.shuffle (cestovanie); }

Okrem generovania počiatočného poradia potrebujeme metódy výmeny náhodných dvoch miest v cestovnom poradí. Použijeme ho na hľadanie lepších riešení v algoritme simulovaného žíhania:

public void swapCities () {int a = generateRandomIndex (); int b = generateRandomIndex (); previousTravel = cestovanie; Mesto x = travel.get (a); Mesto y = travel.get (b); travel.set (a, y); travel.set (b, x); }

Ďalej potrebujeme metódu na vrátenie generovania swapu v predchádzajúcom kroku, ak náš algoritmus nebude akceptovať nové riešenie:

public void revertSwap () {travel = previousTravel; }

Poslednou metódou, ktorú chceme pokryť, je výpočet celkovej cestovnej vzdialenosti, ktorý sa použije ako kritérium optimalizácie:

public int getDistance () {int vzdialenosť = 0; pre (int index = 0; index <travel.size (); index ++) {Počiatočné mesto = getCity (index); Cieľ mesta; if (index + 1 <travel.size ()) {destination = getCity (index + 1); } else {destination = getCity (0); } vzdialenosť + = starting.distanceToCity (cieľ); } spiatočná vzdialenosť; }

Teraz sa zameriame na hlavnú časť, implementáciu algoritmu Simulovaného žíhania.

5. Implementácia simulovaného žíhania

V nasledujúcej implementácii Simulovaného žíhania ideme vyriešiť problém TSP. Len na pripomenutie, cieľom je nájsť najkratšiu vzdialenosť na prekonanie všetkých miest.

Aby sme mohli zahájiť proces, musíme uviesť tri hlavné parametre, a to počiatočná teplota, numberOfIterations a chladiaca rýchlosť:

verejné zdvojnásobenie simulateAnnealing (zdvojnásobenie počiatočnej teploty, int početOfIterácií, zdvojnásobenie chladiacej rýchlosti) {dvojnásobok t = začiatočná teplota; travel.generateInitialTravel (); double bestDistance = travel.getDistance (); Cestovný prúd Riešenie = cestovanie; // ...}

Pred začiatkom simulácie vygenerujeme počiatočné (náhodné) poradie miest a vypočítame celkovú cestovnú vzdialenosť. Pretože toto je prvá vypočítaná vzdialenosť, uložíme ju do bestDistance premenná spolu s currentSolution.

V ďalšom kroku spustíme hlavnú simulačnú slučku:

for (int i = 0; i 0,1) {// ...} else {continue; }}

Smyčka vydrží počet iterácií, ktoré sme zadali. Ďalej sme pridali podmienku na zastavenie simulácie, ak bude teplota nižšia alebo rovná 0,1. Umožní nám to ušetriť čas simulácií, pretože pri nízkych teplotách nie sú optimalizačné rozdiely takmer viditeľné.

Pozrime sa na hlavnú logiku algoritmu simulovaného žíhania:

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

V každom kroku simulácie náhodne zameníme dve mestá v poradí na cestách.

Ďalej vypočítame currentDistance. Ak novo vypočítané currentDistance je nižšia ako bestDistance, ukladáme to ako najlepšie.

V opačnom prípade skontrolujeme, či je Boltzmannova funkcia rozdelenia pravdepodobnosti nižšia ako náhodne vybraná hodnota v rozsahu od 0 do 1. Ak áno, vraciame zámenu miest. Ak nie, zachovávame nové poradie miest, pretože nám môže pomôcť vyhnúť sa miestnym minimám.

Nakoniec v každom kroku simulácie znížime teplotu podľa predpokladu rýchlosť chladenia:

t * = chladiacaRýchlosť;

Po simulácii vrátime najlepšie riešenie, ktoré sme našli pomocou Simulovaného žíhania.

Vezmite prosím na vedomie niekoľko tipov, ako zvoliť najlepšie parametre simulácie:

• pre malé priestory na riešenie je lepšie znížiť počiatočnú teplotu a zvýšiť rýchlosť chladenia, pretože to zníži čas simulácie bez straty kvality
• pre väčšie priestory na riešenie zvoľte vyššiu začiatočnú teplotu a malú rýchlosť chladenia, pretože bude existovať viac miestnych minim
• vždy poskytnite dostatok času na simuláciu od vysokej po nízku teplotu systému

Pred spustením hlavných simulácií nezabudnite stráviť nejaký čas vyladením algoritmu s menšou inštanciou problému, pretože to zlepší konečné výsledky. Vyladenie algoritmu Simulovaného žíhania bolo ukázané napríklad v tomto článku.

6. Záver

V tomto rýchlom výučbe sme sa mohli dozvedieť o algoritme simulovaného žíhania a vyriešili sme problém Cestujúci predavač. Dúfajme, že to ukáže, aký užitočný je tento jednoduchý algoritmus pri použití na určité typy optimalizačných problémov.

Celú implementáciu tohto článku nájdete na GitHub.