Sie haben sich sicherlich mit dem Travelling Salesman Problem (TSP) beschäftigt. Sie haben vielleicht schon einige Implementationen realisiert. Sie sind voraussichtlich darauf gestoßen, dass heuristische Verfahren in lokale Minima geraten. Daher soll hier die Frage nach dem passenden Raum für die Betrachtung des TSP diskutiert werden.
Generelle Vorstellung
Der Raum des TSP wird normalerweise als möglich Lösungen, d.h. round-trips der Input-Sequenz, und deren zugehöriger Länge betrachtet.Das ist hier auch so. Jedoch mit einer anderen Norm.
Um nun zur Erklärung zu kommen, muss vorerst eine Abgrenzung und Auflösung typischer Annahmen getroffen werden.
Sehr oft wird vermutet, dass sich gute Lösungen des TSP in der Nähe der optimalen Lösung des TSP befinden. Das wird durch viele Beispiele widerlegt.
Die Kosten, die durch eine weniger optimale Lösung, d.h. die Änderung durch vielleicht eines Punktes, entstehen, sind verhältnismäßig hoch. Wird ein Punkt verändert, so kommt es schnell zu höheren Kosten. Das liegt daran, da sich dann die Reihenfolge der Punkte ändert und dies mindestens zwei andere Kanten zur Folge hat. Diese anderen Kanten haben andere Längen, welche in der Summe dann wieder zu einer höheren Länge führen. D.h. eine Änderung eines Punktes kann typischerweise eine sehr viel höhere Gesamtlänge zur Folge haben.
Es ist also so, dass der Raum der Lösungen des TSP nicht dicht, oder gar gleich-verteilt, um die beste Lösung liegt, sondern sehr "sparse" verteilt ist. Der Begriff "sparse" kommt aus der Mathematik und ist in der ersten Interpretation das Gegenteil von dicht.
Es ist nun so, dass die Punkte, wenn wir sie uns als eindimensionale Reihenfolge vorstellen, einen großen Abstand zischen einander haben.
Der Raum der Lösungen ist beim TSP multi-dimensional. D.h. jeder Punkt bildet durch seine Position in der Reihenfolge des round-trip's, eine neue Dimension.
Damit es verständlicher wird, kann der Lösungsraum des TSP als zweidimensionale Punktwolke vorgestellt werden. Diese ist sparse verteilt.
Das Ergebnis der Lösungen, d.h. die Länge des round-trip's, kann als eine weitere Achse in einem dreidimensionalen Raum vorgestellt werden. Dies ist dann die Z-Achse.
Auf der Z-Achse wird die Gesamtlänge des round-rips, also einer Lösung, aufgetragen.
Die generelle Vorstellung ist nun, dass bei geeigneter Norm für das TSP ein Raum entsteht, der viele lokale Minima enthält.
Als "geeignete Norm", wird oft die euklidische Länge betrachtet. Unter dieser Norm tendiert der Raum jedoch stärker zu lokalen Minima.
Daher stellt sich die Frage, ob der Raum mit euklidischer Länge geeignet ist um das TSP zu Lösen. Lösen, in dem Sinne, das auf effizienteste Art und Weise die optimale Lösung gefunden wird.
Neue Vorstellung
Das Problem des nicht geeigneten Raumes, kann durch eine andere Norm gelöst werden. Typischerweise wird die euklidische Länge als "geeignete Norm" betrachtet. Jedoch bietet sich die Norm des "Umweges" eher an.In diesem hier präsentierten Lösungsansatz wird diese Norm des Umweges für die Lösung des TSP als sehr geeignet angesehen.
Es ergibt sich die Vermutung, dass unter der Norm des Umweges, welche gleich näher erläutert wird, der Raum keine lokalen Minima mehr enthält und man direkt mit Gradientenverfahren das kleinste Minima, also die optimale Lösung, bestimmen kann.
Die Norm des Umweges, in diesem Lösungsvorschlag auch SeboehDist genannt, berechnet die euklidische Länge des Weges, welcher zusätzlich notwendig ist, um von Punkt A nach Punkt B zu gehen, und dabei Punkt C auch zu besuchen.
Diese Norm bietet sich für das TSP besonders an, da vermutet wird, dass eine lokale Minimierung anhand dieser Norm, zu einem globalen optimalen kürzesten Weg nach der üblichen euklidischen Norm führt.
Resümee
In getesteten Beispielen, kann direkt gezeigt werden, dass die Verwendung der euklidischen Länge als Norm für die Lösung des kürzesten round-trip, nicht geeignet ist.Damit ist klar, dass eine optimale Lösung nicht mit der reinen Betrachtung der euklidischen Länge erreicht werden kann.
Zusätzlich hat sich gezeigt, dass die Norm SeboehDist in allen bisherig getesteten Fällen zum Erfolg führte.
Mit freundlichen Grüßen, Sebastian Böhmer
PS: Sehen Sie das auch so?
Keine Kommentare:
Kommentar veröffentlichen