遗传算法中交叉的效率问题

Question

我已经实现了许多遗传算法来解决各种问题。然而，我仍然怀疑交叉/重组的有用性。

通常在实现交叉之前，我先实现变异。在实现交叉之后，与仅使用变异并引入每个代中的一些随机个体以确保基因多样性相比，我通常不会看到生成良好的候选解的速度显着提高。

当然，这可能归因于交叉函数和/或概率选择不当，但我希望得到一些具体的解释/证据，说明交叉是否改进了遗传算法。是否有关于此的任何研究？

我理解其中的道理：交叉可以将两个个体的优点结合成一个个体。但对我来说，这就像是说我们可以将一位科学家和一只美洲豹交配，得到一个聪明而快速的杂交品种。

编辑：在mcdowella的答案中，他提到找到一个情况，其中交叉可以改进从多个起始点进行爬坡的情况是非平凡的。有人能详细解释一下这一点吗？

- tskuzzy

---

这种问题可能会在cstheory.SE得到更好的答案。 - Fred Foo

1. 你使用了哪种交叉方式？随机的？单点的？双点的？
2. 你具体在寻找什么？是一篇讨论交叉对解决方案质量影响的文章参考吗？

- amit

这始终取决于问题，并且可以被证明如此。没有一种通用的技术。任何有效的搜索算法只有在其偏好在某种程度上与搜索空间的显著特征保持一致时才有效。当你只有相对较少的大山时，爬山算法表现最佳。当优化点之间的障碍大多较浅时，模拟退火算法表现最佳。有些情况下，特定的交叉算子效果良好，而有些情况则不然。 - deong

@deong：是的，但我正在寻找交叉效果良好的示例/案例。 - tskuzzy

问题在于“交叉”这个术语非常模糊。假设您正在解决一个仅使用变异的单目标问题。这里有一个交叉算子：从任何一个父代中取出任意1位。我肯定希望我的算法能够胜过你的算法。从您的经验来看，您真正能说的只是您尝试过的交叉算子似乎对您正在解决的特定问题实例没有帮助。我怀疑对于任何特定的问题，都存在一种交叉算子可以提高性能，纯粹是因为算子空间如此之大。 - deong

Answer 1

这强烈地取决于您的搜索空间的平滑度。如果每个“基因组”在用于生成“表型组”之前都被哈希化，那么您只会进行随机搜索。

较不极端的情况是，这就是为什么我们经常在遗传算法中使用格雷码整数的原因。

您需要根据编码定制交叉和变异函数。如果您向它们投入不友好的计算，遗传算法很容易衰减。如果A和B的交叉不能产生既像A又像B的东西，那么它就是无用的。

示例：

基因组长度为3位，第0位确定其是否陆生或海生。第1-2位描述陆生生物的消化功能和海生生物的视觉能力。

考虑两种陆生生物。

    | bit 0 | bit 1 | bit 2
----+-------+-------+-------
Mum | 0     | 0     | 1
Dad | 0     | 1     | 0

他们可能在位1和2之间交叉，产生一个消化功能介于母亲和父亲之间的孩子。太棒了。

这种交叉似乎是合理的前提是位0没有改变。如果发生了改变，那么你的交叉函数就把某些肠子变成了某种眼睛。呃……什么鬼？它可能像随机突变一样。

这就引出了DNA如何解决这个问题。嗯，它既具有模态性，又具有层次性。有些大段可以发生很大的变化而没有太多的影响，而在其他情况下，单个突变可能会产生极端的影响（如上面的位0）。有时X的值会影响到Y所触发的行为，而所有X的值都是合法的，并且可以进行探索，而对Y的修改会使动物出现故障。

遗传算法的理论分析通常使用非常简单的编码，并且它们更容易受到数值问题的影响，而不是语义问题。

- spraff

---

在你的例子中，每个比特都是独立的。然而我发现，通常个体的质量也取决于其编码的每个“部分”之间的关系。在我看来，交叉具有非常低的概率能够创造出更好的个体，考虑到这些复杂的关系。但当然，你说得对，这主要取决于搜索空间和特定的交叉函数（正如你所提到的，应该根据手头的问题进行定制）。 - tskuzzy

Answer 2

我的印象是从多个随机起点开始的爬山算法非常有效，但是尝试找到交叉可以改进这一点的案例并不容易。其中之一参考文献是David Icl˘anzan的《Crossover: The Divine Afflatus in Search》，其中陈述道：

传统遗传算法理论基于建筑块假说（BBH），该假说指出遗传算法通过以强并行方式在高质量字符串中发现、强调和重新组合低阶图式来工作。历史上，捕捉体现这种直观简单过程的拓扑适应性景观特征的尝试大多未成功。基于群体的重组方法在特殊设计的抽象测试套件上被不同变异算法的变体反复胜过。

相关论文是David Iclănzan和Dan Dumitrescu的《Overcoming Hierarchical Difficulty by Hill-Climbing the Building Block Structure》，其中陈述道：

建筑块假说表明，遗传算法（GAs）非常适用于分层问题，其中高效求解需要适当的问题分解和从具有强非线性相互依赖关系的子解决方案中组装解决方案。本文提出了一种在建筑块（BB）空间上运行的爬山者，可以有效地解决分层问题。

- mcdowella

---

没错！在我看来，爬山算法似乎比交叉算法更有可能产生更好的结果，所以我想知道为什么我们要浪费 CPU 周期进行交叉。我会查看那些参考资料，因为我想了解如何有效地使用交叉算法。 - tskuzzy

嗯，我们至少有一个存在证明，即杂交在某些环境中表现更好。;) - Nick Johnson

Answer 3

您对基因交叉操作持怀疑态度是正确的。有一篇论文叫做《关于模拟进化优化中交叉有效性的研究》（Fogel和Stayton，Biosystems 1994）。您可以在这里免费获取。顺便说一下，如果您还没有了解过差分进化技术，我建议您去了解一下。它可以很好地解决许多优化问题。

- user_48349383

Answer 4

约翰·霍兰的两部重要著作《自然和人工系统中的适应性》和《隐藏的秩序》（较为非正式）深入探讨了杂交理论。在我看来，戈德伯格的《遗传算法在搜索、优化和机器学习中的应用》一书中有一章关于数学基础的内容非常易懂，其中包括以下结论：“通过交叉和复制……那些表现良好且定义长度较短的模式将以指数增长的速度被采样。” 另一个不错的参考资料可能是安肯布兰特的《收敛理论的扩展和遗传算法时间复杂度的证明》（收录于 Rawlins 的《遗传算法基础》中）。

我很惊讶您在工作中没有意识到交叉的强大之处；当我开始使用遗传算法，并看到“有针对性”的交叉如此强大时，我感到我对进化的洞见颠覆了我在学校所学的知识。所有关于“突变如何导致这个和那个？”和“嗯，在这么多代之后……”的问题似乎从根本上是错误的。

- Larry OBrien

---

这两本书都是开创性的参考资料，但现在已经非常过时。有理论研究表明交叉操作是可证益的，但像大多数遗传算法理论一样，为了使数学可行，削减现实假设使得结果在实际问题中高度值得怀疑。 - deong

@deong 你能澄清一下吗 -- 你是在说遗传算法的理论优势随着理论的进步而削弱，还是说遗传算法的实用性仍然具有挑战性？ - Larry OBrien

大多数情况下发生的是，那些早期工作中提倡用模式定理来证明遗传算法运行的合理性（包括交叉的好处），已被发现过于简单化。取而代之的理论更加准确，但目前在大多数情况下无法产生实际的预测结果，而且通常不能告诉您算法在给定实际问题上的性能。我们基本上回到了“它在某些问题上运行得相当好，但我们不能说太多关于何时或为什么。” - deong

@deong：所以使用遗传算法来解决问题是一种乱猜？选择一个好的交叉操作符只是运气和机会的问题吗？即使仅仅是一条指南而不是定理，也必须有某种方式表征遗传算法何时有效。 - tskuzzy

大多数设计启发式算法的指南都是经验性的——人们报告了对他们有效的参数。这在起点上还好，但我们实际上还不知道如何从根本上描述交叉对问题的影响。而且，这几乎适用于元启发式算法中的所有内容。 “什么算法对我的问题最有效”这个问题仍然未解决，可能毫不夸张地称之为该领域的“P=NP?”问题。 - deong

Answer 5

交叉和变异！实际上两个都是必要的。交叉是一种探索性操作，而变异是一种开发性操作。考虑解决方案、问题的结构和优化率的可能性，选择正确的Pc和Pm值（交叉概率和变异概率）非常重要。

请查看此 GA-TSP-Solver，它使用许多交叉和变异方法。您可以测试任何交叉并与给定概率一起进行变异。

- MShams

Answer 6

这主要取决于搜索空间和您使用的交叉类型。对于某些问题，我发现在开始时使用交叉然后进行变异会加速找到解决方案的过程，但这不是很好的方法，因为最终会找到类似的解决方案。如果我们同时使用交叉和变异，通常可以获得更好的优化解决方案。但是对于某些问题，交叉可能非常破坏性。

此外，仅凭遗传算子无法解决大型/复杂问题。当您的算子不能改善解决方案（即它们不增加适应度值）时，您应该开始考虑其他解决方案，例如增量演化等。

- ES2018