17

有人可以解释一下差分进化方法吗？维基百科的定义非常技术性。

一个简单的解释和一个简单的例子将不胜感激:)

4

3 回答 3

15

这是一个简化的描述。DE 是一种优化技术，它迭代地修改一组候选解决方案，使其收敛到您的函数的最优值。

您首先随机初始化您的候选解决方案。然后在每次迭代和每个候选解决方案 x 中，您执行以下操作：

  1. 您生成一个试验向量：v = a + ( b - c ) / 2，其中 a、b、c 是在您的总体中随机挑选的三个不同的候选解决方案。
  2. 您在 x 和 v 之间随机交换向量分量以生成 v'。v 中的至少一个组件必须被交换。
  3. 只有当它是一个更好的候选者（即它更好地优化你的功能）时，你才用 v' 替换你的人口中的 x。

（请注意，上述算法非常简化；不要从中编写代码，而是在其他地方找到适当的规范）

不幸的是，维基百科的文章缺少插图。使用图形表示更容易理解，您可以在以下幻灯片中找到一些内容：http ://www-personal.une.edu.au/~jvanderw/DE_1.pdf 。

它类似于遗传算法（GA），只是候选解不被视为二进制字符串（染色体），而是（通常）被视为实向量。DE 的一个关键方面是突变步长（参见突变的步骤 1）是动态的，也就是说，它适应您的人口配置，并且在收敛时趋于零。这使得 DE 比 GA 更不容易受到遗传漂移的影响。

于 2011-09-22T18:20:06.197 回答
12

回答我自己的问题...

概述

  • 遗传算法和差分进化（DE）之间的主要区别在于遗传算法依赖于交叉，而进化策略使用突变作为主要搜索机制。
  • DE 通过将两个总体成员之间的加权差异添加到第三个成员来生成新的候选者（更多内容见下文）。
  • 如果生成的候选者优于与之比较的候选者，则将其替换；否则，原候选人保持不变。

定义

  • 人口由NP候选人组成。
  • Xi=来自当前一代的索引处的父候选i（索引范围从0到）。NP-1也称为目标向量。
  • 每个候选包含D参数。
  • Xi(j)=候选中的第jXi个参数。
  • Xa, Xb, Xc= 三个随机家长候选人。
  • 差向量 =(Xb - Xa)
  • F= 决定种群进化速度的权重。
    • 理想值：[0.5, 1.0]
  • CR= 发生交叉的概率。
    • 范围：[0, 1]
  • Xc`= 通过差分变异操作获得的变异向量。也称为施主向量。
  • XtXi=和的孩子Xc`。也称为试验向量。

算法

  1. 对于总体中的每个候选人
    • for (int i = 0; i<NP; ++i)
  2. 随机选择三个不同的父母（他们必须彼此不同并且i）
do
{
  a = random.nextInt(NP);
} while (a == i)
do
{
  b = random.nextInt(NP);
} while (b == i || b == a);
do
{
  c = random.nextInt(NP);
} while (c == i || c == b || c == a);
  1. （变异步骤）将两个总体成员之间的加权差异向量添加到第三个成员
    • Xc` = Xc + F * (Xb - Xa)
  2. （交叉步骤）对于 中的每个变量Xi，应用具有继承自的概率的均匀交叉；否则，继承自. 至少一个变量必须继承自CRXc`XiXc`
int R = random.nextInt(D);
for (int j=0; j < D; ++j)
{
  double probability = random.nextDouble();
  if (probability < CR || j == R)
    Xt[j] = Xc`[j]
  else
    Xt[j] = Xi[j]
}
  1. (选择步骤) 如果Xt优于Xi则在下一代中Xt替换。Xi否则，Xi保持不变。

资源

于 2015-04-13T02:50:28.113 回答
6

DE算法的工作非常简单。考虑您需要在给定范围内优化（最小化，例如）∑Xi^2 （球体模型），例如[-100,100]。我们知道最小值是 0。让我们看看 DE 是如何工作的。

DE是一种基于人口的算法。并且对于人口中的每个个体，都会有固定数量的染色体（想象它是一组人类和每个人的染色体或基因）。让我解释一下上面的函数

我们需要固定种群大小和染色体或基因的数量（称为参数）。例如，让我们考虑一个大小为 4 的群体，每个人都有 3 条染色体（或基因或参数）。我们称这些个体为 R1、R2、R3、R4。

第 1 步：初始化种群

我们需要在 [-100,100] 范围内随机初始化总体

        G1    G2    G3    objective fn value
R1 -> |-90  |  2  | 1   |   =>8105
R2 -> |  7  |  9  | -50 |   =>2630
R3 -> |  4  |  2  | -9.2|   =>104.64
R4 -> | 8.5 |  7  |  9  |   =>202.25

使用给定的目标函数计算目标函数值。在这种情况下，它是∑Xi^2。所以对于 R1，obj fn 值将是-90^2+2^2+2^2 = 8105。同样，它适用于所有人。

第 2 步：突变

固定一个目标向量，例如 R1，然后随机选择三个其他向量（个体），例如 R2、R3、R4 并执行突变。突变如下进行，

MutantVector = R2 + F(R3-R4)

（向量可以随机选择，不必按任何顺序）。[0,1] 范围内的 F（缩放因子/突变常数）是 DE 拥有的少数控制参数之一。简单地说，它描述了突变向量的不同程度。让我们保持 F = 0.5。

|  7  |  9  | -50 |
        +

       0.5 *

|  4  |  2  | -9.2|

        +

| 8.5 |  7  |  9  |

现在执行 Mutation 将给出以下 Mutant Vector

MV = | 13.25 | 13.5 | -50.1 | =>2867.82

第 3 步：交叉

现在我们有了一个目标向量（R1）和一个由 R2、R3 和 R4 形成的突变向量 MV，我们需要进行交叉。将 R1 和 MV 视为两个父母，我们需要这两个父母的孩子。进行交叉以确定要从父母双方那里获取多少信息。它由交叉率（CR）控制。孩子的每个基因/染色体确定如下，

生成一个介于 0 和 1 之间的随机数，如果它大于 CR ，则从目标（R1）继承一个基因，否则从突变体（MV）继承一个基因。

让我们设置 CR = 0.9。由于我们有 3 个个体染色体，我们需要生成 3 个介于 0 和 1 之间的随机数。例如，这些数字分别是 0.21、0.97、0.8。第一个和最后一个小于 CR 值，因此子向量中的这些位置将由来自 MV 的值填充，第二个位置将由从目标（R1）获取的基因填充。

目标-> |-90 | 2 | 1 | 突变体->| 13.25 | 13.5 | -50.1 |

random num - 0.21, =>  `Child -> |13.25| -- | --    |`
random num - 0.97, =>  `Child -> |13.25| 2  | --    |`
random num - 0.80, =>  `Child -> |13.25| 2  | -50.1 |`

Trial vector/child vector -> | 13.25 | 2 | -50.1 | =>2689.57

第 4 步：选择

现在我们有了孩子和目标。比较两者的 obj fn，看看哪个更小（最小化问题）。从两个人中选择那个人为下一代

 R1                       -> |-90    |  2  | 1     |   =>8105
Trial vector/child vector -> | 13.25 | 2   | -50.1 |   =>2689.57

显然，孩子更好，所以用孩子替换目标（R1）。所以新的人口将成为

        G1    G2    G3    objective fn value
R1 -> | 13.25 | 2   | -50.1 |   =>2689.57
R2 -> |  7    |  9  | -50   |   =>2500
R3 -> |  4    |  2  | -9.2  |   =>104.64
R4 -> | -8.5  |  7  |  9    |   =>202.25

此过程将继续进行，直到达到所需的代数或直到我们获得所需的值。希望这会给你一些帮助。

于 2016-01-13T08:52:10.727 回答