遗传算法-旅行推销员

Question

我正在复习一篇过去的试卷，我试着理解以下问题：

假设你有N个城市。从每个城市到其他任何一个城市都是可能的。假设您以表格形式提供了有关城市之间距离的完整信息。城市数k和城市数l之间的距离由d(k，l)表示；例如，从第三城市到第九城市的距离是d(3,9)。注意，d(k，l)=d(l，k)。 旅行推销员需要访问所有N个城市，并希望找到连接所有城市的最短路线。用遗传算法解决这个问题。 问题:为这个问题定义一个合适的健身功能，并说明高健康还是低健康更好。

有人知道我该怎么回答这个问题吗？我真的很纠结于从哪里开始，需要一些方向。

Answer 1

使用TSP，您希望将旅行的距离降到最小。n城市有许多不同的旅行方式；确切地说，是N! / 2。

因此，如果您有N = 4，则需要一个整数1-4数组，每个数组只出现一次。因此，一些可能的选择是：

[1,4,2,3]
[4,1,2,3]
[3,1,4,2]

然后通过从城市i到列表中的i+1来评估分数，计算距离。对列表中的每一个城市i这样做(但最后一次)，你就有了总距离；这就是你的分数！

因此，对于上面的例子，分数应该是：

// Please note that the integers 1-4 represent cities
score([1,4,2,3]) = d(1,4) + d(4,2) + d(2,3)
score([4,1,2,3]) = d(4,1) + d(1,2) + d(2,3)
score([3,1,4,2]) = d(3,1) + d(1,4) + d(4,2)

你想把距离降到最小，从而把分数降到最低。

​

可以通过创建替换列表中的两个城市的突变函数来做到这一点，例如：

​

[1,4,2,3] -> [4,1,2,3]
[1,2,3,4] -> [1,3,2,4]

这段视频展示了通过遗传算法优化距离的Javascript实现的一个很好的例子。