2.2 差分进化算法基本原理

2.2.1 算法原理及关键步骤

DE算法主要用于求解连续变量的全局优化问题，其主要工作步骤与其他进化算法基本一致，主要包括变异（Mutation）、交叉（Crossover）、选择（Selection） 3种操作。算法的基本思想是从某一随机产生的初始群体开始，利用从种群中随机选取的两个个体的差向量作为第三个个体的随机变化源，将差向量加权后按照一定的规则与第三个个体求和而产生变异个体，该操作称为变异。然后，变异个体与某个预先决定的目标个体进行参数混合，生成试验个体，这一过程称为交叉。如果试验个体的适应度值优于目标个体的适应度值，则在下一代中试验个体取代目标个体，否则目标个体仍保存下来，该操作称为选择。在每一代的进化过程中，每一个体矢量作为目标个体一次，算法通过不断地迭代计算，保留优良个体，淘汰劣质个体，引导搜索过程向全局最优解逼近[5]。

下面以求解非线性函数最小化问题为例，详细说明 DE 算法的基本操作。将非线性函数最小值问题表示为minf(X),XL≤X≤XU,XL和XU分别是变量X=(x1,x2, …,xn)取值的上界和下界，n为变量维数。利用DE算法求解该非线性函数最小值问题时，首先在取值范围内生成包含NP个个体的初始种群，每个个体对应可行解空间中的一个候选解，且个体变量的维数D等于目标函数决策变量X的维数n。假设算法最大迭代次数为G，则第t代种群中的第i个个体可表示为Xi(t)=(xi1(t),xi2(t), …,xin(t)),i=1, 2, …,NP。每一代进化过程中，种群通过变异、交叉、选择操作更新种群个体，将变异操作生成的变异个体表示为Vi(t)=(vi1(t),vi2(t), …,vin(t))，而交叉操作生成的试验个体表示为Ui(t)=(ui1(t),ui2(t), …,uin(t))。以下对DE算法中的关键步骤进行说明。

1.种群初始化

设置初始进化代数t=0，在优化问题的可行解空间内按式（2-1）随机产生满足约束条件的NP个个体X构成初始种群，NP的选取一般在s5n与10n之间。

其中，Xi(0)表示第0代种群中的第i个个体；rand()为[0,1]区间上的随机数。

2.变异操作

变异操作是DE算法中的关键步骤，也是其与其他进化算法的主要区别所在。DE算法最基本的变异成分是父代的差分矢量，每个差分矢量对应父代种群中两个不同个体的差向量，差分矢量定义见式（2-2）。

其中，r1和r2表示父代种群中两个随机选择的不同个体的索引号。将差分矢量Dr1,2加权后与另一个随机选择的父代个体矢量求和就生成了一个子代变异个体矢量。对于当前第t代种群中每一目标个体矢量Xi(t)，其对应的变异操作见式（2-3）。

其中，r1,r2,r3∈{1, 2, …,NP}为随机选取的互不相同的正整数，且r1,r2,r3与当前目标个体矢量索引号i不同，由此可见，DE算法的种群规模必须大于4，否则将无法进行变异操作。Vi(t+1)为目标个体矢量Xi(t)对应的变异个体矢量，Xr3(t)称为基向量，F∈[0, 2]为常数，是DE算法的主要控制参数之一，称为变异因子或缩放因子，控制差异矢量的缩放幅度，也即对基向量影响的大小。

由此可见，DE算法的变异个体是通过把种群中两个体之间的加权差向量加至基向量上产生的，相当于在基向量上附加了一个随机偏差扰动。由于3个个体都是从父代种群中随机选取，因此父代个体之间存在多种组合方式，保证了DE算法良好的种群多样性。进化早期种群个体之间的差异较大，使得差分矢量对基向量的扰动较大，保证了DE算法前期种群较强的勘探能力和个体全局搜索能力。随着进化迭代次数的增加，群体个体之间的差异度减小，使得DE算法后期种群开采能力和个体局部搜索能力加强，有助于加快收敛速度。图2-1所示为目标函数为二维时的DE算法变异操作示意。

3.交叉操作

为进一步增加种群多样性，DE 算法将目标矢量个体Xi(t)与其对应的变异个体Vi(t+1)进行交叉操作，产生试验个体，即目标个体的候选个体Ui(t+1)。为保证目标个体Xi(t)的进化，必须保证试验个体Ui(t+1)中至少有一维分量由变异个体Vi(t+1)贡献，而其他维分量则由交叉概率因子CR决定。由此试验个体中每一维分量uij(t+1)按式（2-4）生成。

其中，xij(t)表示父代种群中目标个体矢量Xi(t)中的第j维分量，vij(t+1)为变异个体Vi(t+1)中的第j维分量，其中i=1,…,NP,j=1,…,D。rand(j)∈[0,1]为第j维分量对应的随机数。交叉概率因子CR∈[0,1]是DE算法的另一个主要控制参数，它决定了变异个体Vi(t+1)在生成的试验个体Ui(t+1)中所占的比例。k为第i个个体对应的系数，一般是从序列[1, 2, …,D]中随机选择的一个整数，用来确保候选个体Ui(t+1)中至少有一维分量来自变异个体Vi(t+1)。

交叉操作的过程示意如图2-2所示，由图2-2可见，当第j维分量对应的随机数rand(j)小于等于交叉概率因子CR或者当前维数j等于预定系数k时，试验个体Ui(t+1)中相应维分量均来自于变异个体Vi(t+1)，否则相应维分量仍于父代种群中目标个体矢量Xi(t)相同。

交叉操作实质上是变异操作的进一步延续和调控，通过混合变异个体和目标个体相应维分量实现种群个体的进化。此外，交叉操作通过参数CR控制试验个体中来自变异个体的更新成分，若更新成分在试验个体中占比较大，则个体进化程度较高，反之则进化程度较低，由此控制种群个体进化的程度。由上述分析可知，交叉操作对DE算法收敛速度、求解精度等性能的影响应与变异操作遵循同一趋势。

4.选择操作

和其他进化算法一样，DE 算法采用“优胜劣汰”的选择操作来保证算法不断向全局最优解进化。选择操作中首先对试验个体Ui(t+1)和目标个体Xi(t)进行适应度评价，评估个体对应于待求最优化问题的优劣的相对值大小，再将二者的适应度值进行比较，按式（2-5）选择适应度值较优的个体进入下一代。

通过以上的变异、交叉和选择操作，种群进化到下一代并反复循环，直到算法迭代次数t达到预定的最大迭代次数G，或种群的最优解达到预定误差精度时算法结束。

在使用DE算法时有3个控制参数需要提前设定。

① 种群规模NP，即群体中所含个体数量，一般由用户根据需要决定，NP越大，种群多样性越强，获得最优解的概率越大，但相应计算时间也更长；

② 变异因子F，取值0～2，一般初始值取0.5；

③ 交叉概率CR，取值0～1，一般初始值取0.4。

这3个参数对算法的求解结果和求解效率都有较大影响，因此需要合理设置，具体设置原则将在2.4节中详细说明。

2.2.2 算法框架及流程

图2-3是DE算法的工作过程示意，详细说明了算法中种群个体经历变异、交叉和选择操作生成新一代种群个体的操作过程。

①选择目标向量和基向量。

②随机选择2个种群个体。

标准DE算法的运算流程如图2-4所示。