genetic-algorithm - 遗传算法应用于旅行商的一个细节问题

Question

我阅读了有关此的各种内容并了解所涉及的原理和概念，但是，没有一篇论文提到如何计算涉及未直接连接的相邻城市(在染色体中)的染色体(代表一条路线)的适应度的细节通过一条边(在图中)。

例如，给定一条染色体 1|3|2|8|4|5|6|7，其中每个基因代表一个城市在图/ map 上的索引，我们如何计算它的适应度(即总和行进的距离)如果，比如说，在城市 2 和 8 之间没有直接的边缘/链接。我们是否遵循某种贪婪算法来计算出 2 和 8 之间的路线，并将这条路线的距离加到总和中？

在将 GA 应用于 TSP 时，这个问题似乎很常见。有做过的 friend 分享一下经验吧。谢谢。

Answer 1

如果图表上的 2 和 8 之间没有联系，那么任何包含 2|8 或 8|2 的染色体对于经典的旅行商问题都是无效的。如果您发现 2 和 8 之间的其他路线，您可能会违反“访问每个位置一次”的要求。

一种非常狡猾但实用的解决方案是在那些距离非常远的节点之间包含边，如果您的语言支持，甚至可以包含 +INF。这样，您的标准最小化适应度函数将自然地修剪它们。

我认为问题的原始表述包括所有节点之间的边，所以这不是问题。