遗传算法 - 旅行商

Question

我经历过去的试卷，我想了解以下问题：

假设你有N个城市。从每个城市到其他任何城市都是可能的。假设你有一个表格形式的城市之间的距离的完整信息。城市号码k与城市号码l之间的距离由d（k，l）给出;例如，从第三城市到第九城市的距离由d（3,9）给出。请注意，d（k，l）= d（l，k）。

旅行商需要访问所有N个城市，并希望找到连接所有城市的最短路线。使用遗传算法来解决这个问题。

问题：为这个问题定义一个合适的适应度函数 并且说是高或低适合度更好。

有没有人知道我需要为这个问题做什么？我真的很难从哪里开始，需要一些方向。

Answer 1

随着TSP你想尽量减少行驶距离。有很多不同的方式可以在城市旅行;准确地说是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] 

This video显示了Javascript实现通过遗传算法优化的距离的一个很好的例子。