Reiseverkäufer Beispiel mit bekannten globalen optimalen

Question

Ich habe einen memetischen Algorithmus in Python für traveling salesman problem. Alle Testdaten (Liste der Entfernungen zwischen den Städten), die ich gefunden habe, fehlen jedoch die Informationen der besten Lösung, so dass ich nicht wissen kann, wie nahe das globale Optimum meinem Algorithmus kommt.

Weiß jemand, wo ich einige Testdaten (vorzugsweise in Matrixform, aber alles ist gut) mit bekannten besten Lösung finden kann?

Answer 1

Haben Sie gegoogelt?

http://www.tsp.gatech.edu/data/index.html

Diese Seite bietet mehrere Testfälle, von denen 16 eine optimale Lösung.

Answer 2

Vielleicht können Sie Ihre eigenen Testdaten generieren?

Dies wird definitiv nicht umfassende Tests sein, aber es könnte helfen. Hinweis: Im Folgenden wird der hamiltonische Pfad beschrieben. Wenn Sie nach Zyklen suchen, wird etwas Ähnliches funktionieren.

Sie folgendes tun:

Sagen Sie bitte einen ungerichteten Graphen G mit n Knoten angegeben.

Sie erstellen nun einen gewichteten Graphen G ', indem Sie das Gewicht der Kanten in G auf 1 setzen und die Kanten nicht in G addieren und ihnen eine zufällige Gewichtung> 1 geben, dh G' ist ein vollständiger Graph mit Gewichte, die all seinen Kanten zugewiesen sind.

Wenn Sie jetzt einen gültigen TSP-Algorithmus auf G 'ausführen und einen Pfad der Größe n-1 generiert, dann hat G einen Hamilton-Pfad. Ansonsten hat G keinen Hamilton-Pfad.

So, jetzt können Sie Diagramme verwenden Sie wissen, dass haben/nicht hamiltonsch Pfade aufweisen (z: Hypercube hamiltonsch Pfade hat) und Testdaten für Ihren TSP-Algorithmus erzeugen.

Diese Seite hat einige hinreichende Bedingungen, die nützlich sein könnten Graphen zu erzeugen, die Hamilton-Operator Pfade: http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html

Ich nehme an, Sie nicht haben eine harte Zeit der Suche nach Daten auf Graphen mit/ohne hamiltonsch Pfade haben.

Ich hoffe, es hilft. Viel Glück!

Answer 3

TSPLIB ist eine Bibliothek von Beispielinstanzen für den TSP (und verwandte Probleme) aus verschiedenen Quellen und verschiedenen Typen.

http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/