解释差异进化方法

问题描述 投票：17回答：3

有人可以解释差异进化方法吗？维基百科definition非常技术性。

一个简单的例子后面的一个愚蠢的解释将是赞赏:)

evolutionary-algorithm differential-evolution
3个回答
14
投票

这是一个简化的描述。 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更不易受遗传漂移的影响。

9
投票

回答我自己的问题......

概观

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

定义

  • 人口由NP候选人组成。
  • Xi =来自当前一代的指数i（指数范围从0到NP-1）的父母候选人。也称为目标矢量。
  • 每个候选人都包含D参数。
  • Xi(j) =候选Xi中的第j个参数。
  • Xa，Xb，Xc =三个随机的父母候选人。
  • 差异向量= (Xb - Xa)
  • F =决定人口进化速度的权重。 理想值：[0.5,1.0]
  • CR =交叉发生的概率。 范围：[0,1]
  • Xc` =通过差异突变操作获得的突变载体。也称为供体载体。
  • Xt = Xi和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中的每个变量，应用uniform crossover和概率CR从Xc`继承;否则，继承自Xi。必须从Xc`继承至少一个变量
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保持不变。

资源

4
投票

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

DE是一种基于人口的算法。对于群体中的每个个体，将存在固定数量的染色体（将其视为一组人类和染色体或每个染色体中的基因）。让我解释一下DE w.r.t上面的功能

我们需要确定种群大小和染色体或基因的数量（命名为参数）。例如，让我们考虑一个大小为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，则从突变体（MV）继承靶（R1）的基因。

我们设置CR = 0.9。由于我们有3条个体染色体，我们需要在0和1之间生成3个随机数。例如，这些数字分别为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

这个程序将持续到所需的世代数达到或直到我们得到我们想要的值。希望这会给你一些帮助。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.