1

为什么具体使用它？

我知道它会增加变化，这可能有助于探索问题空间，但它会增加多少及时找到最佳解决方案/配置的概率？它还有其他好处吗？

它是否一定总是有帮助，或者是否存在会增加找到最佳解决方案所需时间的情况？

4

1 回答 1

3

正如帕特里克·特伦丁所说，交叉提高了收敛速度，因为它允许结合已经在人群中发现的好基因。

但是，对于神经进化而言，交叉面临着“排列问题”，也称为“竞争约定问题”。当两个父母是同一个网络的排列时，除了极少数情况外，他们的后代总是有较低的适应度。因为网络的同一部分被复制到两个不同的位置，所以后代正在失去这两个位置之一的可行基因。

例如网络 A,B,C,D 和 D,C,B,A 是同一网络的排列。后代可以是：

A,B,C,D (copy of parent 1)           
D,C,B,A (copy of parent 2)

A,C,B,D OK
A,B,C,A
A,B,B,A 
A,B,B,D
A,C,B,A
A,C,C,A
A,C,C,D

D,B,C,A OK
D,C,B,D
D,B,B,A 
D,B,B,D
D,B,C,D
D,C,C,A
D,C,C,D

所以，对于这个例子，2/16 的后代是父母的副本。2/16 是没有重复的组合。12/16 有重复的基因。

出现排列问题的原因是，作为排列之一的网络具有相同的适应度。因此，即使对于精英 GA，如果一个被选为父代，另一个也经常被选为父代。

排列可能只是部分的。在这种情况下，结果比完全排列要好，但在很多情况下，后代的适应度仍然低于父母。

为了避免排列问题，我听说过基于相似性的交叉，它计算神经元及其连接突触的相似性，在最相似的神经元之间进行交叉，而不是基于轨迹的交叉。

在演化网络拓扑时，一些 NEAT 专家认为排列问题是更广泛问题的一部分：“可变长度基因组问题”。而 NEAT 似乎通过网络的形态来避免这个问题，当两个网络在拓扑和权重上相差太大时，它们就不允许交配。因此，NEAT 算法似乎认为置换网络过于不同，并且不允许它们交配。

一个关于 NEAT 的网站还说：

然而，在另一种意义上，人们可以说可变长度基因组问题永远无法“解决”，因为它是任何系统所固有的，它产生了解决同一问题的不同结构。例如，鸟和蝙蝠都代表飞行问题的解决方案，但它们是不兼容的，因为它们是做同一件事的不同约定。同样的情况也可能发生在 NEAT 中，其中可能会出现非常不同的结构来做同样的事情。当然，这样的结构不会交配，避免了后代受损的严重后果。尽管如此，可以说，由于不同的表示可以同时存在，不兼容的基因组仍然存在，因此问题没有“解决”。归根结底，问题是否得到解决是主观的。这取决于您会考虑什么解决方案。但是，至少可以说“避免了可变长度基因组的问题”是正确的。

编辑：回答您的评论。

您可能适合基于相似性的交叉，我不确定它是否完全避免了排列问题。

关于交叉的最终目标，不考虑置换问题，我不确定它对神经网络的进化是否有用，但我的想法是：如果我们将一个神经网络分成几个部分，每个部分都有助于适应度，所以两个具有高适应度的网络可能有不同的好的部分。结合这些部分应该会创建一个更好的网络。一些后代当然会继承坏的部分，但其他一些后代会继承好的部分。

就像 Ray 所建议的那样，在有和没有交叉的情况下试验神经网络的进化可能是有用的。由于进化存在随机性，因此问题在于运行大量测试，以计算平均进化速度。

关于进化神经网络以外的东西，我发现一篇论文说使用交叉的算法在解决全对最短路径问题 (APSP) 方面优于仅突变算法。

编辑2：

即使排列问题似乎只适用于某些特定问题，如神经进化，我认为我们不能对交叉说同样的话，因为也许我们遗漏了一些似乎不适合的问题交叉。

我找到了一篇关于基于相似性的神经进化交叉的论文的免费版本，它表明：

  • 使用朴素交叉的算法比仅突变算法的性能更差。

  • 使用基于相似性的交叉，它对所有测试用例的性能都优于仅突变算法。

  • NEAT 算法有时比仅突变算法执行得更好。

交叉是复杂的，我认为缺乏将其与仅突变算法进行比较的研究，可能是因为它的有用性高度取决于：

  • 它的工程，在特定问题的函数中，如排列问题。所以我们使用的交叉类型（基于相似性、单点、均匀、边缘重组等）。

  • 以及交配算法。例如，本文表明性别遗传算法在解决 TSP 问题上明显优于非性别遗传算法。对于解决另外两个问题，该算法并没有明显优于非性别 GA。在这个实验中，雄性是根据他们的健康状况来选择的，而雌性是根据它们产生好后代的能力来选择的。不幸的是，这项研究没有将结果与仅突变算法进行比较。

于 2018-02-17T06:00:36.217 回答