遗传算法中的交叉效率

Question

我已经实现了许多遗传算法来解决各种问题.但是我仍然对交叉/重组的有用性持怀疑态度.

我通常在实现交叉之前首先实现变异.在我实施交叉之后,与简单地使用突变并在每一代中引入一些随机个体以确保遗传相比,我通常不会看到产生良好候选解决方案的速率显着提高.

当然,这可能是由于交叉函数和/或概率的选择不当,但我想得到一些具体的解释/证据,说明为什么/是否交叉改善了GA.有没有关于此的研究？

我理解它背后的原因:交叉可以将两个人的优势结合成一个人.但对我来说,就像说我们可以交配科学家和美洲虎来获得智能和快速的混合动力.

编辑:在mcdowella的回答中,他提到了如何找到一个案例,从多个起点爬山可以改善交叉是非常重要的.有人可以详细说明这一点吗？

Answer 1

它在很大程度上取决于搜索空间的平滑度.如果每个"基因组"在被用于生成"现象"之前进行哈希处理,那么你只会做随机搜索.

不太极端的情况,这就是为什么我们经常在GA中使用灰度代码整数.

您需要根据编码定制交叉和变异函数.如果你对它们进行无情的计算,那么很容易衰变.如果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的修改会使动物发生段错误.

对GA的理论分析经常使用非常粗糙的编码,并且它们受数值问题的影响大于语义问题.

Answer 2

我的印象是,从多个随机开始爬山是非常有效的,但试图找到交叉可以改善的情况是非常重要的.其中一个参考文献是DavidIcl˘anzan撰写的"Crossover:The Divine Afflatus in Search"

传统的GA理论以构建模块假设(BBH)为支柱,该模型指出遗传算法(GA)通过以高度并行的方式发现,强调和重新组合高质量字符串中的低阶模式来工作.从历史上看,尝试捕获拓扑健身景观特征,这些特征体现了这种直观直接的过程,但大多数都是不成功的.通过基于突变的算法的不同变体,基于群体的重组方法在特殊设计的抽象测试套件上反复表现优异.

一篇相关的论文是DavidIclănzan和Dan Dumitrescu撰写的"克服爬坡构造块结构的等级难度"

构件块假设表明遗传算法(GA)非常适合于分层问题,其中有效求解需要适当的问题分解和从具有强非线性相互依赖性的子解决方案组装解决方案.本文提出了一种爬坡者在积木(BB)空间上作业,可以有效地解决等级问题.

Answer 3

你对交叉操作持怀疑态度是正确的.有一篇论文称为"关于模拟进化优化中交叉的有效性"(Fogel and Stayton,Biosystems 1994).它免费提供1.

顺便说一句,如果你还没有我推荐一种名为"差异进化"的技术.它可以很好地解决许多优化问题.