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

例如,给定一个染色体1 | 3 | 2 | 8 | 4 | 5 | 6 | 7,其中每个基因代表图表/地图上城市的索引,我们如何计算其适应性(即总和距离旅行)如果说城市2和8之间没有直接边缘/连接。我们是否遵循某种贪婪的算法来制定2和8之间的路线,并将此路线的距离添加到总数?

将GA应用于TSP时,这个问题似乎很普遍。任何在此之前做过的人,请分享您的经验。谢谢。

有帮助吗?

解决方案

如果图表上的2和8之间没有链接,则任何具有2 | 8或8 | 2的染色体是无效的 对于古典旅行推销员问题. 。如果您在2和8之间找到其他路线,则可能会违反“一次访问每个位置”的要求。

一个真正狡猾但弹药的解决方案是在具有难以置信的高距离的那些节点之间包括边缘,如果您的语言支持它,则包括 + +INF。这样,您的标准适应性功能自然会修剪它们。

我认为该问题的原始表述包括所有节点之间的边缘,因此这是一个非问题。

其他提示

这是确切的问题,专门的交叉和突变方法已用于基于GA的解决方案,以解决TSP问题。看到这个 问题.

如果染色管不代表有效的解决方案,则完全不适合解决问题。因此,取决于您的订购方式。即,如果较低的数字代表更多的健身(当健身代表总成本时可能是一个好主意),那么当您进入无效的基因序列时,您将为它分配一个最大值并打破该铬酮上的任何进一步的健身计算。

(反之亦然,如果较高的健身意味着染色体更适合该工作,则将其分配为零)

但是,正如其他人指出的那样,最好确保不会发生无效的染色体。但是,如果这本身就是一个过度的Compex过程,那么允许它们并确保损坏的染色剂不太可能将其分为连续的世代,这可能是一种可以接受的方法。

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top