解释差异进化方法

Question

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

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

Answer 1

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

Answer 2

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

概观

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

定义

• 人口由NP候选人组成.
• Xi=索引的父候选者i(索引范围从0to到NP-1当前一代).也称为目标矢量.
• 每个候选人包含D参数.
• Xi(j)= 候选人中的第j个参数Xi.
• 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);

3. (突变步骤)将两个群体成员之间的加权差异向量添加到第三个成员
   • Xc` = Xc + F * (Xb - Xa)
4. (交叉步骤)对于每个变量Xi,应用均匀交叉概率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]
}

5. (选择步骤)如果Xt优于Xi当时Xt替换Xi下一代.否则,Xi保持不变.

资源

• 见这对术语的概述
• 请参阅Vasan Arunachalam对差分进化的优化,以解释差分进化算法
• 参见Evolution:Swagatam Das和Ponnuthurai Nagaratnam Suganthan对差异进化算法的不同变体的最新技术概述
• 有关Python中的DE算法实现的详细说明,请参阅Scratch with Python中的差异进化优化.

Answer 3

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)

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

|  7  |  9  | -50 |
        +

       0.5 *

|  4  |  2  | -9.2|

        +

| 8.5 |  7  |  9  |

现在执行 Mutation 将提供以下突变向量

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 条个体染色体，因此我们需要生成 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

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