Das Problem des Handlungsreisenden in Java

1. Einleitung

In diesem Tutorial lernen wir den Simulated Annealing-Algorithmus kennen und zeigen die Beispielimplementierung basierend auf dem Travelling Salesman Problem (TSP).

2. Simuliertes Tempern

Der Simulated Annealing-Algorithmus ist eine Heuristik zur Lösung der Probleme mit einem großen Suchraum.

Die Inspiration und der Name kamen vom Glühen in der Metallurgie; Es ist eine Technik, die das Erhitzen und kontrollierte Abkühlen eines Materials beinhaltet.

Im Allgemeinen verringert das simulierte Tempern die Wahrscheinlichkeit, schlechtere Lösungen zu akzeptieren, wenn es den Lösungsraum untersucht und die Temperatur des Systems senkt. Die folgende Animation zeigt den Mechanismus zum Finden der besten Lösung mit dem Simulated Annealing-Algorithmus:

Wie wir beobachten können, verwendet der Algorithmus einen breiteren Lösungsbereich mit hoher Systemtemperatur und sucht nach dem globalen Optimum. Während die Temperatur gesenkt wird, wird der Suchbereich kleiner, bis das globale Optimum gefunden wird.

Der Algorithmus verfügt über einige Parameter, mit denen gearbeitet werden kann:

  • Anzahl der Iterationen - Stoppbedingung für Simulationen
  • Anfangstemperatur - die Startenergie des Systems
  • Abkühlratenparameter - der Prozentsatz, um den wir die Temperatur des Systems senken
  • Mindesttemperatur - optionale Stoppbedingung
  • Simulationszeit - optionale Stoppbedingung

Die Werte dieser Parameter müssen sorgfältig ausgewählt werden, da sie einen erheblichen Einfluss auf die Leistung des Prozesses haben können.

3. Problem mit dem reisenden Verkäufer

Das Travelling Salesman Problem (TSP) ist das bekannteste Problem der Optimierung der Informatik in einer modernen Welt.

Mit einfachen Worten, es ist ein Problem, eine optimale Route zwischen Knoten im Diagramm zu finden. Die Gesamtfahrstrecke kann eines der Optimierungskriterien sein. Weitere Details zu TSP finden Sie hier.

4. Java-Modell

Um das TSP-Problem zu lösen, benötigen wir zwei Modellklassen, nämlich Stadt und Reisen . Im ersten werden die Koordinaten der Knoten im Diagramm gespeichert:

@Data public class City { private int x; private 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()); return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2)); } }

Der Konstruktor der Stadt Klasse ermöglicht es uns , zufällige Orte der Städte zu schaffen. Die Logik distanceToCity (..) ist für die Berechnung der Entfernung zwischen den Städten verantwortlich.

Der folgende Code ist für die Modellierung einer Tour durch reisende Verkäufer verantwortlich. Beginnen wir mit der Generierung der ersten Reihenfolge der Städte auf Reisen:

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

Zusätzlich zur Generierung der ursprünglichen Bestellung benötigen wir die Methoden zum Vertauschen der beiden zufälligen Städte in der Reisereihenfolge. Wir werden es verwenden, um nach den besseren Lösungen innerhalb des Simulated Annealing-Algorithmus zu suchen:

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

Darüber hinaus benötigen wir eine Methode, um die im vorherigen Schritt generierte Swap-Funktion zurückzusetzen, wenn die neue Lösung von unserem Algorithmus nicht akzeptiert wird:

public void revertSwap() { travel = previousTravel; }

Die letzte Methode, die wir behandeln möchten, ist die Berechnung der Gesamtfahrstrecke, die als Optimierungskriterium verwendet wird:

public int getDistance() { int distance = 0; for (int index = 0; index < travel.size(); index++) { City starting = getCity(index); City destination; if (index + 1 < travel.size()) { destination = getCity(index + 1); } else { destination = getCity(0); } distance += starting.distanceToCity(destination); } return distance; }

Konzentrieren wir uns nun auf den Hauptteil, die Implementierung des Simulated Annealing-Algorithmus.

5. Simulierte Glühimplementierung

In der folgenden Implementierung von Simulated Annealing werden wir das TSP-Problem lösen. Nur eine kurze Erinnerung, das Ziel ist es, die kürzeste Entfernung zu finden, um alle Städte zu bereisen.

Um zu starten, müssen wir drei Hauptparameter zur Verfügung zu stellen, nämlich startingTemperature , numberOfIterations und Kühlrate :

public double simulateAnnealing(double startingTemperature, int numberOfIterations, double coolingRate) { double t = startingTemperature; travel.generateInitialTravel(); double bestDistance = travel.getDistance(); Travel currentSolution = travel; // ... }

Vor dem Start der Simulation generieren wir eine anfängliche (zufällige) Reihenfolge der Städte und berechnen die Gesamtentfernung für die Reise. Da dies der erste berechnete Abstand ist, speichern wir sie in der bestDistance Variable neben der currentSolution.

Im nächsten Schritt starten wir eine Hauptsimulationsschleife:

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

Die Schleife dauert die von uns angegebene Anzahl von Iterationen. Darüber hinaus haben wir eine Bedingung hinzugefügt, um die Simulation zu stoppen, wenn die Temperatur niedriger oder gleich 0,1 ist. Dadurch können wir Zeit für Simulationen sparen, da bei niedrigen Temperaturen die Optimierungsunterschiede fast nicht sichtbar sind.

Schauen wir uns die Hauptlogik des Simulated Annealing-Algorithmus an:

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

In jedem Simulationsschritt tauschen wir zufällig zwei Städte in der Reisereihenfolge aus.

Außerdem berechnen wir den aktuellen Abstand . Wenn der neu berechnete currentDistance niedriger als ist bestDistance , speichern wir es als das beste.

Andernfalls prüfen wir, ob die Boltzmann-Funktion der Wahrscheinlichkeitsverteilung niedriger als der zufällig ausgewählte Wert in einem Bereich von 0-1 ist. Wenn ja, setzen wir den Tausch der Städte zurück. Wenn nicht, behalten wir die neue Ordnung der Städte bei, da dies uns helfen kann, die lokalen Minima zu vermeiden.

Schließlich reduzieren wir in jedem Schritt der Simulation die Temperatur durch die bereitgestellte Kühlrate:

t *= coolingRate;

Nach der Simulation geben wir die beste Lösung zurück, die wir mit Simulated Annealing gefunden haben.

Please note the few tips on how to choose the best simulation parameters:

  • for small solution spaces it's better to lower the starting temperature and increase the cooling rate, as it will reduce the simulation time, without lose of quality
  • for bigger solution spaces please choose the higher starting temperature and small cooling rate, as there will be more local minima
  • always provide enough time to simulate from the high to low temperature of the system

Don't forget to spend some time on the algorithm tuning with the smaller problem instance, before you start the main simulations, as it will improve final results. The tuning of the Simulated Annealing algorithm was shown for example in this article.

6. Conclusion

In diesem kurzen Tutorial konnten wir den Simulated Annealing-Algorithmus kennenlernen und das Travelling Salesman-Problem lösen . Dies zeigt hoffentlich, wie praktisch dieser einfache Algorithmus ist, wenn er auf bestimmte Arten von Optimierungsproblemen angewendet wird.

Die vollständige Implementierung dieses Artikels finden Sie auf GitHub.