遗传算法 - 旅行商
问题描述:
我经历过去的试卷,我想了解以下问题:遗传算法 - 旅行商
假设你有N个城市。从每个城市到其他任何城市都是可能的。假设你有一个表格形式的城市之间的距离的完整信息。城市号码k与城市号码l之间的距离由d(k,l)给出;例如,从第三城市到第九城市的距离由d(3,9)给出。请注意,d(k,l)= d(l,k)。
旅行商需要访问所有N个城市,并希望找到连接所有城市的最短路线。使用遗传算法来解决这个问题。
问题:为这个问题定义一个合适的适应度函数 并且说是高或低适合度更好。
有没有人知道我需要为这个问题做什么?我真的很难从哪里开始,需要一些方向。
答
你可以通过创建一个交换两个城市在列表例如突变功能做到这一点:
随着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实现通过遗传算法优化的距离的一个很好的例子。
非常感谢您的帮助! – 7389573987