我们知道遗传算法（或进化计算）使用我们的解决方案空间 Ω 中的点的编码而不是直接使用这些点。在文献中，我们经常发现遗传算法有以下缺点：（1）由于许多染色体被编码成一个相似的Ω点或相似的染色体有非常不同的点，效率相当低。你认为这真的是一个缺点吗？因为这类算法在每次迭代中都使用变异算子来使候选解多样化。为了增加更多的多样化，我们只需增加交叉的概率。而且我们不能忘记我们的初始种群（染色体）是随机生成的（另一个更加多样化）。问题是，如果您认为 (1) 是 GA 的一个缺点，您能否提供更多细节？谢谢你。
问问题
989 次
2 回答
6
变异和随机初始化不足以解决被称为遗传漂移的问题，这是遗传算法的主要问题。遗传漂变意味着遗传算法可能会很快失去其大部分遗传多样性，并且搜索以不利于交叉的方式进行。这是因为随机初始种群很快收敛。变异是另一回事，如果它很高，它会多样化，这是真的，但同时它会阻止收敛，并且解决方案将以更高的概率与最优值保持一定距离。您将需要在搜索过程中调整突变概率（而不是交叉概率）。以类似的方式，类似于 GA 的进化策略在搜索期间调整突变强度。
我们开发了一种称为 OffspringSelection GA (OSGA) 的 GA 变体，它在交叉后引入了另一个选择步骤。只有那些超过父母适应度的孩子才会被接受（更好、更差或任何线性插值）。通过这种方式，您甚至可以使用随机父选择，并对后代的质量产生偏见。已经表明，这减缓了遗传漂变。该算法在我们的框架HeuristicLab中实现。它具有图形用户界面，因此您可以下载并尝试解决一些问题。
其他对抗遗传漂移的技术是利基和拥挤，它们让多样性流入选择，从而引入另一种但可能不同的偏见。
编辑：我想补充一点，拥有多个质量相同的解决方案的情况当然可能会带来问题，因为它会在搜索空间中创建中性区域。不过，我觉得你不是这个意思。主要问题是遗传漂变，即。（重要）遗传信息的丢失。
于 2012-02-08T09:43:01.880 回答
0
作为旁注，您（OP）说：
我们知道遗传算法（或进化计算）使用我们的解决方案空间 Ω 中的点的编码而不是直接使用这些点。
这并非总是如此。个体被编码为基因型，它可以具有任何形状，例如字符串（遗传算法）或实数向量（进化策略）。在评估个体时，即在计算其适应度时，每个基因型都会转化为表型。在某些情况下，表型与基因型相同：称为直接编码。否则，编码称为间接。（您可以在此处找到更多定义（第 2.2.1 节））
直接编码示例： http ://en.wikipedia.org/wiki/Neuroevolution#Direct_and_Indirect_Encoding_of_Networks
Example of indirect encoding:
Suppose you want to optimize the size of a rectangular parallelepiped dened by its length, height and width. To simplify the example, assume that these three quantities are integers between 0 and 15. We can then describe each of them using a 4-bit binary number. An example of a potential solution may be to genotype 0001 0111 01010. The corresponding phenotype is a parallelepiped of length 1, height 7 and width 10.
现在回到关于多样性的原始问题，除了 DonAndre 所说的之外，您还可以阅读AE Eiben 和 JE Smith 编写的优秀书籍Introduction to Evolutionary Computing的第 9 章“多模态问题和空间分布”。以及有关该问题的研究论文，例如鼓励进化机器人中的行为多样性：一项实证研究。总之，多样性不是 GA 的缺点，它“只是”一个问题。
于 2012-02-08T12:54:30.097 回答