Beispiel für Reiseverkäufer mit bekanntem globalem Optimum

Question

Ich habe einen memetischen Algorithmus in Python für gemacht Problem mit reisenden Verkäufern. In allen Testdaten (Liste der Entfernungen zwischen Städten), auf die ich gestoßen bin, fehlt es jedoch nicht die Informationen über die beste Lösung. Daher kann ich nicht wissen, wie nahe mein Algorithmus ist.

Weiß jemand, wo ich einige TSP -Testdaten finden kann (vorzugsweise in Matrixform, aber alles Gute) mit bekannter beste Lösung?

Answer 1

Hast du Google?

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

Diese Seite enthält mehrere Testbewohner, von denen 16 eine optimale Lösung aufweist.

Answer 2

Vielleicht können Sie Ihre eigenen Testdaten generieren?

Dies wird definitiv kein umfassendes Test sein, aber es könnte helfen. Hinweis: Im Folgenden handelt es sich um einen Hamiltonschen Weg, und wenn Sie nach Zyklen suchen, funktioniert ähnliches.

Sie können Folgendes machen:

Angenommen, Sie erhalten ein ungerichtes Diagramm G mit n Knoten.

Sie erstellen nun ein gewichtetes Diagramm G ', indem Sie das Gewicht der Kanten in G auf 1 einstellen und die Kanten nicht in G hinzufügen und ihnen ein zufälliges Gewicht> 1 geben, dh G' ist ein vollständiges Diagramm mit Gewichten, die allen zugewiesen sind seine Kanten.

Wenn Sie nun einen gültigen TSP-Algorithmus auf G 'ausführen und einen Pfad der Größe N-1 erzeugt, hat G einen Hamiltonschen Weg. Andernfalls hat G keinen Hamiltonschen Weg.

Jetzt können Sie Diagramme verwenden kennt Das haben/haben keine Hamiltonschen Wege (für zB: Hypercube hat Hamiltonsche Wege) und generieren Testdaten für Ihren TSP -Algorithmus.

Diese Seite hat einige ausreichende Bedingungen, die sich als nützlich erweisen könnten, um Grafiken mit Hamiltonschen Wegen zu erzeugen: http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html

Ich nehme an, Sie haben es nicht schwer, Daten zu Grafiken mit/ohne Hamiltonschen Wege zu finden.

Ich hoffe es hilft. Viel Glück!

Answer 3

TSPLIB ist eine Bibliothek von Stichprobeninstanzen für die TSP (und verwandte Probleme) aus verschiedenen Quellen und verschiedener Typen.

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