何时以及为什么交叉有利于差异进化？

Question

我为我正在做的边项目实现了差分进化算法.因为交叉步骤似乎涉及很多参数选择(例如交叉概率),所以我决定跳过它并仅使用变异.该方法似乎工作正常,但我不确定如果我介绍交叉,我是否会获得更好的性能.

主要问题:将差异引入差异进化的动机是什么？您能提供一个玩具示例,其中介绍交叉超出纯变异吗？

我的直觉是,交叉会在二维中产生类似下面的内容.假设我们有两个父矢量(红色).均匀交叉可以在其中一个蓝点处产生新的试验向量.

我不确定为什么这种探索会被认为是有益的.事实上,如果高适应度解决方案遵循一些线性趋势,这似乎会使性能变差.在下图中,假设红点是当前的总体,最佳解决方案是在右下角.人口正在山谷中行进,使得右上角和左下角产生不良解决方案.左上角产生"好"但不是最理想的解决方案.注意均匀交叉如何产生与改进方向正交的试验(蓝色).我使用了1的交叉概率和忽略的变异来说明我的观点(见代码).我想这种情况可能会在优化问题中经常出现,但可能会误解某些东西.

注意:在上面的例子中,我隐含地假设群体在这个空间中被随机初始化(均匀),并且已经开始收敛到中心谷(正左上到右下)的正确解.

这个玩具示例是凸的,因此差分演化甚至不是合适的技术.然而,如果这个主题嵌入在多模态健身景观中,那么交叉似乎可能是有害的.虽然交叉确实支持探索,这可能是有益的,但我不确定为什么人们会选择在这个特定的方向上进行探索.

以上示例的R代码:

N = 50

x1 <- rnorm(N,mean=2,sd=0.5)
x2 <- -x1+4+rnorm(N,mean=0,sd=0.1)
plot(x1,x2,pch=21,col='red',bg='red',ylim=c(0,4),xlim=c(0,4))

x1_cx = list(rep(0, 50))
x2_cx = list(rep(0, 50))
for (i in 0:N) {
  x1_cx[i] <- x1[i]
  x2_cx[i] <- x2[sample(1:N,1)]
}

points(x1_cx,x2_cx,pch=4,col='blue',lwd=4)

后续问题:如果交叉在某些情况下是有益的,是否有合理的方法来a)确定您的特定问题是否会受益于交叉,以及b)如何调整交叉参数以优化算法？

一个相关的stackoverflow问题(我正在寻找更具体的东西,例如玩具示例):在差分进化算法中跨越的重要性是什么？

一个类似的问题,但不是特定的差异演化:遗传算法中的交叉效率

Answer 1

我并不是特别熟悉DE算法的具体细节,但一般来说,交叉点是如果你有两个非常不同的高适应度的个体,它会产生一个介于它们之间的后代而不是特别相似.突变只探讨每个人的当地社区,而不考虑其他人口.如果您将基因组视为某些高维向量空间中的点,则突变会随机方向移动.因此,突变需要采取一些小步骤,因为如果你从一个明显优于随机的位置开始,随机方向的长步骤几乎肯定会使事情变得更糟,因为它基本上只是将熵引入进化的基因组.您可以将交叉视为从父母一方到另一方的一个步骤.由于另一个父母也比随机更好,因此更有希望在这个方向上迈出更长的一步.这允许更快地探索健身景观的有希望的部分.

在真实的生物有机体中,基因组通常以这样的方式组织,即依赖于彼此的基因在同一染色体上紧密相连.这意味着交叉不太可能破坏协同基因组合.真正的进化实际上会移动基因来实现这一点(虽然这比单个基因的进化要慢得多),有时基因组的高阶结构(DNA的三维形状)也会发展,以防止特别敏感区域的交叉.这些机制很少在进化算法中建模,但如果您按照可能相互接近的基因的方式对基因组进行排序,您将获得更多的交叉.