Welcher Ansatz erzeugt die kürzere Tour im TSP Problem: nächsten Nachbarn oder genetische Algorithmen?

Question

In den letzten Tagen habe ich ein paar web rel="nofollow Sites , die TS-Lösung demonstriert genetische Algorithmen.

Welche ist Ansatz die kürzere Tour im TSP Problem erzeugt: nächsten Nachbarn oder genetische Algorithmen

Answer 1

Da weder Technik eine optimale Lösung garantiert, wird Ihre Laufleistung variieren. Mit ein wenig Glück kann entweder Technik aus-führen die andere. Beide Techniken haben Vor- und Nachteile.

Nächster Nachbar: + schnell, + einfache, -Normalerweise nicht optimal

Genetische Algorithmus: -slower, -Mehr Komplex, + Lösungen Trend zur optimalen Lauf der Zeit

Der große Unterschied ist, dass randomisierte Algorithmen wie simulierte Glühen und genetische Algorithmen können weiterhin im Laufe der Zeit verbessern - je länger Sie lassen sie laufen, desto mehr Chancen Sie für eine optimale Lösung haben (obwohl es keine Garantie).

Da NN schnell ist, gibt es nichts hindert Sie daran, die Techniken zu kombinieren. Run NN eine möglicherweise besser als zufällige Ausgangslösung zu finden. Dann führen Sie diese Lösung in Ihrem genetischen Algorithmus und lassen Sie es so lange laufen, wie Sie für angemessen halten ist.

Wenn Sie in optimalen Lösungen interessiert sind, besuchen Sie das Lin-Kernighan heuristische und Linear Programming . Beide wurden verwendet, um optimale Lösungen für große Touren inklusive dieser Lösung zu finden ein 85.900 Stadtrundfahrt und 24978 Stadt Schweden Tour .

Die Georgia Tech TSP-Website ist eine großartige Ressource.