问题有点陈旧,但问题似乎没有过时或解决,所以我认为我的研究可能对某人有帮助.
至于突变和交叉在TSP问题中是非常微不足道的,其中每个突变都是有效的(因为染色体代表访问固定节点的顺序 - 交换顺序然后始终可以创建有效结果),在最短路径或最优的情况下路径,其中染色体是精确的路线表示,这不适用,并不是那么明显.这就是我如何使用GA解决求解最优路径的问题.
对于交叉,几乎没有选择:
对于至少有一个公共点(除了开始和结束节点)的路由 - 在交叉点找到所有公共点和交换子路由
家长1:
51 33 41 7 12 91 60家长2:
51 9 33 25 12 43 15 60潜在的交叉点是33和12.我们可以得到以下儿童:
51 9 33 41 7 12 43 15 60和51 33 25 12 91 60那些使用这两个交叉点的交叉的结果.当两条路线没有共同点时,从每个父路线中随机选择两个点并连接它们(您可以使用随机遍历,回溯或启发式搜索,如A*或波束搜索).现在可以将此路径视为交叉路径.为了更好地理解,请参见以下两种交叉方法的图片:
见http://i.imgur.com/0gDTNAq.png
黑色和灰色路径是父母,粉色和橙色路径是孩子,绿色点是交叉位置,红色点是开始和结束节点.第一个图表显示第一种类型的交叉,第二个图表是另一个交叉的示例.
对于突变,也有很少的选择.通常,虚拟变异如节点的交换顺序或添加随机节点对于具有平均密度的图实际上是无效的.所以这里有保证有效突变的方法:
从路径中随机取两个点,并用这两个节点之间的随机路径替换它们.
染色体:
51 33 41 7 12 91 60,随机点:33和12,随机/最短路径之间:33 29 71 12,突变染色体:51 33 29 71 12 91 60从路径中找到随机点,删除它并连接它的邻居(真的非常类似于第一个)
从路径中查找随机点并找到其邻居的随机路径
尝试从一些随机选择的点遍历路径,直到到达初始路径上的任何点(稍微修改第一个方法).
见http://i.imgur.com/19mWPes.png
每个图以适当的顺序对应于每个突变方法.在最后一个示例中,橙色路径是将替换突变点(绿色节点)之间的原始路径的路径.
注意:这种方法在这种情况下显然可能存在性能缺陷,当找到替代子路由(使用随机或启发式方法)会卡在某个地方或找到非常长且无用的子路径时,所以考虑限制突变执行的时间或试验数.
对于我的情况,即在最大化顶点权重之和方面找到最佳路径,同时保持节点总和权重小于给定界限,这些方法非常有效并且给出了良好的结果.如果您有任何疑问,请随时提出.对不起我的MS Paint技能;)
更新
一个很大的提示:我在实现中基本上使用了这种方法,但使用随机路径生成有一个很大的缺点.我决定使用最短路径遍历随机选择的点切换到半随机路由生成 - 它更有效(但显然可能不适用于所有问题).
| 归档时间： |
|
| 查看次数： |
1476 次 |
| 最近记录： |