The working of DE algorithm is very simple.
Consider you need to optimize(minimize,for eg) ∑Xi^2 (sphere model) within a given range, say [-100,100]. We know that the minimum value is 0. Let's see how DE works.
DE is a population-based algorithm. And for each individual in the population, a fixed number of chromosomes will be there (imagine it as a set of human beings and chromosomes or genes in each of them).
Let me explain DE w.r.t above function
We need to fix the population size and the number of chromosomes or genes(named as parameters). For instance, let's consider a population of size 4 and each of the individual has 3 chromosomes(or genes or parameters). Let's call the individuals R1,R2,R3,R4.
Step 1 : Initialize the population
We need to randomly initialise the population within the range [-100,100]
objective function value is calculated using the given objective function.In this case, it's ∑Xi^2. So for R1, obj fn value will be -90^2+2^2+2^2 = 8105. Similarly it is found for all.
Step 2 : Mutation
Fix a target vector,say for eg R1 and then randomly select three other vectors(individuals)say for eg.R2,R3,R4 and performs mutation. Mutation is done as follows,
MutantVector = R2 + F(R3-R4)
(vectors can be chosen randomly, need not be in any order).F (scaling factor/mutation constant) within range [0,1] is one among the few control parameters DE is having.In simple words , it describes how different the mutated vector becomes. Let's keep F =0.5.
Now performing Mutation will give the following Mutant Vector
MV = | 13.25 | 13.5 | -50.1 | =>2867.82
Step 3 : Crossover
Now that we have a target vector(R1) and a mutant vector MV formed from R2,R3 & R4 ,we need to do a crossover. Consider R1 and MV as two parents and we need a child from these two parents. Crossover is done to determine how much information is to be taken from both the parents. It is controlled by Crossover rate(CR). Every gene/chromosome of the child is determined as follows,
a random number between 0 & 1 is generated, if it is greater than CR , then inherit a gene from target(R1) else from mutant(MV).
Let's set CR = 0.9. Since we have 3 chromosomes for individuals, we need to generate 3 random numbers between 0 and 1. Say for eg, those numbers are 0.21,0.97,0.8 respectively. First and last are lesser than CR value, so those positions in the child's vector will be filled by values from MV and second position will be filled by gene taken from target(R1).
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
Step 4 : Selection
Now we have child and target. Compare the obj fn of both, see which is smaller(minimization problem). Select that individual out of the two for next generation
This procedure will be continued either till the number of generations desired has reached or till we get our desired value. Hope this will give you some help.
它与遗传算法 (GA) 类似，只是候选解不被视为二进制字符串（染色体），而是（通常）被视为实数向量。 DE 的一个关键方面是突变步长（参见突变的步骤 1）是动态的，也就是说，它会适应群体的配置，并且在收敛时趋于零。这使得 DE 比 GA 更不容易受到遗传漂变的影响。
Here's a simplified description. DE is an optimisation technique which iteratively modifies a population of candidate solutions to make it converge to an optimum of your function.
You first initialise your candidate solutions randomly. Then at each iteration and for each candidate solution x you do the following:
you produce a trial vector: v = a + ( b - c ) / 2, where a, b, c are three distinct candidate solutions picked randomly among your population.
you randomly swap vector components between x and v to produce v'. At least one component from v must be swapped.
you replace x in your population with v' only if it is a better candidate (i.e. it better optimise your function).
(Note that the above algorithm is very simplified; don't code from it, find proper spec. elsewhere instead)
Unfortunately the Wikipedia article lacks illustrations. It is easier to understand with a graphical representation, you'll find some in these slides: http://www-personal.une.edu.au/~jvanderw/DE_1.pdf .
It is similar to genetic algorithm (GA) except that the candidate solutions are not considered as binary strings (chromosome) but (usually) as real vectors. One key aspect of DE is that the mutation step size (see step 1 for the mutation) is dynamic, that is, it adapts to the configuration of your population and will tend to zero when it converges. This makes DE less vulnerable to genetic drift than GA.
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);
（突变步骤）将两个群体成员之间的加权差异向量添加到第三个成员
Xc` = Xc + F * (Xb - Xa)
（交叉步骤）对于 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]
}
The principal difference between Genetic Algorithms and Differential Evolution (DE) is that Genetic Algorithms rely on crossover while evolutionary strategies use mutation as the primary search mechanism.
DE generates new candidates by adding a weighted difference between two population members to a third member (more on this below).
If the resulting candidate is superior to the candidate with which it was compared, it replaces it; otherwise, the original candidate remains unchanged.
Definitions
The population is made up of NP candidates.
Xi = A parent candidate at index i (indexes range from 0 to NP-1) from the current generation. Also known as the target vector.
Each candidate contains D parameters.
Xi(j) = The jth parameter in candidate Xi.
Xa, Xb, Xc = three random parent candidates.
Difference vector = (Xb - Xa)
F = A weight that determines the rate of the population's evolution.
Ideal values: [0.5, 1.0]
CR = The probability of crossover taking place.
Range: [0, 1]
Xc` = A mutant vector obtained through the differential mutation operation. Also known as the donor vector.
Xt = The child of Xi and Xc`. Also known as the trial vector.
Algorithm
For each candidate in the population
for (int i = 0; i<NP; ++i)
Choose three distinct parents at random (they must differ from each other and 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);
(Mutation step) Add a weighted difference vector between two population members to a third member
Xc` = Xc + F * (Xb - Xa)
(Crossover step) For every variable in Xi, apply uniform crossover with probability CR to inherit from Xc`; otherwise, inherit from Xi. At least one variable must be inherited from 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]
}
(Selection step) If Xt is superior to Xi then Xt replaces Xi in the next generation. Otherwise, Xi is kept unmodified.
发布评论
评论（3）
DE算法的工作非常简单。
考虑您需要在给定范围内优化（最小化，例如）ΣXi^2（球体模型），例如[-100,100]。我们知道最小值是0。让我们看看DE是如何工作的。
DE 是一种基于群体的算法。对于种群中的每个个体，都会有固定数量的染色体（将其想象为一组人类以及每个人中的染色体或基因）。
让我解释一下上述函数的 DE
我们需要固定种群大小和染色体或基因的数量（称为参数）。例如，让我们考虑一个大小为 4 的群体，每个个体都有 3 条染色体（或基因或参数）。我们将这些个体称为 R1、R2、R3、R4。
步骤1：初始化种群
我们需要在[-100,100]范围内随机初始化种群，
使用给定的目标函数计算目标函数值。在本例中，它是ΣXi^2 。因此对于 R1，obj fn 值为 -90^2+2^2+2^2 = 8105。同样，它也适用于所有人。
第2步：突变
固定一个目标向量，例如R1，然后随机选择三个其他向量（个体）例如R2，R3，R4并执行突变。突变按如下方式完成，
（向量可以随机选择，无需按任何顺序）。范围 [0,1] 内的 F（缩放因子/突变常数） 是少数控制参数之一DE就是具有。简单来说，它描述了变异向量变得多么不同。让我们保持 F =0.5。
现在执行突变将得到以下突变向量
第3步：交叉
现在我们有了目标向量(R1)和由R2、R3和R2形成的突变向量MV。 R4，我们需要做一个交叉。将 R1 和 MV 视为两个父母，我们需要这两个父母的一个孩子。交叉是为了确定从父母双方获取多少信息。它由交叉率(CR)控制。孩子的每个基因/染色体都按如下方式确定，即
0 和 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.25 13.5 | 13.5 -50.1 |
第 4 步：选择
现在我们有了子项和目标。比较两者的 obj fn，看看哪个较小（最小化问题）。从这两个个体中选择该个体作为下一代
显然，子代更好，因此用子代替换 target(R1)。所以新的种群将成为
这个过程将继续，直到达到所需的代数或直到我们得到我们想要的值。希望这能给您一些帮助。
The working of DE algorithm is very simple.
Consider you need to optimize(minimize,for eg) ∑Xi^2 (sphere model) within a given range, say [-100,100]. We know that the minimum value is 0. Let's see how DE works.
DE is a population-based algorithm. And for each individual in the population, a fixed number of chromosomes will be there (imagine it as a set of human beings and chromosomes or genes in each of them).
Let me explain DE w.r.t above function
We need to fix the population size and the number of chromosomes or genes(named as parameters). For instance, let's consider a population of size 4 and each of the individual has 3 chromosomes(or genes or parameters). Let's call the individuals R1,R2,R3,R4.
Step 1 : Initialize the population
We need to randomly initialise the population within the range [-100,100]
objective function value is calculated using the given objective function.In this case, it's ∑Xi^2. So for R1, obj fn value will be -90^2+2^2+2^2 = 8105. Similarly it is found for all.
Step 2 : Mutation
Fix a target vector,say for eg R1 and then randomly select three other vectors(individuals)say for eg.R2,R3,R4 and performs mutation. Mutation is done as follows,
(vectors can be chosen randomly, need not be in any order).F (scaling factor/mutation constant) within range [0,1] is one among the few control parameters DE is having.In simple words , it describes how different the mutated vector becomes. Let's keep F =0.5.
Now performing Mutation will give the following Mutant Vector
Step 3 : Crossover
Now that we have a target vector(R1) and a mutant vector MV formed from R2,R3 & R4 ,we need to do a crossover. Consider R1 and MV as two parents and we need a child from these two parents. Crossover is done to determine how much information is to be taken from both the parents. It is controlled by Crossover rate(CR). Every gene/chromosome of the child is determined as follows,
a random number between 0 & 1 is generated, if it is greater than CR , then inherit a gene from target(R1) else from mutant(MV).
Let's set CR = 0.9. Since we have 3 chromosomes for individuals, we need to generate 3 random numbers between 0 and 1. Say for eg, those numbers are 0.21,0.97,0.8 respectively. First and last are lesser than CR value, so those positions in the child's vector will be filled by values from MV and second position will be filled by gene taken from target(R1).
Target->
|-90 | 2 | 1 |Mutant->| 13.25 | 13.5 | -50.1 |Step 4 : Selection
Now we have child and target. Compare the obj fn of both, see which is smaller(minimization problem). Select that individual out of the two for next generation
Clearly, the child is better so replace target(R1) with the child. So the new population will become
This procedure will be continued either till the number of generations desired has reached or till we get our desired value. Hope this will give you some help.
这是简化的描述。 DE 是一种优化技术，它迭代地修改候选解的群体，使其收敛到函数的最优值。
您首先随机初始化候选解决方案。然后，在每次迭代中，对于每个候选解决方案 x，您执行以下操作：
（请注意，上述算法非常简化；不要从中编码，而是在其他地方找到适当的规范）
不幸的是，维基百科文章缺乏插图。通过图形表示更容易理解，您可以在这些幻灯片中找到一些内容：http://www-personal.une.edu.au/~jvanderw/DE_1.pdf。
它与遗传算法 (GA) 类似，只是候选解不被视为二进制字符串（染色体），而是（通常）被视为实数向量。 DE 的一个关键方面是突变步长（参见突变的步骤 1）是动态的，也就是说，它会适应群体的配置，并且在收敛时趋于零。这使得 DE 比 GA 更不容易受到遗传漂变的影响。
Here's a simplified description. DE is an optimisation technique which iteratively modifies a population of candidate solutions to make it converge to an optimum of your function.
You first initialise your candidate solutions randomly. Then at each iteration and for each candidate solution x you do the following:
(Note that the above algorithm is very simplified; don't code from it, find proper spec. elsewhere instead)
Unfortunately the Wikipedia article lacks illustrations. It is easier to understand with a graphical representation, you'll find some in these slides: http://www-personal.une.edu.au/~jvanderw/DE_1.pdf .
It is similar to genetic algorithm (GA) except that the candidate solutions are not considered as binary strings (chromosome) but (usually) as real vectors. One key aspect of DE is that the mutation step size (see step 1 for the mutation) is dynamic, that is, it adapts to the configuration of your population and will tend to zero when it converges. This makes DE less vulnerable to genetic drift than GA.
回答我自己的问题...
概述
定义
NP候选者组成。Xi= 当前一代中索引i处的父候选（索引范围从0到NP-1） 。也称为目标向量。D参数。Xi(j)= 候选Xi中的第 j 个参数。Xa、Xb、Xc= 三个随机父候选者。(Xb - Xa)F= 决定种群进化速率的权重。CR= 发生交叉的概率。Xc`= 通过差分变异操作得到的变异向量。也称为供体载体。Xt=Xi和Xc`的子级。也称为试验向量。算法
for (int i = 0; ii）Xc` = Xc + F * (Xb - Xa)Xi中的每个变量，应用 概率均匀交叉CR继承自Xc`；否则，继承Xi。至少一个变量必须从Xc`继承Xt优于Xi，则Xt在下一代中取代Xi。否则，Xi保持不变。资源
Answering my own question...
Overview
Definitions
NPcandidates.Xi= A parent candidate at indexi(indexes range from0toNP-1) from the current generation. Also known as the target vector.Dparameters.Xi(j)= The jth parameter in candidateXi.Xa,Xb,Xc= three random parent candidates.(Xb - Xa)F= A weight that determines the rate of the population's evolution.CR= The probability of crossover taking place.Xc`= A mutant vector obtained through the differential mutation operation. Also known as the donor vector.Xt= The child ofXiandXc`. Also known as the trial vector.Algorithm
for (int i = 0; i<NP; ++i)i)Xc` = Xc + F * (Xb - Xa)Xi, apply uniform crossover with probabilityCRto inherit fromXc`; otherwise, inherit fromXi. At least one variable must be inherited fromXc`Xtis superior toXithenXtreplacesXiin the next generation. Otherwise,Xiis kept unmodified.Resources