旅行推銷員 - 最近鄰對遺傳DEATHMATCH

Question

在過去的幾天裏，我注意到幾個websites，證明了使用遺傳算法的TS解決方案。

我在尋找你的意見，這對於這個特殊問題更好。

Heuristics vs Genetic。

更好的是，我的意思是會產生一個更短/更低的成本路徑。

解釋爲什麼你覺得你的方式。

歡迎舉例和非現場鏈接。

Answer 1

由於這兩種技術都不能保證最佳解決方案，因此您的里程將有所不同。有一點運氣，任何一種技術都可以超越其他技術。這兩種技術都有優點和缺點。

近鄰：+快速+簡單， - 通常不是最佳

遺傳算法：-slower， - 更復雜，解決方案+對趨勢的最佳隨着時間的推移

的最大區別在於，隨機算法，如隨着時間的推移，遺傳算法可能會持續改進 - 您讓它們運行的​​時間越長，獲得最佳解決方案的機會就越多（儘管沒有保證）。

由於神經網絡速度很快，所以沒有什麼能夠阻止您將這些技術結合在一起。運行NN找到一個可能的好於隨機的開始解決方案。然後，將該解決方案輸入到您的遺傳算法中，只要您認爲合適就讓它運行。

如果您對最佳解決方案感興趣，請查看Lin-Kernighan heuristic和Linear Programming。兩者都用於爲大型旅遊尋找最佳解決方案，包括this solution，85,900 city tour和24,978 city Sweden tour。

Georgia Tech TSP site是一個很好的資源。