streamalism.org

1. Introduktion

I denne vejledning lærer vi om den simulerede annealing-algoritme, og vi viser eksemplets implementering baseret på TSP (Traveling Salesman Problem).

2. Simuleret annealing

Simuleret annealing-algoritmen er en heuristik til løsning af problemerne med et stort søgerum.

Inspirationen og navnet stammer fra udglødning i metallurgi; det er en teknik, der involverer opvarmning og kontrolleret afkøling af et materiale.

Generelt mindsker simuleret annealing sandsynligheden for at acceptere dårligere løsninger, da den udforsker løsningsrummet og sænker systemets temperatur. Følgende animation viser mekanismen til at finde den bedste løsning med Simulated Annealing algoritmen:

Som vi måske bemærker, bruger algoritmen et bredere løsningsområde med systemets høje temperatur og søger efter globalt optimalt. Mens temperaturen sænkes, bliver søgeområdet mindre, indtil det finder det globale optimale.

Algoritmen har et par få parametre at arbejde med:

• antal iterationer - standsningstilstand for simuleringer
• starttemperatur - systemets startenergi
• afkølingshastighedsparameter - den procentdel, hvormed vi reducerer systemets temperatur
• minimumstemperatur - valgfri stoptilstand
• simuleringstid - valgfri stoptilstand

Værdierne for disse parametre skal vælges omhyggeligt - da de kan have betydelig indflydelse på processens ydeevne.

3. Rejsende sælgerproblem

Travelsælgerproblemet (TSP) er det mest kendte problem inden for datalogioptimering i en moderne verden.

Med enkle ord er det et problem at finde den optimale rute mellem noder i grafen. Den samlede rejseafstand kan være et af optimeringskriteriet. For flere detaljer om TSP, se her.

4. Java-model

For at løse TSP-problemet har vi brug for to modelklasser, nemlig By og Rejse. I den første gemmer vi koordinaterne for noderne i grafen:

@ Data offentlig klasse By {privat int x; privat int y; public City () {this.x = (int) (Math.random () * 500); this.y = (int) (Math. tilfældigt () * 500); } offentlig dobbelt distanceToCity (byby) {int x = Math.abs (getX () - city.getX ()); int y = Math.abs (getY () - city.getY ()); returner Math.sqrt (Math.pow (x, 2) + Math.pow (y, 2)); }}

Konstruktøren af By klasse giver os mulighed for at oprette tilfældige placeringer af byerne. Det distanceToCity (..) logik er ansvarlig for beregninger vedrørende afstanden mellem byerne.

Følgende kode er ansvarlig for modellering af en rejsende sælger tur. Lad os starte med at generere den oprindelige rækkefølge af byer i rejsen:

offentlig tomrum generereInitialTravel () {hvis (travel.isEmpty ()) ny rejse (10); Collections.shuffle (rejse); }

Ud over at generere den oprindelige ordre har vi brug for metoderne til at bytte de tilfældige to byer i den rejsende rækkefølge. Vi bruger det til at søge efter de bedre løsninger inden for den simulerede annealing-algoritme:

public void swapCities () {int a = createRandomIndex (); int b = createRandomIndex (); previousTravel = rejse; By x = rejse.get (a); By y = rejse.get (b); travel.set (a, y); rejse.sæt (b, x); }

Desuden har vi brug for en metode til at tilbageføre swapgenerering i det foregående trin, hvis den nye løsning ikke accepteres af vores algoritme:

offentlig ugyldighed revertSwap () {travel = previousTravel; }

Den sidste metode, vi ønsker at dække, er beregningen af ​​den samlede rejseafstand, som vil blive brugt som et optimeringskriterium:

public int getDistance () {int distance = 0; for (int index = 0; index <travel.size (); index ++) {City start = getCity (index); By destination; hvis (indeks + 1 <rejs.størrelse ()) {destination = getCity (indeks + 1); } andet {destination = getCity (0); } distance + = start.distanceToCity (destination); } returafstand }

Lad os nu fokusere på hoveddelen, simuleret annealing algoritme implementering.

5. Simuleret annealing implementering

I den følgende simulerede annealing-implementering skal vi løse TSP-problemet. Bare en hurtig påmindelse, målet er at finde den korteste afstand til at rejse alle byer.

For at starte processen er vi nødt til at angive tre hovedparametre, nemlig starttemperatur, numberOfIterations og kølerate:

offentlig dobbelt simulateAnnealing (dobbelt starttemperatur, int antalOfIterationer, dobbelt kølerate) {dobbelt t = startTemperatur; travel.generateInitialTravel (); dobbelt bestDistance = rejse.getDistance (); RejsestrømSolution = rejse; // ...}

Før simuleringens start genererer vi den indledende (tilfældige) rækkefølge af byer og beregner den samlede afstand for rejsen. Da dette er den første beregnede afstand, gemmer vi den inde i bestDistance variabel sammen med nuværende løsning.

I det næste trin starter vi en hovedsimulationssløjfe:

for (int i = 0; i 0,1) {// ...} ellers {fortsæt; }}

Sløjfen varer det antal iterationer, som vi specificerede. Desuden tilføjede vi en betingelse for at stoppe simuleringen, hvis temperaturen vil være lavere eller lig med 0,1. Det giver os mulighed for at spare tid på simuleringer, da optimeringsforskellene næsten ikke er synlige ved lave temperaturer.

Lad os se på hovedlogikken i Simuleret Annealing-algoritmen:

currentSolution.swapCities (); dobbelt strømDistance = currentSolution.getDistance (); hvis (currentDistance <bestDistance) {bestDistance = currentDistance; } ellers hvis (Math.exp ((bestDistance - currentDistance) / t) <Math.random ()) {currentSolution.revertSwap (); }

I hvert simuleringstrin bytter vi tilfældigt to byer i rejsefølge.

Desuden beregner vi nuværende Afstand. Hvis den nyberegnede nuværende Afstand er lavere end bestDistance, vi gemmer det som det bedste.

Ellers kontrollerer vi, om sandsynlighedsfordelingens Boltzmann-funktion er lavere end tilfældigt valgt værdi i et interval fra 0-1. Hvis ja, tilbagefører vi byernes bytte. Hvis ikke, holder vi den nye orden i byerne, da det kan hjælpe os med at undgå de lokale minima.

Endelig reducerer vi temperaturen ved hvert trin i simuleringen kølepris:

t * = kølerate;

Efter simuleringen returnerer vi den bedste løsning, vi fandt ved hjælp af simuleret annealing.

Bemærk de få tip til, hvordan du vælger de bedste simuleringsparametre:

• for små løsningsrum er det bedre at sænke starttemperaturen og øge kølehastigheden, da det reducerer simuleringstiden uden at miste kvaliteten
• for større løsningsrum skal du vælge den højere starttemperatur og lille kølehastighed, da der vil være flere lokale minima
• giver altid tilstrækkelig tid til at simulere fra systemets høje til lave temperatur

Glem ikke at bruge lidt tid på algoritmen til at tune med den mindre problemforekomst, inden du starter de vigtigste simuleringer, da det vil forbedre de endelige resultater. Tuning af algoritmen Simuleret annealing blev vist for eksempel i denne artikel.

6. Konklusion

I denne hurtige vejledning var vi i stand til at lære om Simuleret Annealing algoritme og vi løste det rejsende sælgerproblem. Dette viser forhåbentlig, hvor praktisk denne enkle algoritme er, når den anvendes på visse typer optimeringsproblemer.

Den fulde implementering af denne artikel kan findes på GitHub.