1.2 差分进化算法介绍

差分进化（Differential Evolution，DE）算法是由Storn与Price在1995年提出的一种社会性的、基于种群的寻优算法。差分进化算法属于进化算法（Evolutionary Algorithm，EA）的子领域，也是简单但很有效的随机进化算法。与其他随机优化进化算法类似，DE算法采用了与标准进化算法类似的计算方法步骤，主要通过变异（Mutation）、交叉（Crossover）和选择（Selection）3种操作进行智能搜索。但与传统的进化算法有所不同，DE算法通过随机选择不一样的个体生成比例差分向量扰动当代种群，并运用与候选解之间的差别产生新的个体。与其他进化算法相比，DE算法具有结构简单（该算法只有3个控制参数）、容易实现（Matlab实现的核心的代码仅有几十行）、全局搜索性能好、稳健性强等优势[7]。

DE算法需要经过个体的初始化、变异、交叉和选择4个基本流程。个体经过初始化操作之后，由差分进化算法中最重要的差分变异（Differential Mutation）算子将同一种群中的2个个体进行差分和缩放，并且加上该种群内另外的随机个体向量来产生变异个体向量（Mutant Vector），然后父代个体和变异个体的向量采用交叉操作获得实验个体向量（Trial Vector），最后比较实验个体向量和父代个体向量的适应度值，将较优者保存到进化的下一代中。DE算法利用差分变异、交叉和选择等方式不停迭代地对种群进行演变，直到满足停止的要求为止。

（1）个体的初始化

传统的DE算法采用实数编码，更加适宜处理实数优化问题。DE算法保持了一个规模为（NP，D）的实参类型种群（NP为种群大小，D为决策变量的个数），其中第i个个体xi如式（1-1）所示。

016-1

其中，xi,j∈[Lj,Uj]。在种群初始化之前，确定参数的上界Uj和下界Lj，xi,j在[Lj,Uj]内随机均匀初始化，如式（1-2）所示。

016-1

其中，函数randj(0,1)表示从区间[0,1)随机选择一个数，j表示在第j维上产生的随机数。

（2）差分变异操作

DE算法正因为差分变异操作而得名，通常统一采用“DE/a/b”的形式表示，其中，“DE”表示差分进化算法；“a”表示挑选被变异个体的方式，常运用“rand”和“best”两种方式，“rand”为从种群中任意挑选个体向量，“best”为挑选当前适应度最优的个体向量；“b”表示在变异流程内采用的向量的数目。在变异过程中，个体xi,G可采用变异策略产生变异向量vi,G，被广泛采用的5种变异策略具体如式（1-3）～（1-7）所示。

016-1
016-1

其中，r1、r2、r3、r4和r5为{1,…,NP}之间随机选择的5个互不相等的整数，xbest,G为在当前G代中具备最好适应度函数值的向量，缩放因子F为在区间[0,1]的加权差分向量的控制参数。

在变异操作中，DE算法要判断差分变异产生的新向量是否能保证变异向量在搜索的空间范围内。如果变异向量不在搜索空间内，则要通过运用修复操作对变异向量进行处理，通常连续向量采用式（1-8）或式（1-9）所示方法进行处理。

016-1

其中，016-1表示变异向量v第G代中第i个向量的第j维的值。

（3）交叉操作

为了进一步完善差分变异搜索流程，DE算法运用了交叉方法，该方法包括二项式交叉（Binomial Crossover，BIN）和指数交叉（Exponential Crossover，EXP），其中二项式交叉如式（1-10）所示。

016-1

其中，016-1表示实验向量U中第G代的第i个向量的第j维的值。jrand表示从{1,2,…,D}中随机选择的一个数。CR表示交叉概率。

当进行指数交叉操作时，开始在[1,D]任意挑选整数n，作为进行交叉的开始位置，另一个整数L再在[1,D]随机挑选，L代表变异向量占目标向量位置的数量。利用上述方法选定n和L，最终进行指数交叉产生实验向量的值016-1。指数交叉如式（1-11）所示。

016-1

其中，<·>D表示对D取模函数，整数L按如下伪代码生成。

生成整数L的伪代码
L=0;
do {
L=L+1;
} while (rand(0,1)≤CR&L≤D)

（4）选择操作

DE算法经过差分变异和交叉进化流程后，采取选择操作把实验向量与目标向量进行对比。若实验向量ui,G的适应度函数值小于或等于目标向量xi,G的适应度函数值，那么实验向量取代相应的目标向量，从而获得进入下一代的机会；反之目标向量就一直维持到下一代进化过程。最小化优化问题中的选择操作可以作如式（1-12）所示的描述。

016-1

其中，f(xi,G)是计算出的第G代个体xi,G适应度目标的函数值。

总之，DE算法的一次进化过程包含了初始化种群、变异、交叉和选择4个基本步骤。DE算法的伪代码如下。

初始化种群规模NP，缩放因子F和交叉概率CR，设定进化代数G=0；
执行初始化操作，产生和初始化有NP个个体的种群X，并评估适应度f(X)；
while停止条件非真do
for种群中的每个个体xi,G ∈ XG do
根据差分变异策略生成差分变异向量vi,G；
判断差分变异向量是否在搜索空间范围内，如不在，则采用修复操作；
通过交叉策略得到实验向量ui,G；
通过选择操作，确定下一代种群中的个体xi,G+1；
end For
G=G+1;
end while
返回最佳适应度的个体xbest,G；
上一章目录下一章