遗传算法-路径的交叉和变异算子 [英] Genetic Algorithms - Crossover and Mutation operators for paths

问题描述

我想知道是否有人知道图形中路径的直觉交叉和变异运算符?谢谢！

I was wondering if anyone knew any intuitive crossover and mutation operators for paths within a graph? Thanks!

推荐答案

问题有点老了，但是问题似乎并没有过时或无法解决，因此我认为我的研究仍可能对某人有所帮助.

Question is a bit old, but the problem doesn't seem to be outdated or solved, so I think my research still might be helpful for someone.

就TSP问题而言，突变和交叉是非常琐碎的，其中每个突变都是有效的(这是因为染色体代表访问固定节点的顺序-交换顺序之后总能产生有效的结果)，如果是最短的情况路径或最佳路径，其中染色体是精确的路径表示，这并不适用，也不是那么明显.因此，这就是我如何解决使用遗传算法求解最优路径的问题.

As far as mutation and crossover is quite trivial in the TSP problem, where every mutation is valid (that is because chromosome represents an order of visiting fixed nodes - swapping order then always can create a valid result), in case of Shortest Path or Optimal Path, where the chromosome is a exact route representation, this doesn't apply and isn't that obvious. So here is how I approach problem of solving Optimal Path using GA.

对于跨界，很少有选择:

1. 对于具有至少一个公共点(在起始和结束节点之外)的路线-查找所有公共点并在交叉处交换子路线

1. For routes that have at least one common point (besides start and end node) - find all common points and swap subroutes in the place of crossing

父母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，它们是使用这两个交叉点进行交叉的结果.

Potential crossing point are 33 and 12. We can get following children: 51 9 33 41 7 12 43 15 60 and 51 33 25 12 91 60 that are the result of crossing using both of these crossing points.

当两条路线没有公共点时，请从每个父级中随机选择两个点并将其连接起来(您可以用于随机遍历，回溯或启发式搜索(例如A *)或光束搜索).现在，可以将此路径视为交叉路径.为了更好地理解，请参见下面两种交叉方法的图片:

When two routes don't have common point, select randomly two points from each parent and connect them (you can use for that either random traversal, backtracking or heuristic search like A* or beam search). Now this path may be treated as crossover path. For better understanding, see below picture of two crossover methods:

请参见 http://i.imgur.com/0gDTNAq.png

黑色和灰色路径为父路径，粉红色和橙色路径为父路径 孩子们，绿点是一个交叉的地方，红点是开始 和末端节点.第一个图显示了第一种交叉类型，第二个图是另一个交叉的示例.

Black and gray paths are parents, pink and orange paths are children, green point is a crossover place, and red points are start and end nodes. First graph shows first type of crossover, second graph is example of another one.

对于变异，也很少有选择.通常，虚拟突变(例如交换节点的顺序或添加随机节点)对于具有平均密度的图而言实际上是无效的.因此，以下是保证有效突变的方法:

For mutation, there are also few options. Generally, dummy mutation like swapping order of nodes or adding random node is really ineffective for graphs with average density. So here are the approaches that guarantee valid mutations:

1. 从路径中随机获取两个点，并用这两个节点之间的随机路径替换它们.

1. Take randomly two points from path and replace them with a random path between those two nodes.

染色体:51 33 41 7 12 91 60，随机点: 33 和 12 ，其间的随机/最短路径:33 29 71 12，突变的染色体:51 33 29 71 12 91 60

Chromosome: 51 33 41 7 12 91 60 , random points: 33 and 12, random/shortest path between then: 33 29 71 12, mutated chromosome: 51 33 29 71 12 91 60

从路径中找到随机点，将其删除并连接其邻居(与第一个非常相似)

Find random point from path, remove it and connect its neighbours (really very similar to the first one)

从路径中找到随机点，并找到到其邻居的随机路径

Find random point from path and find random path to its neighbour

尝试从某个随机选择的点开始遍历路径，直到到达初始路线上的任意点为止(第一种方法的稍作修改).

Try subtraversing the path from some randomly chosen point, until reaching any point on the initial route (slight modification of the first method).

请参见 http://i.imgur.com/19mWPes.png

每个图以适当的顺序对应于每种突变方法.在最后一个示例中，橙色路径是替换突变点(绿色节点)之间的原始路径的路径.

Each graph corresponds to each mutation method in appropriate order. In last example, the orange path is the one that would replace original path between mutation points (green nodes).

注意:在以下情况下，这种方法显然可能会带来性能缺陷:当找到替代子路由(使用随机或启发式方法)会停留在某个地方或找到很长且无用的子路径时，请考虑限制执行突变或试验次数的时间.

Note: this methods obviously may have performance drawback in the case, when finding alternative subroute (using a random or heuristic method) will stuck at some place or find very long and useless subpath, so consider bounding the time of mutation execution or trials number.

对于我来说，这是在最大化顶点权重总和的同时保持节点权重总和小于给定范围的最佳路径，这些方法非常有效并且给出了很好的结果.如有任何疑问，请随时提问.另外，对我的MS Paint技术很抱歉；)

For my case, which is finding an optimal path in terms of maximizing sum of vertices weights while keeping sum of nodes weight less than given bound, those methods are quite effective and give a good result. Should you have any question, feel free to ask. Also, sorry for my MS Paint skills ;)

更新

一个重要提示:我基本上在实现中使用了这种方法，但是使用随机路径生成存在一个很大的缺点.我决定使用最短路径遍历随机选取的点来切换为半随机路由生成-这样效率更高(但显然可能不适用于所有问题).

One big hint: I basically used this approach in my implementation, but there was one big drawback of using random path generating. I decided to switch to semi-random route generation using shortest path traversing randomly picked point(s) - it is much more efficent (but obviously may not be applicable for all problems).

这篇关于遗传算法-路径的交叉和变异算子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！