我想知道是否有人知道图形中路径的任何直观的交叉和变异算子?谢谢!

最佳答案

问题有点老,但问题似乎并没有过时或解决,所以我认为我的研究仍然可能对某人有所帮助。

至于突变和交叉在 TSP 问题中是非常微不足道的,在最短路径或最优的情况下,每个突变都是有效的(这是因为染色体代表访问固定节点的顺序 - 交换顺序总是可以创建有效结果) Path,其中染色体是精确的路线表示,这不适用,也不那么明显。所以这就是我如何解决使用 GA 解决最佳路径的问题。

对于 交叉 ,有几个选项:

  • 对于具有 至少一个公共(public) 点(除了起点和终点节点)的路线 - 在交叉点找到所有公共(public)点并交换子路线

    父级 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 6051 33 25 12 91 60,它们是使用这两个交叉点交叉的结果。
  • 当两条路线 没有公共(public)点 时,从每个父节点中随机选择两个点并将它们连接起来(您可以使用随机遍历、回溯或启发式搜索,如 A* 或波束搜索)。现在这条路径可以被视为交叉路径。为了更好地理解,请参见下图两种交叉方法:


  • 对于 突变 ,也有几个选项。一般来说,像交换节点顺序或添加随机节点这样的虚拟变异对于具有平均密度的图来说确实是无效的。所以这里是保证有效突变的方法:
  • 从路径中随机取两个点并用这两个节点之间的随机路径替换它们。

    染色体: 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/

    10-14 19:44
    查看更多