Traveling Salesman Problem - Lösungsansätze

Simulated Annealing gehört zu den schrittweisen (iterativen) Lösungsansätzen. Dabei wird zuerst zufällig eine Tour ausgewählt. Die Kosten dieser Tour werden wahrscheinlich sehr groß sein. Im nächsten Schritt wird eine kleine Änderung dieserTour vorgenommen. Wenn dies zu einer Senkung der Kosten führt, wird diese Tour als neue, bessere Tour übernommen.

Diese Schritte werden solange wiederholt, bis die kleinen Änderungen nicht mehr zu einer Senkung der Kosten führen. Die so gefundenen Tour wird aber wahrscheinlich nicht die optimale Tour sein. Der Algorithmus wird wohl eher in einem lokalen Minimum steckenbleiben.

Da aber das globale Minimum gesucht wird, bemühten sich KIRKPATRIK, GELATT und VECCI um eine Verbesserung diese Algorithmus. Die Idee kam dazu aus der Metallurgie.

Metalle bestehen aus Kristallen. Diese Kristalle bilden eine regelmäßige Anordnung von Atomen. Je regelmäßiger die Anordnung der Atome desto besser ist die Energiebilanz des Metalls.

Solche Metalle sind aber nur schwer herzustellen. Sie müssen in einem aufwendigen Verfahren erzeugt werden. Dazu werden die Metalle, die aus der Schmelze kommen, langsam abgekühlt. Teilweise werden sie sogar wieder erhitzt. Dadurch können sich die Atome an ihre 'korrekten' Plätze begeben.

Wo besteht jetzt der Zusammenhang zum TSP? Vielleicht wird der Zusammenhang deutlicher mit einem Beispiel. Dabei geht es um die gedankliche Veranschaulichung des Simulated Annealing. Man stelle sich ein Gebirge vor, so ähnlich wie einen Eierkarton. Nur, daß die Täler und Berge unterschiedliche Höhen haben.

Jetzt läßt man in dieses Gebirge eine Kugel fallen. Sie wird sicherlich in einem lokalen Minimum landen. Jetzt beginnt man, das gesamte Gebirge hin und her zu schütteln. Wenn man stark genug schüttelt, rollt die Kugel aus dem Minimum heraus in ein anderes. Je tiefer dieses Minimum ist, desto schwerer ist es für die Kugel, diesen Bereich wieder zu verlassen. Das Schütteln des Gebirges wird immer weniger, bis es schließlich ganz aufhört. Die Kugel wird letzendlich in einem Minimum liegen bleiben, das vielleicht nicht das globale Minimum ist, aber doch tiefer als die lokalen Minima in der Umgebung.

Diese lokalen Minima sind die, in denen die einfachen iterativen Ansätze des TSP steckenbleiben. Man versucht also, durch kurzzeitige Verschlechterung der Tourkosten (Überwinden des Berges) dichter an die optimale Tour heranzukommen.

Es geht jetzt darum, zu berechnen, ob es bei gegegebener Temperatur für die Kugel wahrscheinlicher ist in ihrem Zustand zu bleiben, oder ihren Zustand zu ändern. Wichtig für das Verständnis ist dabei folgende Formel:

P(Z1) / P(Z2) = exp ( (E(Z2) - E(Z1)) / (k * T))

Dabei bedeuten Z1 und Z2 die Zustände, P ist die Wahrscheinlichkeit des Zustandes, E die Energie, k die Boltzmann-Konstante und T die Temperatur.

In der Praxis wird eine Zufallszahl zwischen 0 und 1 bestimmt. Ist diese kleiner als P(Z1)/P(Z2), so wird der neue Zustand angenommen, auch wenn dieser energetisch schlechter ist.

Für das TSP wird als Temperatur die Entfernung gewählt. Nimmt man eine hohe Temperatur (Entfernung) wird fast jede Änderung in der Reihenfolge der Tour akzeptiert werden. Je geringer die Temperatur wird, desto kleiner sind die Änderungen, die akzeptiert werden.

Der Pseudocode, sowie eine Verbesserung des Algorithmus durch Threshold Accepting können in der c't Heft 1, 1994, S.190-192 nachgelesen werden.

Die Leistungsfähigkeit des Algorithmus kann hier getestet werden.