2

差分进化 (DE) 和遗传算法 (GA) 之间的区别之一是 DE 会丢弃一个新候选者，除非它比它所衍生的旧候选者更合适，而 GA 允许“不太合适”的候选者以一定的概率存活。最初 DE 的方法听起来是个好主意，但我相信这会阻止它解决以下类别的问题。

想象一下，我们正在尝试最大化以下的适应度得分：

A - [max(0, A - 50) * B] + [max(0, A - 75) * 2 * B]

其中参数范围从0到100。

  • 最初增加它是有益的A，直到达到50.
  • 其次，设置B为零是有益的。
  • 接下来，增加到A75是有利的。
  • 其次，同时增加B和是有益的A。

最后一点很重要：如果两者中的一个A或B两个独立增加，则适应度得分将下降。

回到差分进化算法，我看不出它如何解决上述问题，因为最初我们希望每一代只改变一个参数，但最终我们希望每一代改变多个参数。如果我们过早地改变每一代的多个参数，我们会降低生存的概率，进而降低进化的速度。但是，如果我们一次改变一个参数，我们将永远找不到全局最大值。

我的问题如下：

  • 这是差分进化算法的一个已知问题吗？
  • 有已知的解决方案吗？
  • 通用算法会遇到同样的问题吗？

我不是要求解决上述特定功能。我在问差分进化是否有可能解决您事先不知道在任何给定时间需要改变多少参数并且您希望最终尽可能接近全局最大值的问题。

4

1 回答 1

1

DE是一种流行的优化元启发式算法，具有大量变体（此处有一些示例）。

第一个 DE 归功于 R. Storn 和 K. Price (1997)。从那时起，主要算子的许多变化、杂交、自动参数调整、自适应方案、结构化种群……都被提出。

因此，要准确回答该问题，需要有关您所指的 DE 风味的更多详细信息。

无论如何，DE的典型方案是：

 g = 0                          // Generation 0
 P(g) = {x_1(g), ... , x_n(g)}  // Population initialization 
 while (!stop())                // Some stop condition
   for i = 1 to n
     y_i = new_mutant(X(g))
     z_i = crossover(x_i(g), y_i)
     if f(z_i) < f(x_i(g))
       x_i(g + 1) = z_i
     else
       x_i(g + 1) = x_i(g)
   ++g

该函数的一个常见选择crossover()是二项式交叉（类似于 GA统一交叉）：

if (random(0,1) < CR || j == 0)
  z_i[j] = y_i[j]
else
  z_i[j] = x_i[j]

（所描述的策略通常称为rand1bin）

通常多于一种成分（和至少一种）取自突变载体。

从进化的开始到结束，DE 产生具有一个或两个参数A/B突变的后代（这是通过 控制的CR）。

这不是问题，因为 DE 是一种基于群体的算法：对于一个人来说“最终”的东西对于另一个人来说是“初始”的。

rand1bin尤其是一个很好的探索策略，并且利用参数的完整数值范围（即[0, 100]在示例中）的初始种群避免了所描述的问题。

在我看来，修改顺序可能仅对极少数群体或具有初始不必要限制多样性的群体来说是一个问题。

3D 绘图 等高线图

使用rand1bin / best1bin和小群体（即 20 个人）进行的各种模拟10 x number of parameters证实了特定功能并不“难”，并且经常在 120 代内找到全局最大值。

于 2016-03-31T13:02:29.087 回答