遗传算法应用于旅行商的一个细节问题
我阅读了有关这方面的各种内容并了解所涉及的原理和概念，但是没有一篇论文提到如何计算涉及不直接连接的相邻城市（在染色体中）的染色体（代表一条路线）的适应度的细节通过一条边（在图中）。
例如，给定一条染色体 1|3|2|8|4|5|6|7，其中每个基因代表图形/地图上一个城市的索引，我们如何计算它的适应度（即行驶距离）如果城市 2 和 8 之间没有直接的边缘/链接。我们是否遵循某种贪婪算法来计算 2 和 8 之间的路线，并将该路线的距离添加到总距离中？
当将 GA 应用于 TSP 时，这个问题似乎很常见。有做过的朋友请分享一下经验。谢谢。
I read various stuff on this and understand the principle and concepts involved, however, none of paper mentions the details of how to calculate the fitness of a chromosome (which represents a route) involving adjacent cities (in the chromosome) that are not directly connected by an edge (in the graph).
For example, given a chromosome 1|3|2|8|4|5|6|7, in which each gene represents the index of a city on the graph/map, how do we calculate its fitness (i.e. the total sum of distances traveled) if, say, there is no direct edge/link between city 2 and 8. Do we follow some sort of greedy algorithm to work out a route between 2 and 8, and add the distance of this route to the total?
This problem seems pretty common when applying GA to TSP. Anyone who's done it before please share your experience. Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果图表中 2 和 8 之间没有联系，则任何包含 2|8 或 8|2 的染色体对于经典旅行商问题都是无效的。如果您发现 2 到 8 之间的其他路线，您可能会违反“每个位置访问一次”的要求。
一种真正狡猾但实用的解决方案是在那些距离非常远的节点之间包含边，甚至+INF（如果您的语言支持的话）。这样，您的标准最小化适应度函数就会自然地修剪它们。
我认为问题的原始表述包括所有节点之间的边，所以这不是问题。
If there is no link between 2 and 8 on your graph, then any chromosome with 2|8 or 8|2 in it is invalid for the classical travelling salesman problem. If you find some other route between 2 and 8, you are probably going to violate the "visit each location once" requirement.
One really dodgy-but-pragmatic solution is to include edges between those nodes with incredibly high distances, or even +INF if your language supports it. That way, your standard minimizing fitness function will naturally prune them.
I think the original formulation of the problem includes edges between all nodes, so this is a non-issue.
这就是确切的问题类型，专门的交叉和变异方法已应用于基于 GA 的 TSP 问题解决方案。请参阅此问题。
This is the exact kind of problem, specialized Crossover and mutation methods have been applied for GA based solutions to TSP problems. See this question.
如果色酮不代表有效的解决方案，那么它完全不适合解决该问题。所以取决于你如何订购健身。即，如果较低的数字代表更高的适应度（当适应度代表总成本时，这可能是一个好主意），那么您可以为其分配一个最大值，并在到达无效的基因序列时中断对该染色体的任何进一步的适应度计算。
（反之亦然，如果较高的适应度意味着染色体更适合该工作，则将其分配为零）
但是，正如其他人指出的那样，最好确保不会发生无效的染色体。然而，如果这本身就是一个过于复杂的过程，那么允许它们并确保断裂的发色酮不太可能进入连续的世代可能是一种可以接受的方法。
if the chromosone does not represent a valid solution then it is completly unfit to solve the problem. So depending on how you order fitness. ie if a lower number represents more fitness (possibly a good idea when fitness represents total cost) then you'd assign it a max value and break any further fitness calculation on that chromosone when you get to a gene sequence that is invalid.
(or vice versa, assign it a fitness of zero if a higher fitness means a chromosone is more fit for the job)
however as others have pointed out it could be better to ensure that invalid chromosones dont occur. However if that is itself an overly compex process then allowing them and ensuring that broken chromosones are unlikely to make it into successive generations could be an acceptable approach.