3.2 差分进化算法的不同形式

差分进化算法发展至今，人们在基本形式的基础上不断改进，提出了多种其他形式和改进形式。这些不同形式的差分进化算法差别主要体现在变异操作和交叉操作上，为不同的使用者提供了更多的选择空间。

3.2.1 差分进化算法的基本形式

差分进化算法的基本形式又称为基本差分进化算法、标准差分进化算法或简单差分进化算法。该形式不仅是本章研究的重点，也是学习其他形式的基础。基本差分进化算法核心构成要素和主要操作包括种群初始化、变异操作、交叉操作、选择操作和边界条件处理等。

1.种群初始化

假设差分进化算法的种群数量为NP，求解问题的维数为 N ，种群中所有个体表示为 X =[ X ₁ ， X ₂ ，…， X _NP ] ^T ，个体的位置向量表示为 X _i =[ x _{i ，1} ， x _{i ，2} ，…， x _{i ， N} ]， i =1，2，…，NP。利用求解问题的目标函数构建用于个体评价的适应度函数，计算种群中所有个体的适应度函数值fit _i =fit（ X _i ）， i =1，2，…，NP。对于最大值优化问题，可直接使用目标函数作为适应度函数；对于最小值优化问题，需要对目标函数进行适当转换，将最小值优化问题转换为最大值优化问题。

在算法进化迭代开始时，需要给定种群中所有个体的初始位置。通常采用随机初始化种群位置的方式，使所有个体都随机分布在求解问题的搜索空间中。种群中第 i 个个体的初始位置可记为 X _i （0）=[ x _{i ，1} （0）， x _{i ，2} （0），…， x _{i ， N} （0）]，各分量取值为

式中，rand为均匀分布随机数，rand∈[0，1]； x _{n ，max} 为第 n 维自变量的取值上限； x _{n ，min} 为第 n 维自变量的取值下限。

从式（3-1）不难看出，当rand=0时， x _{i ， n} （0）= x _{n ，min} ；当rand=1时， x _{i ， n} （0）= x _{n ，max} 。通过随机数rand的不同取值，可使 x _{i ， n} （0）在[ x _{n ，min} ， x _{n ，max} ]内随机均匀分布。当然，如果可以预先估计到问题最优解的大体位置，也可以在最优解附近给定种群的初始位置。这种利用先验知识给定初始位置的方法，有利于缩短搜索时间，提高算法的收敛速度。

2.变异操作

对于当前个体 X _i （ t ），从当代种群中选择若干父辈个体进行变异操作，产生中间个体对应的合成向量 V _i （ t +1），在基本差分进化算法中变异操作的具体方法如下：

式中， 、 和 为从种群中随机选择的三个个体， 为被选择进行变异的个体， 和 为被选择进行差分操作的个体， r ₁ 、 r ₂ 和 r ₃ 互不相同，且与当前个体的序号 i 也都互不相同，所以种群数量要满足NP≥4；变异因子或缩放因子 F ∈[0，2]是一个实常数，用来控制对差分向量的放大比例。

由式（3-2）可见， 和 的差 称为二者的差分向量，变异因子 F 作为权重，实现对差分向量的缩放控制， 称为加权差分向量或扰动向量。将扰动向量加到被变异个体对应的基点向量 上，就相当于 受到了扰动向量的干扰产生变异，产生中间个体对应的合成向量 V _i （ t +1）。正是由于中间个体的产生方法用到了父辈个体的差分运算，同时借鉴了遗传算法模拟生物进化过程中的变异操作、交叉操作和选择操作等概念，故称为差分进化算法。

3.交叉操作

为了保持种群的多样性，在差分进化算法中引入交叉操作，产生候选个体对应的试验向量 U _i （ t +1），由中间个体对应的合成向量 V _i （ t +1）和当前个体对应的目标向量 X _i （ t ）进行交叉产生。目前常用的交叉方式有二项式交叉和指数交叉。

（1）二项式交叉。二项式交叉即采用伯努利（Binomail）试验方式来进行交叉操作，如图3-1所示，具体方法如下：

式中，rand为均匀分布随机数，rand∈[0，1]； P _c 为交叉概率或交叉因子， P _c ∈[0，1]；randi为随机整数，randi∈[1， N ]用来确保 u _{i ， n} （ t +1）中至少从 v _{i ， n} （ t +1）中获得一个分量。

（2）指数交叉。指数交叉方法如下：

式中， n _start 为交叉起点位置， n _end 为交叉结束位置。在中间个体的合成向量中随机找到一个起点位置 n _start ，从 n = n _start 开始，如果生成的随机数满足rand≤ P _c ，则 n = n +1，连续进行上述操作，直到在某个分量位置出现rand＞ P _c 或到达向量尾部为止，此时 n = n _end ，则试验向量 U _i （ t +1）对应位置分量就从合成向量 V _i （ t +1）中抽取这一段连续的对应位置分量，其他位置分量取目标向量 X _i （ t ）对应位置的分量，如图3-2所示。

4.选择操作

候选个体 U _i （ t +1）与当前个体 X _i （ t ）进行“一对一”方式的贪婪竞争选择，形成进入下一代的新种群，实现优胜劣汰和种群进化。选择操作方法是通过比较 U _i （ t +1）与 X _i （ t ）的适应度函数值，选取适应度函数值较大的个体进入下一代种群，即

式中，fit[ U _i （ t +1）]为 U _i （ t +1）的适应度函数值；fit[ X _i （ t ）]为 X _i （ t ）的适应度函数值。

差分进化算法将候选个体与当前个体进行比较后择优选取，保证了下一代种群中的所有个体都比当代种群中的对应个体更佳或至少不差。需要注意的是，在基本差分进化算法的选择操作中，新产生的候选个体只与当前个体本身相比较，而不与当前种群中的所有个体相比较。因此，基本差分进化算法采用了“一对一”方式的贪婪竞争选择策略，而不是群体竞争选择策略。这种贪婪选择策略在进化过程中必然会过早淘汰一些较好的优质个体。

5.边界条件处理

在有边界约束的优化问题中，必须保证试验向量 U _i （ t +1）中的参数值处于求解问题限定的搜索范围内。如果试验向量 U _i （ t +1）中存在参数值超出边界的情况，则必须进行边界条件处理，也就是防越界处理。常用的边界条件处理方法如下。

（1）随机替代法。将试验向量 U _i （ t +1）中超出边界约束的参数值用在搜索范围内随机产生的参数值替代。若 u _{i ， n} （ t +1）＜ x _{n ，min} 或 u _{i ， n} （ t +1）＞ x _{n ，max} ，那么

式中，rand为均匀分布随机数，rand∈[0，1]； x _{n ，max} 为第 n 维自变量的取值上限； x _{n ，min} 为第 n 维自变量的取值下限。

（2）边界吸收法。将试验向量 U _i （ t +1）中超出边界约束的参数值直接设置为临近的边界值，即

（3）镜像对称法。将试验向量 U _i （ t +1）中超出边界约束的参数值以边界为对称轴进行镜像处理，得到符合边界约束的取值，即

事实上，如果候选个体的试验向量 U _i （ t +1）中出现参数值超出边界的情况，也是由于变异操作产生中间个体的合成向量 V _i （ t +1）中出现参数值超出边界引起的。因此，边界条件处理既可以针对试验向量 U _i （ t +1），也可以针对合成向量 V _i （ t +1）。但对试验向量 U _i （ t +1）进行边界条件处理，可以忽视在交叉操作中未被选中合成向量 V _i （ t +1）中参数值超出边界条件的情况，有利于减少不必要的计算。

3.2.2 差分进化算法的其他形式

在基本差分进化算法的基础上，由于采用的变异操作和交叉操作不同，还发展出了差分进化算法的其他形式。这些差分进化算法的形式统一用符号“DE/ x / y / z ”加以区分，其中， x 表示变异操作中被变异个体的选择方式，可以为“rand”“best”或“current”，“rand”表示从种群中随机选择的一个个体，“best”表示当前最优个体，“current”表示当前个体； y 表示所用差分向量的个数； z 表示交叉操作的方式，可以为“bin”或“exp”，“bin”表示采用二项式交叉，“exp”表示采用指数交叉。利用上述命名规则，基本差分进化算法可描述为DE/rand/1/bin，而目前差分进化算法常用的其他形式还有以下几种。

（1）DE/best/1/bin，其中变异操作公式为

式中， X _best （ t ）为当前最优个体； 和 为从种群中随机选择的两个个体， r ₁ 和 r ₂ 互不相同，与 i 和best也都互不相同。

（2）DE/rand/2/bin，其中变异操作公式为

式中， 、 、 、 和 为从种群中随机选择的五个个体， r ₁ 、 r ₂ 、 r ₃ 、 r ₄ 和 r ₅ 互不相同，与 i 也都互不相同； λ 和 F 一样，也是一个实常数变异因子。

（3）DE/best/2/bin，其中变异操作公式为

式中， X _best （ t ）为当前最优个体， 、 、 和 为从种群中随机选择的四个个体， r ₁ 、 r ₂ 、 r ₃ 和 r ₄ 互不相同，与 i 和best也都互不相同。

（4）DE/current-to-best/1/bin，其中变异操作公式为

式中， X _i （ t ）为当前个体； X _best （ t ）为当前最优个体； 和 为从种群中随机选择的两个个体， r ₁ 和 r ₂ 互不相同，与 i 和best也都互不相同。

上述四种形式各有各的特点，但Rainer Storn和Kenneth Price经过大量实验研究表明，DE/rand/1/bin和DE/best/2/bin的性能较其他方式要好，实际应用也最多。如果采用指数交叉，又会得到另外五种其他形式，具体可写成：DE/rand/1/exp、DE/best/1/exp、DE/rand/2/exp、DE/best/2/exp、DE/current-to-best/1/exp。

3.2.3 差分进化算法的改进

作为一种高效的并行优化算法，差分进化算法发展很快，出现了很多改进的差分进化算法。下面主要介绍自适应差分进化算法和离散差分进化算法。

1.自适应差分进化算法

在基本差分进化算法中，变异因子和交叉概率取常数。通常情况下，良好的搜索策略应该是在搜索初始阶段保持种群多样性，尽可能进行全局搜索，避免过早限于局部最优，而在搜索后期应加强局部搜索能力，以提高算法的求解精度。为此可以采用能够动态调整的变异因子和交叉概率。

1）动态变异因子

变异因子取值太大，扰动量增大，可能导致算法搜索效率低下，求得全局最优解精度降低；变异因子取值太小，扰动量减小，又容易使种群多样性降低，陷入局部最优，出现“早熟”现象。因此，可根据算法搜索进展情况动态调整变异因子。比如，将动态变异因子设计成如下形式：

式中， F ₀ 为变异因子系数； a 为幂底数； λ 为幂指数； t 为进化代数； G 为最大进化代数。当 F ₀ =0.2， a =2，3，4，5， G =500时，动态变异因子变化曲线如图3-3所示。

由图3-3可见，在算法开始时自适应变异因子近似为 aF ₀ ，随着算法进化代数增加，变异因子逐步降低，到进化结束时近似为 F ₀ 。相当于差分向量的权重由大变小，在算法前期有助于加速向最优解靠拢，而在算法后期有助于在最优解附近细致搜索。

2）动态交叉概率

在交叉操作中，交叉概率也可设计成动态变化的。例如，随着进化代数的增加，交叉概率由小变大，将动态交叉概率设计成如下形式：

式中， t 为进化代数； G 为最大进化代数； P _c，min 为最小交叉概率； P _c，max 为最大交叉概率。

式（3-14）中交叉概率 P _c 随着进化代数的增加，从 P _c，min 线性增大到 P _c，max ，搜索初始阶段目标向量对试验向量的贡献大，而到了搜索后期，合成向量对试验向量的贡献大。而式（3-15）中交叉概率 P _c 随着进化代数的增加，从 P _c，max 线性减小到 P _c，min ，搜索初始阶段合成向量对试验向量的贡献多，而到了搜索后期，目标向量对试验向量的贡献多。

动态交叉概率也可设计成如下形式：

式中，rand为均匀分布随机数，rand∈[0，1]。这样交叉概率随机变化，但平均值保持在0.75，可使差分向量产生的扰动也随机变化，有助于在搜索过程中保持种群的多样性。

2.离散差分进化算法

差分进化算法是一种在连续变量空间求解优化问题的有效方法，但要将其应用于求解整数规划或混合整数规划问题，必须对差分进化算法进行改进。如对变异操作增加取整运算，使之变为整数变量，就能在整数空间进行搜索寻优，即

式中，floor(·)表示沿-∞方向取整；ceil(·)表示沿+∞方向上取整；round(·)表示四舍五入取整。 dU2Y4oz/ANMIw47gsk3CLz6JDLSZv1Fi3EgJYf4lnpXEIBlXllg40uNczyhC63h4