遗传算法 - 交叉和变异算为路径(Genetic Algorithms - Crossover an

我想知道是否有人知道任何直观的交叉和变异算一个图中的路径？ 谢谢！

Answer 1:

问题是有点老了，但似乎问题并没有过时或解决，所以我觉得我的研究仍然可能是别人有帮助的。

至于变异和交叉是在TSP问题，其中每一个突变是有效的用处不大（这是因为染色体代表来访固定节点的顺序 - 交换顺序，然后总是可以创建一个有效的结果），在最短路径或最佳的情况下，路径，其中染色体是准确的路线表示，这并不适用，所以不是很明显。 因此，这里是我如何着手解决在使用GA最优路径的问题。

对于交叉 ，有几个选项：

1. 对于至少有一个共通点（除了开始和结束点）的路线-找到交叉的地方所有的共同点和交换子路径

   父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是同时使用这些交叉点的交叉的结果。

2. 当两个路径没有共通点 ，分别来自父母随机选择两个点并连接（你可以使用，要么随意穿越，回溯或像A *或定向搜索启发式搜索）。 现在，这条路径可以被视为连接路。 为了更好的理解，请参见下面两个交叉方法的画面：

   看到http://i.imgur.com/0gDTNAq.png

   黑色和灰色的路径父母，粉红色和橙色的路径是儿童，绿点是一个交叉的地方，红色的点是起点和终点节点。 第一曲线示出了第一类型的交叉的，第二曲线是例如另外一个。

对于突变 ，也有几个选项。 一般来说，像交换节点的顺序或随机添加节点虚设突变是与平均密度图真的是无效的。 因此，这里是保证有效突变的方法：

1. 从路径随机取两分，并与这两个节点之间的随机路径替换它们。

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

2. 查找路径随机点，清除，并连接邻国（真的非常相似，第一个）

3. 从路径查找随机点，并找到其邻居随机路径

4. 尝试从一些随机选择的点subtraversing路径，直到到达初始路径上的任何点（第一种方法的略微修改）。

   看到http://i.imgur.com/19mWPes.png

   每个图表对应于适当的顺序每个突变方法。 在最后一个例子，橙色的路径是一个将取代突变位点（绿色节点）之间的原始路径。

注意：这个方法显然可以有性能缺陷的情况下，发现当替代subroute（使用随机或启发式方法）将停留在一些地方或找到很长的和无用的子路径，因此考虑边界的突变执行或试验数的时间。

对于我而言，这是发现在同时保持节点重量小于给定的约束和最大化顶点的权重之和方面的最优路径，这些方法是非常有效的，并给予了良好的效果。 如果您有任何问题，随时问。 此外，对不起我的MS油漆技能;）

更新

一个很大的提示：我基本上是用这种方法在我的实现，但有使用随机路径生成的一个大缺点。 我决定用最短路径遍历随机挑选点（一个或多个）切换到半随机路径产生 - 这是很多比较有效（但显然未必适用于所有的问题）。

Answer 2:

EMM ..这是非常难的问题，人们写的是论文，仍然没有正确的答案。

总的原则是“一切都取决于你的域”。

有一些通用的GA库，会做一些对你的工作，但求最佳效果，建议自己实现你的GA操作，专为您的域名。

你可能有更多的运气与答案理论CS ，但你需要扩大你的问题更多，并添加您的任务和域的详细信息。

更新：所以，你有一个曲线图。 在GA而言，通过曲线图中的路径代表一个个体，在路径中的节点将是染色体。 在这种情况下，我会说的突变可表示为地方从原来的路径的偏差 - 节点之一的某处移动，并调整路径，以便在路径的开始和结束的值保持不变。

突变可导致无效的个体。 而在这种情况下，你需要做一个决定：允许无效问卷，并希望他们会收敛一些未开发的解决方案。 或者杀死他们当场。 当我和GA的工作，我也允许无效的解决方案，以适应沿加入“不适运”的价值。 一些研究人员认为这可能与解空间的广泛探索帮助。

交叉只能发生于彼此交叉的路径：在交叉点上的点，交换与父母路径的遗体。

请记住，有对交叉多种方式：个人可以在多个点上交叉记号或者只是一个。 在与图的情况下，你可以有多个交叉点，那自然可以导致多个子图。

正如我之前说的，有这样做的没有正确或错误的方式，但你只能通过实验就可以找出最好的方式。

文章来源: Genetic Algorithms - Crossover and Mutation operators for paths