I made a memetic algorithm in Python for traveling salesman problem. However, all the test data (list of distances between cities) I've encountered lack the information of the best solution, so I can't know how close to global optimum my algorithm gets.
Does anyone know where I can find some tsp test data (preferably in matrix form, but anything's good) with known best solution?
Did you google?
http://www.tsp.gatech.edu/data/index.html
That page provides several test-cases of which 16 has an optimal solution.
也许您可以生成自己的测试数据？
这绝对不会是全面的测试，但它可能会有所帮助。注意：下面是关于汉密尔顿路径的，如果你正在寻找循环，类似的东西会起作用。
您可以执行以下操作：
假设给定一个具有 n 个节点的无向图 G。
您现在创建一个加权图 G'，通过将 G 中的边的权重设置为 1，并添加不在 G 中的边，并给它们一个随机权重 > 1，即 G' 是一个完整的图，其权重分配给所有它的边缘。
现在，如果您在 G' 上运行有效的 TSP 算法并生成大小为 n-1 的路径，则 G 具有哈密顿路径。否则 G 没有哈密顿路径。
所以现在您可以使用您知道的具有/不具有汉密尔顿路径的图（例如：Hypercube具有汉密尔顿路径）并为您的 TSP 算法生成测试数据。
此页面有一些充分条件，可能证明对生成具有汉密尔顿路径的图很有用：http ://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html
我想你不会很难在有/没有汉密尔顿路径的图表上找到数据。
希望能帮助到你。祝你好运！
TSPLIB 是来自各种来源和各种类型的 TSP（和相关问题）的示例实例库。