具有已知全局最優化的旅行推銷員示例

Question

我爲traveling salesman problem在Python中製作了一個memetic算法。然而，我遇到的所有測試數據（城市之間的距離列表）都缺少最佳解決方案的信息，所以我無法知道我的算法得到的全局最優值有多接近。

有沒有人知道在哪裏可以找到一些tsp測試數據（最好是矩陣形式，但任何東西都很好）與已知的最佳解決方案？

Answer 1

你谷歌嗎？

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

該網頁提供了幾個試驗例，其中16具有最佳的解決方案。

Answer 2

也許你可以生成自己的測試數據？

這絕對不會是全面的測試，但它可能會有所幫助。注意：下面是關於哈密爾頓路徑，如果你正在尋找週期，類似的東西會起作用。

你可以做到以下幾點：

說你將得到一個無向圖G有n個節點。

您現在通過將G中邊的權重設置爲1並添加不在G中的邊並給它們一個隨機權重> 1來創建加權圖G'，即G'是一個完整圖分配給所有邊的權重。

現在，如果你在G'上運行一個有效的TSP算法，並且它生成一個大小爲n-1的路徑，那麼G就有一個哈密爾頓路徑。否則G沒有哈密爾頓路徑。

所以，現在你可以使用你的圖表知道有/沒有哈密爾頓路徑（e.g：Hypercube有漢彌爾頓路徑），並生成測試數據的TSP算法。

這個頁面有一些充分條件可能生成具有漢彌爾頓路徑曲線證明是有用的：http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html

我想你不會有很難找到與/圖表數據，而漢彌爾頓路徑。

希望它有幫助。祝你好運！

Answer 3

TSPLIB是來自各種來源和各種類型的TSP（以及相關問題）的示例實例庫。

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