我想知道是否有人知道图形中路径的任何直观的交叉和变异算子?谢谢!
最佳答案
问题有点老,但问题似乎并没有过时或解决,所以我认为我的研究仍然可能对某人有所帮助。
至于突变和交叉在 TSP 问题中是非常微不足道的,在最短路径或最优的情况下,每个突变都是有效的(这是因为染色体代表访问固定节点的顺序 - 交换顺序总是可以创建有效结果) Path,其中染色体是精确的路线表示,这不适用,也不那么明显。所以这就是我如何解决使用 GA 解决最佳路径的问题。
对于 交叉 ,有几个选项:
父级 1:
51 33 41 7 12 91 60
父 2:
51 9 33 25 12 43 15 60
潜在的交叉点是 33 和 12 。我们可以得到以下 child :
51 9 33 41 7 12 43 15 60
和 51 33 25 12 91 60
,它们是使用这两个交叉点交叉的结果。 对于 突变 ,也有几个选项。一般来说,像交换节点顺序或添加随机节点这样的虚拟变异对于具有平均密度的图来说确实是无效的。所以这里是保证有效突变的方法:
染色体:
51 33 41 7 12 91 60
,随机点: 33 和 12 ,然后之间的随机/最短路径: 33 29 71 12
,变异染色体: 51 33 29 71 12 91 60
注意: 这种方法在这种情况下显然可能有性能缺陷,当寻找替代子路由时(使用随机或启发式方法)会卡在某个地方或找到很长且无用的子路径,因此请考虑限制突变执行或试验的时间数字。
对于我的情况,即在最大化顶点权重总和同时保持节点权重小于给定界限方面找到最佳路径,这些方法非常有效并给出了很好的结果。如果您有任何问题,请随时提出。另外,对不起我的 MS Paint 技能;)
更新
一个重要提示:我在我的实现中基本上使用了这种方法,但是使用随机路径生成有一个很大的缺点。我决定使用最短路径遍历随机选取的点切换到半随机路线生成 - 它更有效(但显然可能不适用于所有问题)。
关于path - 遗传算法 - 路径的交叉和变异算子,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/12687963/