Travelling-Salesman-Problem

Heuristische Verfahren

 aufwärts

Problem

Das Travelling-Salesman-Problem (TSP) oder Problem des Handlungs­reisenden besteht darin, dass ein Handlungs­reisender eine Rundreise durch n Städte unternehmen und dabei einen möglichst kurzen Weg zurücklegen soll. Die Entfernungen zwischen den einzelnen Städten sind bekannt. Gefragt ist also nach der Reihenfolge, in der die Städte besucht werden müssen.

Es gibt (n-1)! Möglichkeiten, beginnend bei einer bestimmten Stadt alle anderen Städte zu besuchen und wieder zur Ausgangsstadt zurückzukehren, zuviele, um alle durch­zuprobieren. Ein schnelleres Verfahren, das weniger als exponentielle Zeit benötigt, ist nicht bekannt und existiert wahrscheinlich auch nicht, denn TSP ist NP-vollständig.

Es stellt sich daher die Frage nach approximativen Verfahren, die zwar nicht unbedingt die beste Lösung finden, aber dieser sehr nahekommen. Hier sollen die Verfahren Simulated Annealing und Selbst­organisierende Karte [RMS 90] angewendet werden, um das Travelling-Salesman-Problem näherungsweise zu lösen.

Approximative Optimierungs­verfahren versuchen meist, ausgehend von einer vorhandenen Lösung durch eine geeignete Abänderung zu einer besseren Lösung zu gelangen. Führt keine solche mögliche Abänderung mehr zu einer Verbesserung, so ist ein Optimum gefunden. Das Problem hierbei ist, dass es sich um ein lokales Optimum handeln kann, das wesentlich schlechter ist als das globale Optimum.

Bild 1 zeigt diese Situation am Beispiel eines Minimierungs­verfahrens. Die Ausgangslösung ist A, durch schrittweise Verbesserung ist das Verfahren zur Lösung B gelangt. Alle Schritte, die von B aus möglich sind, führen zu einer Ver­schlechterung der Lösung, B ist ein lokales Minimum. Das globale Minimum liegt jedoch bei D. Das Verfahren kann das globale Minimum jetzt nur noch finden, wenn es für eine begrenzte Anzahl von Schritten auch eine Ver­schlechterung der Lösung in Kauf nimmt, so dass es über den Berg C gelangen kann (Bild 1).

Lokales und globales Minimum
Bild 1:  Lokales und globales Minimum

Die beiden hier vorgestellten Verfahren haben diese Eigenschaft, dass sie zwar einerseits die Lösung zu verbessern versuchen, andererseits aber auch Ver­schlechterungen um nicht mehr als sigma akzeptieren. Der Parameter sigma wird im Verlauf des Verfahrens kontinuierlich verringert, bis schließlich überhaupt keine Ver­schlechterungen mehr zugelassen werden.

 

Simulated Annealing

Der Begriff Annealing stammt aus der Metallurgie und bezeichnet das Tempern von Metallen. Ein Metall ist umso härter, je besser sich eine geordnete Kristall­struktur ausgebildet hat. Beim Erstarren aus der Schmelze bilden sich an vielen Stellen Kristallisations­zentren, und das Ergebnis ist ein Metall, bei dem viele kleine Kristalle kreuz und quer durch­einander­liegen. Beim Tempern wird nun das Metall nochmals bis kurz vor den Schmelzpunkt erhitzt und dann langsam wieder abgekühlt, so dass sich die Kristall­struktur des Metalls besser ausbilden kann; es bilden sich größere Kristalle, da die Metallatome innerhalb der Kristall­struktur eine niedrigere potentielle Energie haben als außerhalb der Kristall­struktur.

Durch das Tempern wird den Metallatomen noch einmal die Möglichkeit gegeben, sich zu bewegen, so dass sie beim Abkühlen einen energetisch günstigeren Platz finden können. Das Tempern muss sehr vorsichtig geschehen: wird das Metall zu stark erhitzt, kommen alle Atome wieder durch­einander und die vorher schon gefundene Ordnung wird wieder zerstört. Wird es zu schwach erhitzt, lösen sich die Atome nicht aus ihrer alten Ordnung und es wird keine bessere Ordnung gefunden.

Indem dieser Prozess des Temperns zur Herstellung eines Zustandes möglichst niedriger Energie simuliert wird – daher die Bezeichnung Simulated Annealing – erhält man ein Optimierungs­verfahren. Die Temperatur entspricht hierbei dem oben erwähnten Parameter sigma.

Anwendung auf das Travelling-Salesman-Problem

Um das Travelling-Salesman-Problem mit Simulated Annealing zu lösen, wird wie folgt vorgegangen: Gestartet wird mit einer Rundreise, die die Städte in einer völlig zufälligen Reihenfolge durchläuft. Nun wird versucht, diese Lösung zu verbessern. Hierzu werden zwei Städte si und sj zufällig ausgewählt, und der Weg von si nach sj wird in umgekehrter Richtung durchlaufen (Bild 2).

Die Reihenfolge der Städte in der neuen Rundreise ergibt sich aus der alten Reihenfolge wie folgt:

alte Reihenfolge:    ... si-1 si si+1 ... sj-1 sj sj+1 ...

neue Reihenfolge:  ... si-1 sj sj-1 ... si+1 si sj+1 ...

Ursprüngliche und verbesserte Lösung
Bild 2:  Ursprüngliche und verbesserte Lösung

Ist die neue Rundreise kürzer als die alte Rundreise, so wird mit dieser verbesserten Lösung fortgefahren. Ist sie länger, so wird sie nur dann akzeptiert, wenn sie um höchstens sigma länger ist als die alte Rundreise. Ansonsten wird sie verworfen, und es wird mit der alten Lösung fortgefahren.

Nach jeweils einer bestimmten Anzahl von Iterations­schritten wird der Parameter sigma verringert, bis er den Wert 0 erreicht, so dass zum Schluss keine Ver­schlechterung der Lösung mehr zugelassen wird.

 

Selbst­organisierende Karte

Gegeben ist ein Raum (S, d) von Stimuli; d ist eine Metrik auf S. Ferner ist ein Raum (N, g) von Neuronen gegeben; g ist eine Metrik auf N. Ziel ist es, eine Zuordnung z zwischen S und N zu finden, derart dass nah beieinander liegenden Stimuli auch nah beieinander liegende Neuronen zugeordnet sind, also eine Art stetige Abbildung.

Anwendung auf das Travelling-Salesman-Problem

Die Menge der Stimuli S ist eine endliche Menge von Punkten in der Ebene (die Städte des Travelling-Salesman-Problems), die zugehörige Metrik d ist der euklidische Abstand. Die Neuronen N bilden die Knotenmenge eines ringförmigen Graphen G = (N, E), der Abstand g zwischen zwei Neuronen i und j ist gleich der Länge des kürzesten Weges zwischen i und j. Jedem Neuron n Element N ist ein Punkt der Ebene p(n) zugeordnet.

Bild 3 ver­anschaulicht diese Situation: Die Stimuli sind rot eingezeichnet. Die blauen Punkte sind die Neuronen, und zwar ist jedes Neuron n Element N an der Position p(n) eingezeichnet. Außerdem sind die Kanten zwischen den Neuronen im Graphen G eingezeichnet. Weiterhin ist eine Abbildung z eingezeichnet, und zwar ist jedem Stimulus das nächstgelegene Neuron zugeordnet.

Stimuli S und Neuronen N
Bild 3:  Stimuli S und Neuronen N

Die dargestellte Situation hat schon die gewünschte Eigenschaft, dass nah beieinander liegenden Stimuli auch einiger­maßen nah beieinander liegende Neuronen zugeordnet sind. Die Situation lässt sich aber durch Adaptions­schritte noch verbessern.

Ein Adaptions­schritt besteht darin, dass ein Stimulus s zufällig gewählt wird. Daraufhin rückt das dem Stimulus s am nächsten liegende Neuron n um einen bestimmten Faktor h näher an s heran. Aber auch die beiden Neuronen, die im Graphen direkt mit n benachbart sind, rücken näher an s heran, allerdings um weniger als h. Und auch die Neuronen, die sich im Abstand g = 2, 3, ... von n befinden, rücken an s heran, jedoch umso weniger, je größer g ist.

Bild 4 zeigt, wie die Neuronen in einem Adaptions­schritt an den Stimulus s heranrücken.

Adaptionsschritt
Bild 4:  Adaptions­schritt

Begonnen wird mit einer beliebigen Verteilung der Neuronen in der Ebene, z.B. p(n) = (0,0) für alle n Element N. Durch eine Folge von Adaptions­schritten wird die Zuordnung z dann verbessert. Wie gut dies gelingt, hängt zum einen von der Anzahl der Neuronen ab und zum anderen davon, wie der Faktor h in Abhängigkeit vom Abstand g gewählt wird. Zu Anfang sollte der Einfluss einer Adaption auf weiter entfernte Neuronen größer sein und dann im Verlauf der Berechnung immer kleiner werden. Im allgemeinen wird die Formel

h(g)  =  ε · e -g/sigma

verwendet. Der Parameter sigma steuert den Einfluss der Adaption auf entferntere Neuronen, er ist zunächst groß und wird dann im Verlauf der Berechnung verringert. Der Parameter ε bestimmt die Stärke der Adaption überhaupt.

Am Ende der Berechnung ist der Raum N in den Raum S eingebettet. Damit ist N eine "Karte" von S, die sich durch die Adaption selbst organisiert hat, daher die Bezeichnung "selbst­organisierende Karte". Eine Rundreise durch die Städte ergibt sich, indem die Städte nach z(s) geordnet werden. Es zeigt sich, dass die erzeugten Rundreisen recht kurz sind.

 

Vergleich der Verfahren

Das folgende Applet zeigt einen Vergleich der beiden Verfahren "Selbst­organisierende Karte" (links) und "Simulated Annealing" (rechts). Für beide Verfahren gemeinsam wird der Parameter sigma geführt, der während der Berechnung schrittweise vermindert wird. Die Städte können zufällig (Random) oder regelmäßig (Regular) angeordnet werden; im letzteren Fall kann die Güte der Approximation beurteilt werden: dann hat die optimale Rundreise die Länge 2000.

 

(Java-Applet zum Vergleich der Verfahren Selbst­organisierende Karte und Simulated Annealing)

 

Literatur

[RMS 90]H. Ritter, T. Martinetz, K. Schulten: Neuronale Netze. Addison-Wesley (1990)
[Web 1]http://www.math.uwaterloo.ca/tsp/games/index.html   Spiel: Wie gut sind Sie selbst als Handlungs­reisender?

 

 

Weiter:  up

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 16.03.1999   Updated: 10.12.2013
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot

Web- und Softwaretechnologie

 

Wir bieten Ihnen ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien.

Sehen Sie sich einmal den Studienplan an.

 

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnik

Wirtschaftsinformatik