3

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

4

2 回答 2

7

问题有点老了，但问题似乎并没有过时或解决，所以我认为我的研究仍然可能对某人有所帮助。

就 TSP 问题中的变异和交叉而言，每个变异都是有效的（这是因为染色体代表访问固定节点的顺序 - 交换顺序总是可以产生有效的结果），在最短路径或最优的情况下路径，其中染色体是精确的路径表示，这不适用并且不是那么明显。所以这就是我如何使用 GA 解决最优路径的问题。

对于crossover，有几个选项：

  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 图像

    黑色和灰色的路径是父母，粉红色和橙色的路径是孩子，绿色点是交叉点，红色点是起点和终点节点。第一张图显示了第一种类型的交叉，第二张图是另一个示例。

对于mutation，也有很少的选择。通常，像交换节点顺序或添加随机节点这样的虚拟突变对于平均密度的图实际上是无效的。因此，以下是保证有效突变的方法：

  1. 从路径中随机抽取两个点，并将它们替换为这两个节点之间的随机路径。

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

  2. 从路径中找到随机点，将其移除并连接其邻居（与第一个非常相似）

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

  4. 尝试从某个随机选择的点开始遍历路径，直到到达初始路线上的任何点（对第一种方法稍作修改）。

    见http://i.imgur.com/19mWPes.png 在此处输入图像描述

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

注意：这种方法显然在这种情况下可能存在性能缺陷，当寻找替代子路径（使用随机或启发式方法）时会卡在某个地方或找到非常长且无用的子路径，因此请考虑限制突变执行时间或试验次数。

对于我的情况，即在最大化顶点权重总和同时保持节点权重总和小于给定界限的情况下找到最佳路径，这些方法非常有效并且给出了良好的结果。如果您有任何问题，请随时提问。另外，对不起我的 MS Paint 技能；）

更新

一个重要提示：我在实现中基本上使用了这种方法，但是使用随机路径生成有一个很大的缺点。我决定使用遍历随机选取点的最短路径切换到半随机路由生成——它更有效（但显然可能不适用于所有问题）。

于 2014-04-13T11:58:12.777 回答
3

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

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

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

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

更新： 所以你有一个图表。在 GA 术语中，通过图的路径代表一个个体，路径中的节点将是染色体。在那种情况下，我会说突变可以表示为路径与原始路径的偏差——其中一个节点被移动到某处，并且路径被调整，因此路径中的起始值和结束值保持不变。

突变可导致无效个体。在这种情况下，您需要做出决定：允许无效的，并希望它们会收敛到一些未经探索的解决方案。或者当场杀死他们。当我与 GA 合作时，我确实允许无效的解决方案，将“不适合”值与适合度一起添加。一些研究人员认为这有助于广泛探索解决方案空间。

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

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

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

于 2012-10-02T09:46:51.063 回答