Det reisende selgerproblemet i Java

1. Introduksjon

I denne opplæringen lærer vi om Simulated Annealing-algoritmen, og vi viser eksemplet på implementering basert på Travelling Salesman Problem (TSP).

2. Simulert annealing

Simulert annealing-algoritmen er en heuristikk for å løse problemene med et stort søkeområde.

Inspirasjonen og navnet kom fra gløding i metallurgi; det er en teknikk som innebærer oppvarming og kontrollert kjøling av et materiale.

Generelt reduserer Simulert annealing sannsynligheten for å akseptere dårligere løsninger når den utforsker løsningsrommet og senker temperaturen i systemet. Følgende animasjon viser mekanismen for å finne den beste løsningen med Simulated Annealing algoritmen:

Som vi kan se, bruker algoritmen et bredere løsningsområde med høy temperatur i systemet, og søker etter globalt optimalt. Mens du senker temperaturen, blir søkeområdet mindre, til det finner det globale optimale.

Algoritmen har noen få parametere å jobbe med:

  • antall iterasjoner - stopptilstand for simuleringer
  • starttemperatur - systemets startenergi
  • kjølehastighetsparameter - prosentandelen som vi reduserer systemets temperatur med
  • minimumstemperatur - valgfri stopptilstand
  • simuleringstid - valgfri stopptilstand

Verdiene til disse parameterne må velges nøye - siden de kan ha betydelig innflytelse på ytelsen til prosessen.

3. Reisende selgerproblem

Travelselgerproblemet (TSP) er det mest kjente informasjonsoptimaliseringsproblemet i en moderne verden.

Med enkle ord er det et problem å finne optimal rute mellom noder i grafen. Den totale reiseavstanden kan være et av optimaliseringskriteriene. For mer informasjon om TSP, ta en titt her.

4. Java-modell

For å løse TSP-problemet trenger vi to modellklasser, nemlig By og Reise. I den første lagrer vi koordinatene til nodene i grafen:

@ Data offentlig klasse By {privat int x; privat int y; offentlig by () {this.x = (int) (Math.random () * 500); this.y = (int) (Math.random () * 500); } offentlig dobbel 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 av By klasse lar oss lage tilfeldige steder i byene. De distanceToCity (..) logikk er ansvarlig for beregninger angående avstanden mellom byene.

Følgende kode er ansvarlig for modellering av en omreisende selger-tur. La oss begynne med å generere innledende rekkefølge av byer på reise:

offentlig tomrom generereInitialTravel () {hvis (travel.isEmpty ()) ny reise (10); Collections.shuffle (reise); }

I tillegg til å generere den opprinnelige bestillingen, trenger vi metodene for å bytte de tilfeldige to byene i reiseordren. Vi bruker den til å søke etter de bedre løsningene i Simulert Annealing-algoritmen:

public void swapCities () {int a = createRandomIndex (); int b = createRandomIndex (); previousTravel = reise; By x = reise. Få (a); By y = reise.get (b); travel.set (a, y); travel.set (b, x); }

Videre trenger vi en metode for å tilbakestille byttegenereringen i forrige trinn, hvis den nye løsningen ikke blir akseptert av algoritmen vår:

offentlig ugyldig revertSwap () {travel = previousTravel; }

Den siste metoden vi ønsker å dekke er beregningen av den totale reiseavstanden, som vil bli brukt som et optimaliseringskriterium:

public int getDistance () {int distance = 0; for (int index = 0; index <travel.size (); index ++) {City starting = getCity (index); By destinasjon; hvis (indeks + 1 <travel.size ()) {destinasjon = getCity (indeks + 1); } annet {destinasjon = getCity (0); } distanse + = startdistanseToCity (destinasjon); } returavstand; }

La oss nå fokusere på hoveddelen, Simulert annealing algoritme implementering.

5. Simulert annealing Implementation

I den følgende simulerte annealing-implementeringen skal vi løse TSP-problemet. Bare en rask påminnelse, målet er å finne den korteste avstanden for å reise alle byene.

For å starte prosessen, må vi oppgi tre hovedparametere, nemlig starter temperatur, numberOfIterations og kjølepris:

public double simulateAnnealing (double startingTemperature, int numberOfIterations, double coolingRate) {double t = startingTemperature; travel.generateInitialTravel (); dobbelt bestDistance = travel.getDistance (); Reisestrøm Løsning = reise; // ...}

Før simuleringsstart, genererer vi innledende (tilfeldig) rekkefølge av byer og beregner den totale distansen for reisen. Ettersom dette er den første beregnede avstanden, lagrer vi den inne i bestDistance variabel, sammen med nåværende løsning.

I neste trinn starter vi en hovedsimuleringssløyfe:

for (int i = 0; i 0.1) {// ...} annet {fortsett; }}

Sløyfen vil vare antallet iterasjoner som vi spesifiserte. Videre la vi til en betingelse for å stoppe simuleringen hvis temperaturen vil være lavere eller lik 0,1. Det vil tillate oss å spare tid på simuleringer, da optimaliseringsforskjellene nesten ikke er synlige ved lave temperaturer.

La oss se på hovedlogikken til Simulated Annealing-algoritmen:

currentSolution.swapCities (); dobbel strømDistanse = gjeldende løsning.getDistanse (); if (currentDistance <bestDistance) {bestDistance = currentDistance; } annet hvis (Math.exp ((bestDistance - currentDistance) / t) <Math.random ()) {currentSolution.revertSwap (); }

I hvert simuleringstrinn bytter vi tilfeldig to byer i reisefølgen.

Videre beregner vi gjeldende avstand. Hvis den nylig beregnede gjeldende avstand er lavere enn bestDistance, vi lagrer det som det beste.

Ellers sjekker vi om Boltzmann-funksjonen for sannsynlighetsfordeling er lavere enn tilfeldig valgt verdi i et område fra 0-1. Hvis ja, tilbakestiller vi byttet til byene. Hvis ikke, holder vi den nye ordenen i byene, da det kan hjelpe oss med å unngå lokale minima.

Til slutt, i hvert trinn i simuleringen, reduserer vi temperaturen ved å tilby kjølepris:

t * = kjølepris;

Etter simuleringen returnerer vi den beste løsningen vi fant ved hjelp av Simulated Annealing.

Vær oppmerksom på noen få tips om hvordan du velger de beste simuleringsparametrene:

  • for små løsningsrom er det bedre å senke starttemperaturen og øke kjølehastigheten, da det vil redusere simuleringstiden uten å miste kvaliteten
  • For større løsningsrom, velg høyere starttemperatur og liten kjølehastighet, da det vil være flere lokale minima
  • gi alltid nok tid til å simulere fra høy til lav temperatur i systemet

Ikke glem å bruke litt tid på algoritmen på å justere den mindre problemforekomsten før du starter hovedsimuleringene, da det vil forbedre de endelige resultatene. Innstillingen av den simulerte annealing-algoritmen ble vist for eksempel i denne artikkelen.

6. Konklusjon

I denne raske opplæringen var vi i stand til å lære om Simulert Annealing algoritme og vi løste problemet omreisende selger. Dette viser forhåpentligvis hvor nyttig denne enkle algoritmen er, når den brukes på visse typer optimaliseringsproblemer.

Den fulle implementeringen av denne artikkelen finner du på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found