Sim*_*hes 5 traveling-salesman genetic-algorithm
我阅读了有关这方面的各种内容并理解了所涉及的原理和概念,然而,没有一篇论文提到如何计算染色体(代表一条路线)的适应性的细节,该染色体涉及相邻的城市(在染色体中)没有直接连接通过边缘(在图中).
例如,给定染色体1 | 3 | 2 | 8 | 4 | 5 | 6 | 7,其中每个基因代表图/地图上的城市指数,我们如何计算其适应度(即(例如,在城市2和8之间没有直接边缘/链接).我们是否遵循某种贪婪算法来计算出2到8之间的路线,并将此路线的距离加到总数上？
将GA应用于TSP时,这个问题似乎很常见.任何以前做过的人请分享您的经验.谢谢.
如果图表中2和8之间没有链接,那么任何具有2 | 8或8 | 2的染色体对于经典旅行商问题都是无效的.如果您发现2到8之间的其他路线,您可能会违反"访问每个位置一次"的要求.
一个非常狡猾但实用的解决方案是在这些具有令人难以置信的高距离的节点之间包含边缘,如果您的语言支持它,甚至可以包括+ INF.这样,您的标准最小化适应度函数将自然地修剪它们.
我认为问题的原始公式包括所有节点之间的边缘,因此这不是问题.