一个关于应用遗传算法解决旅行商问题的详细问题

Question

5

我阅读了很多相关文章并理解了其原理和概念，然而，没有一篇论文提到如何计算包含未直接相连节点(在图中)的染色体(代表路径)适应度的细节。

例如，给定一个染色体1|3|2|8|4|5|6|7，在其中每个基因代表图/地图上城市的索引时，如果说城市2和8之间没有直接的边缘连接，我们该如何计算其适应度(即所行驶路程的总和)。我们是否要遵循某种贪婪算法来计算2和8之间的路径，并将该路径的距离加入到总路程中呢？

当应用GA到TSP时，这个问题似乎非常普遍。任何做过的人都可以分享你的经验。谢谢。

- Simon Hughes

1

正如@kibibu所说，您永远不应该能够生成无效的染色体。这适用于任何遗传算法实现。 - Kevin Crowell

3个回答

1

这正是问题的本质，为解决TSP问题，专门的交叉和变异方法已被应用于基于GA的解决方案。请参见此链接。

- user59634

1

如果染色体不代表有效解决方案，那么它完全不适合解决问题。因此，根据您如何排序适应度。例如，如果较低的数字表示更高的适应度（当适应度表示总成本时可能是一个好主意），则您将为其分配最大值，并在到达无效基因序列时中断任何进一步的适应度计算。

（反之亦然，如果更高的适应度意味着染色体更适合工作，则将其分配为零的适应度）

但是，正如其他人指出的那样，确保无效的染色体不会发生可能更好。但是，如果这本身就是一个过于复杂的过程，那么允许它们并确保破碎的染色体不太可能进入后续世代可能是可接受的方法。

- Paul

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kibibu · Accepted Answer

如果您的图表中2和8之间没有链接，则任何染色体中带有2|8或8|2的都是无效的，对于经典旅行商问题而言。如果您找到2和8之间的其他路径，则可能会违反“每个位置只访问一次”的要求。

一个非常不可靠但实用的解决方案是在这些节点之间包含具有极高距离甚至+INF（如果您的语言支持）的边缘。这样，您的标准最小化适应度函数自然会将它们修剪掉。

我认为问题的原始公式包括所有节点之间的边缘，因此这不是问题。