8

我为我正在做的一个副项目实现了一个差分进化算法。因为交叉步骤似乎涉及很多参数选择（例如交叉概率），所以我决定跳过它，只使用突变。该方法似乎工作正常，但我不确定如果我引入交叉是否会获得更好的性能。

主要问题：将交叉引入差异进化的动机是什么？您能否提供一个玩具示例，其中引入交叉优于纯突变？

我的直觉是交叉会在二维中产生类似下面的东西。假设我们有两个父向量（红色）。均匀交叉可以在其中一个蓝点产生一个新的试验向量。

我不确定为什么这种探索会是有益的。事实上，如果高适应度解决方案遵循某种线性趋势，这似乎会使性能变得更糟。在下图中，假设红点是当前人口，最优解在右下角。人口正在沿着山谷移动，因此右上角和左下角会产生不好的解决方案。左上角产生“好的”但次优的解决方案。注意均匀交叉如何产生正交试验（蓝色）向改进的方向发展。我使用了 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问题（我正在寻找更具体的东西，例如一个玩具示例）：在差分进化算法中交叉的重要性是什么？

一个类似的问题，但不是特定于差分进化：遗传算法中的交叉效率

4

3 回答 3

6

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

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

于 2014-01-26T06:31:39.070 回答
1

不，交叉没有用。我在那里说了。:P

我从来没有发现需要交叉。人们似乎认为它有某种魔力。但它没有（也不能）做任何比简单突变更有用的事情。大突变可用于探索整个问题空间，小突变可用于利用利基。

我读过的所有解释（委婉地说）都不令人满意。交叉只会使您的算法复杂化。尽快放下。你的生活会更简单。.... 恕我直言。

于 2014-02-07T00:32:49.923 回答
1

正如 Daniel 所说，交叉是一种在问题环境中采取更大步骤的方法，允许您摆脱单个突变无法做到的局部最大值。

是否合适将取决于问题空间的复杂性，基因型 -> 表型表达的工作方式（相关基因是否会靠近）等。

更正式地说，这是局部搜索算法中的“连通性”概念，它提供了足够强大的算子，使得局部搜索邻域足够大，可以避开局部最小值。

于 2014-01-29T13:20:17.310 回答