遗传算法 - 路径的交叉和变异运算符

Question

我想知道是否有人知道任何直观的交叉和变异操作符在图中的路径？谢谢！

Answer 1

嗯..这是一个非常困难的问题，人们为此写论文，但仍然没有正确的答案。

一般规则是“这一切都取决于你的域名”。

有一些通用GA库会为您做一些工作，但为了获得最佳效果，建议您自己实施GA操作，特别是针对您的域。

您可能在Theoretical CS上有更多回答，但您需要更多地扩展您的问题并添加有关您的任务和域的更多详细信息。

更新： 所以你有一个图。在GA术语中，通过图的路径表示个体，路径中的节点将是染色体。 在这种情况下，我会说突变可以表示为与原始位置之间的路径偏差 - 其中一个节点将移动到某处，并调整路径以使路径中的开始值和结束值保持不变。

突变可能会导致无效的个人。在这种情况下，您需要做出决定：允许无效的决策，并希望它们能够融合到一些尚未解决的解决方案中。或者当场杀死他们。当我和GA一起工作时，我确实允许使用无效解决方案，并在健身方面增加“不适合”值。一些研究人员认为这可以帮助广泛探索解决方案空间。

交叉只能发生在彼此交叉的路径上：在交叉点上，将路径的剩余部分与父母交换。

请记住，交叉有多种方式：个人可以交叉在多个点或只在一个。在图形的情况下，您可以有多个交叉点，并且这自然会导致多个子图。

正如我之前所说，这样做没有对错的方法，但只有通过试验才能找到最好的方法。

Answer 2

问题有点老，但问题似乎并没有过时或解决，所以我认为我的研究仍然可能对某人有所帮助。在TSP问题中，每个突变都是有效的（这是因为染色体代表访问固定节点的顺序 - 交换顺序，然后始终可以创建有效结果），但在TSP问题中相当微不足道最短路径或最佳路径，其中染色体是精确的路径表示，这不适用，并不明显。所以这里是我如何处理使用遗传算法求解最优路径的问题。

对于交叉，有几个选项：

1. 对于有至少一个公共点路线（除了开始和结束点） - 发现在这个地方所有共同点和交换子路径交叉

   的

   父1：51 33 41 7 12 91 60

   父2：51 9 33 25 12 43 15 60

   潜在过境点为和。我们可以得到以下儿童：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 29 71 12，突变的染色体：51 33 29 71 12 91 60

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

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

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

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

   每个图表对应于适当的顺序每个突变方法。在上一个例子中，橙色路径是替换突变点（绿色节点）之间的原始路径的路径。

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

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

更新

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