我想知道是否有人知道图中路径的直观交叉和变异运算符?谢谢!
问题有点老了,但问题似乎没有过时或解决,所以我认为我的研究仍然可能对某人有帮助。
就 TSP 问题而言,突变和交叉是相当微不足道的,在最短路径或最优的情况下,每个突变都是有效的(即因为染色体代表访问固定节点的顺序 - 交换顺序总是可以创建有效的结果)路径,其中染色体是精确的路径表示,这不适用并且不是那么明显。以下是我如何使用遗传算法解决最佳路径问题。
For 交叉,有几个选项:
-
对于有至少有一个共同点点(除了开始和结束节点) - 找到所有公共点并在交叉点交换子路线
家长 1:51 33 41 7 12 91 60
家长2:51 9 33 25 12 43 15 60
潜在的交叉点是33 and 12。我们可以得到以下孩子:51 9 33 41 7 12 43 15 60
and 51 33 25 12 91 60
这是使用这两个交叉点进行交叉的结果。
-
当两条路线没有共同点,从每个父点中随机选择两个点并将它们连接起来(您可以使用随机遍历、回溯或启发式搜索,如 A* 或波束搜索)。现在这条路径可以被视为交叉路径。为了更好地理解,请参见下图两种交叉方法:
see https://i.stack.imgur.com/BPjyf.png https://i.stack.imgur.com/BPjyf.png
黑色和灰色路径是父路径,粉色和橙色路径是
小朋友们,绿点是交叉点,红点是起点
和结束节点。第一张图显示了第一种交叉类型,第二张图是另一种类型的示例。
For mutation,选项也很少。一般来说,交换节点顺序或添加随机节点等虚拟突变对于平均密度的图来说实际上是无效的。因此,以下是保证有效突变的方法:
-
从路径中随机取出两个点,并将它们替换为这两个节点之间的随机路径。
染色体:51 33 41 7 12 91 60
,随机点:33 and 12,然后之间的随机/最短路径:33 29 71 12
,突变染色体:51 33 29 71 12 91 60
从路径中找到随机点,将其删除并连接其邻居(与第一个非常相似)
从路径中找到随机点并找到到其邻居的随机路径
-
尝试从某个随机选择的点开始遍历路径,直到到达初始路线上的任何点(对第一种方法稍作修改)。
see https://i.stack.imgur.com/nbrQ5.png https://i.stack.imgur.com/nbrQ5.png
每个图以适当的顺序对应于每个突变方法。在上一个示例中,橙色路径将替换突变点(绿色节点)之间的原始路径。
Note:这种方法显然可能在这种情况下存在性能缺陷,当寻找替代子路径(使用随机或启发式方法)时会卡在某个地方或找到非常长且无用的子路径,因此请考虑限制突变执行时间或试验次数。
对于我的情况,即寻找一条最大化顶点权重总和同时保持节点权重总和小于给定界限的最佳路径,这些方法非常有效并且给出了良好的结果。如果您有任何疑问,请随时提问。另外,对我的 MS Paint 技能感到抱歉;)
Update
一个重要提示:我在实现中基本上使用了这种方法,但是使用随机路径生成有一个很大的缺点。我决定切换到使用最短路径遍历随机选取点的半随机路线生成 - 它更有效(但显然可能不适用于所有问题)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)