r - 交叉何时以及为何对差异进化有益？

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 问题(我正在寻找更具体的内容，例如玩具示例):what is the importance of crossing over in Differential Evolution Algorithm?

类似的问题，但不特定于差异进化:Efficiency of crossover in genetic algorithms

Answer 1

我不是特别熟悉 DE 算法的细节，但总的来说，交叉点是，如果你有两个非常不同的个体，并且适应度很高，那么它会产生一个介于它们之间的后代，而不会与任何一个特别相似。突变仅探索每个个体的局部邻域，而不考虑群体的其余部分。如果您将基因组视为某些高维向量空间中的点，那么突变就会向随机方向移动。因此，突变需要采取小步骤，因为如果你从一个明显优于随机位置的位置开始，那么朝随机方向迈出一大步几乎肯定会让事情变得更糟，因为它本质上只是将熵引入进化的基因组中。您可以将交叉视为从 parent 一方迈向另一方的一步。由于另一方 parent 也比随机的更好，因此更有希望朝这个方向迈出更远的一步。这样可以更快地探索健身领域有前途的部分。

在真实的生物有机体中，基因组通常以这样的方式组织:相互依赖的基因在同一条染色体上靠近在一起。这意味着交叉不太可能破坏协同基因组合。真正的进化实际上会移动基因来实现这一点(尽管这比单个基因的进化慢得多)，有时基因组的高阶结构(DNA 的 3 维形状)会进化以防止特别敏感区域的交叉。这些机制很少在进化算法中建模，但如果您以一种将可能相互作用的基因彼此靠近的方式对基因组进行排序，您将从交叉中获得更多。