缺乏多样性，这真的是遗传算法的缺点吗？

Question

我们知道，遗传算法(或进化计算)使用的是解空间Ω中的点的编码，而不是直接使用这些点。在文献中，我们经常发现遗传算法的缺点是：(1)由于许多染色体被编码到Ω的一个相似的点上，或者相似的染色体有非常不同的点，效率相当低。你认为这真的是一个缺点吗？因为这类算法在每次迭代中都使用变异算子来使候选解多样化。为了增加更多的多样化，我们只需增加交叉的可能性。我们不能忘记我们的初始群体(染色体)是随机产生的(另一个更多样化的)。问题是，如果您认为(1)是GAs的一个缺点，您能提供更多细节吗？谢谢。

Answer 1

变异和随机初始化不足以解决遗传算法的主要问题，即遗传漂移问题。遗传漂移意味着GA可能很快失去其大部分遗传多样性，搜索以一种不利于交叉的方式进行。这是因为随机初始种群很快就收敛了。变异是另一回事，如果变异很高，它就会多样化，这是真的，但同时它会阻止收敛，解决方案将以更高的概率保持在与最优的一定距离。在搜索过程中，您需要调整变异概率(而不是交叉概率)。以类似于GA的进化策略，在搜索过程中自适应变异强度。

我们开发了一种称为OffspringSelection GA的GA变体，它在交叉后引入了另一个选择步骤。只有那些超过父母适合度的孩子才会被接受(越好、越差或任何线性插值)。这样，你甚至可以使用随机的亲本选择，并将偏差放在后代的质量上。已有研究表明，这会减缓遗传漂移。该算法在我们的框架HeuristicLab中实现。它有一个图形用户界面，所以你可以下载并尝试解决一些问题。

其他对抗遗传漂移的技术是小生境和拥挤，它们让多样性流入选择，从而引入另一个，但可能是不同的偏见。

编辑:我想补充的是，具有相同质量的多个解决方案的情况当然可能会带来问题，因为它在搜索空间中创建了中性区域。然而，我认为你并不是真的那么想的。主要的问题是遗传漂移，即。(重要的)遗传信息的丢失。

Answer 2

作为附注，你(操作员)说：

我们知道，遗传算法(或进化计算)使用的是解空间Ω中的点的编码，而不是直接使用这些点。

这并非总是正确的。个体被编码为基因型，它可以具有任何形状，例如字符串(遗传算法)或real向量(进化策略)。当评估个体时，即当计算其适合度时，每个基因型被转换为表型。在某些情况下，表型与基因型是相同的:它被称为直接编码。否则，该编码称为间接。(你可以找到更多的定义here (section 2.2.1))

直接编码示例：http://en.wikipedia.org/wiki/Neuroevolution#Direct_and_Indirect_Encoding_of_Networks

间接编码示例：

假设您希望优化矩形平行六面体的大小，该矩形平行六面体的长度、高度和宽度都会减小。为了简化示例，假设这三个量是0到15之间的整数。然后我们可以使用4位二进制数来描述它们。潜在解决方案的一个例子可以是基因型0001 0111 01010。相应的表型是长度为1，高度为7，宽度为10的平行六面体。

现在回到最初关于多样性的问题，除了DonAndre说你可以读到的东西之外，你还可以阅读A.E.Eiben和J.E.Smith写的优秀书籍Introduction to Evolutionary Computing的第9章“多模态问题和空间分布”。以及一篇关于这一问题的研究论文，如Encouraging Behavioral Diversity in Evolutionary Robotics: an Empirical Study。总之，多样性不是GA的缺点，它“只是”一个问题。