基于小波基函数的差分进化算法缩放因子改进方法及应用

徐英杰,阎晓琳,邓 武

(1.大连交通大学 软件学院,辽宁 大连 116028；2.大连交通大学，机械工程学院，辽宁 大连 116028)

差分进化(differential evolution，DE)算法是一种基于自然界中种群进化过程的随机搜索算法[1].该算法采用实数编码，原理简单，易于理解和实现，具有较强的鲁棒性、控制参数少、搜索能力强，是一种简单高效的进化算法.近年来，在工程设计、运筹学、生物医学等众多领域取得了良好的应用效果，但是也容易出现早熟和陷入局部最优等问题.在进化过程，DE的控制参数(收缩因子、交叉概率等)需人工设置，这样每代种群的所有个体均采用相同参数，而适用于不同优化问题、不同进化阶段和不同个体的控制参数一般并不相同，因此如何为DE算法设计有效而可靠的参数非常重要.

近年来，诸多学者为了提高DE的性能而开展了大量工作.主要包括以下几方面：设计变异算子、自适应调整参数、引入有效搜索策略、结合其他优化算法、多策略多种群并行搜索等[2-10].Mallipeddi等[5]提出的改进DE算法(EPSDE)，该算法设置了不同的变异、交叉策略池和控制参数池，提高了算法的优化性能.Qin等[6]提出的一种自适应差分进化算法(SaDE)，设计了学习策略自适应，加快了算法的收敛速度，但学习过程较复杂.Wang等[7]提出了复合差分进化算法(CoDE)，该算法在3种不同变异策略中随机选取一种策略进行变异操作，产生后代个体，但不能根据前验自适应选择相关策略，缺乏必要学习过程.

因此，在对DE算法研究基础上，引入小波基函数，提出一种基于小波基函数的差分进化算法缩放因子改进方法.该方法采用小波基函数来改进DE缩放因子F，以保证解的多样性、加速算法收敛和提高算法性能.选择5个标准测试函数来验证改进DE算法的有效性.

1 差分进化算法

1.1 差分进化算法概述

差分进化算法是一种基于群体智能的启发式优化算法，利用个体之间的差异性，使算法在种群进化过程中进行随机搜索.其主要思想是将同一群体中2个不相同的个体向量进行差分操作，与该群体中的第3个个体向量做运算得到一个目标个体向量，然后目标个体向量与个体向量进行交叉生成试验个体向量；最后将试验个体向量与个体向量进行比较选择，适应度值小的个体向量进入下一代种群.差分进化算法的基本进化过程描述如下[11-12].

1.2 初始化

DE算法采用NP个D维向量作为初始解设种群数量N，每个个体可表示为xi(G)=(xi1(G),xi2(G),…,xiD(G)) ，初始种群在[xmin,xmax] 中产生：

xiD=xmin+rand(0,1)×(xmax-xmin),

(1)

其中，G表示第G代，xmax表示搜索空间的最大值，xmin表示搜索空间的最小值.rand(0,1)表示在(0,1)内的随机数.

1.3 变异

DE算法使用变异操作生成当前种群中的每个个体xi(G)的目标个体向量Vi(G) .对于生成的每个个体向量，通过一定的变异策略生成相应的目标个体向量.目前最常用的变异策略.

1)“DE/rand/1”:

Vi(G)=xr1(G)+F·(xr2(G)-xr3(G)),

(2)

2)“DE/best/1”

Vi(G)=xbest(G)+F·(xr1(G)-xr2(G)),

(3)

3)“DE/rand-to-best/1”

Vi(G)=xi(G)+F·(xbest(G)-xi(G))+F·(xr1(G)-xr2(G)),

(4)

4)“DE/best/2”

Vi(G)=xbest(G)+F·(xr1(G)-xr2(G))+F·(xr3(G)-xr4(G)),

(5)

5)“DE/rand/2”

Vi(G)=xr1(G)+F·(xr2(G)-xr3(G))+F·(xr4(G)-xr5(G)),

(6)

式中，索引r1,r2,r3,r4,r5是在[1,NP]内随机生成的不同整数.缩放因子F是差分向量的一个控制参数.xbest(G) 是群体在第G代中具有最佳适应度值的个体向量.

1.4 交叉

变异结束后，对每一个个体向量xi(G) 及其对应的目标个体向量Vi(G)进行交叉操作，生成对应的试验个体向量：Ui(G)=(u1(G),u2(G),…,ui(G)) .使用二项交叉定义如下：

(7)

其中，交叉率CR是(0,1)之间指定的常数，jrand是[1,D]内随机的随机整数.

1.5 选择

计算试验个体向量Ui(G)和对应的个体向量Xi(G)的适应度值，进行比较并执行选择操作.将每个试验向量的适应度值f(Ui(G))与当前种群中相应的个体向量的适应度值f(Xi(G))比较，如果试验个体向量的适应度值小于或等于相应的个体向量适应度值，则试验个体向量取代对应的个体向量，进入下一代种群.选择操作可以表示为：

(8)

2 基于小波基函数的差分进化算法缩放因子改进方法

当所优化求解的目标不同时，需要建模的数学特征也不相同，使DE算法具有不同的搜索步长.当解距离最优点较远时，较长搜索步长有利于算法收敛到最优解空间，而当解距离全局最优点较近时，较小搜索步长有利于算法准确找到更优解[13].因此，DE算法缩放因子F与搜索步长密不可分.因此DE算法缩放因子F的选择至关重要.

针对DE算法缩放因子F选择问题，充分利用小波基函数的特点，提出一种基于小波基函数的差分进化算法缩放因子改进方法，有效实现DE算法缩放因子F的改进.常用小波基有Haar小波、Daubechies(dbN) 小波、Mexican Hat(mexh)小波、Morlet小波、Meyer小波等[14].由于Mexican Hat(mexh)小波Mexican Hat函数为Gauss函数的二阶导数，具有在时间域与频率域都有很好的局部化的特点.因此，DE算法缩放因子F的改进策略如下：

(9)

采用Mexican hat(mexh)小波改进的DE算法缩放因子F，其值在(0,1)之间随机取值，求解不同的问题时能够取得所需的搜索步长，即控制因子F的值，使算法避免出现早熟，防止收敛到局部最优，同时也增加了解的多样性.DE算法缩放因子F的取值，见图1所示.

改进DE算法详细步骤描述如下.

Step 1 在(xmin,xmax) 中随机产生初始种群，并初始化参数，种群大小NP=100，维数D=30，最大迭代次数Gmax=2000；初始迭代次数G=1.

Step 3 进行变异操作，对每个个体向量Xi(G) 用变异策略产生对应的目标个体向量Vi(G) .

Step 4 进行交叉操作，在(0,1)中产生随机数与交叉率CR比较，若小于CR，选取步骤三产生的目标个体向量Vi(G)作为试验个体向量Ui(G)，反之，选取当代的个体向量Xi(G) 作为试验向量Ui(G) .

Step 5 进行选择操作，计算目标个体向量Xi(G)和试验个体向量Ui(G)的适应度值，进行比较，选取适应度值小的作为Xi(G+1)并进入下一代种群中.

Step 6 若达到最大迭代次Gmax=2 000，输出最优值，否则跳到Step 2.

3 实例验证与分析

3.1 测试函数的选择

为了验证改进DE算法的有效性，选择5个测试函数对算法进行了测试，5个函数描述见表1.并与标准DE算法5种策略进行了比较.其中f1～f3是单峰函数，主要用于评价算法精确度、收敛速度等，f4～f5是多峰函数，主要用于评价算法的全局搜索性能和稳定性[15].算法的参数设置，见表2所示.

表1 测试函数描述

表2 改进DE算法参数设置

3.2 实验结果

5个测试函数的测试结果及其比较，见表3所示，并且最优值、平均值和标准差被用来评价算法的有效性.5个测试函数的迭代曲线，见图2所示.

表3 实验结果对比分析

3.3 结果分析

从表3可以看出，对于求解的5个测试函数，改进的DE算法有较好的最优值、平均值和标准差，说明改进的DE算法具有较好的稳定性和较强的寻优能力.从图2可以看出，对于测试函数f1，改进的DE算法在迭代初期就表现出了良好的优化性能，迭代曲线下降快，精度高.对于测试函数f2，改进的DE算法表现出相对较好的优势，在整个迭代过程中，寻优能力强.对于测试函数f3，无论在寻优能力还是在收敛性方面，改进的DE算法优于其它策略.对于测试函数f4和f5，明显可以看出改进的DE算法优化效果极优.从图2总体可知，对于测试函数f1～f3，改进的DE算法收敛曲线下降速度较快，能快速趋向于函数最优值.对于测试函数f4～f5，可以看出改进的DE算法曲线拐点较多，说明改进的DE算法不断跳出局部最优值，逐渐趋向于全局最有值.

综上所述，在DE算法参数缩放因子F不同的情况下，算法存在较大的性能差别，DE算法参数选取不当很可能无法获得满意的结果.而改进DE算法避免固定参数选择的不足，具有局部搜索能力和全局搜索能力.

4 结论

针对差分进化算法在求解复杂优化问题时存在的收敛性和开发能力较差以及控制参数难以确定的不足，引入小波基函数来控制DE算法参数F，提出了基于小波基函数的差分进化算法缩放因子改进方法，保证了解的多样性、加速了收敛速度和提高了算法优化性能.从实验来看，无论对于单峰函数还是多峰函数，改进DE算法都有很好的适应能力，表现出较强的寻优能力和较好的收敛性能.