带局部搜索的自适应动态差分进化算法

，

(天津石油职业技术学院 资源勘查系，天津 301607)

差分演化算法[1、2]是于1995年由R.Storn和K.Price提出来的一种演化算法。该算法和其他进化类算法主要的不同在于差分变异的使用。 DE 与人工生命,特别是进化算法有着极特殊的联系。DE 和微粒群算法一样,都是基于群体智能理论的优化算法,通过群体内个体间的合作与竞争产生的群体智能指导优化搜索。但相比于其他进化算法，DE 算法简单、鲁棒性高、易于程序实现、全局收敛能力强。 但是其随机性又导致其收敛速度慢，本文提出了利用单纯形搜索的方法将群体中较差部分通过单纯形搜索进行优化后再进行差分进化的方法，使得进化速度有了较大的提高[3]。对于差分进化算法来说，差分比例因子F,和交叉概率因子CR都在很大程度上影响了差分进化算法的性能。因此本文提出了一种自适应的差分进化算法，使得进化速度有了较大的提高，同时保留了DE全局搜索的优越性。针对此，本文提出了一种自适应参数的差分进化算法。

一、 差分进化算法和改进的单纯形搜索算法

(一) 基本差分进化算法

差分进化算法采用的选择、交叉和变异这三种基本差分操作是算法的基础。构成差分进化算法的要素主要有：个体适应度评价，差分操作和参数设置。

1. 适应度函数

在差分进化算法中，差分操作主要通过适应度函数(fitness function)的导向来实现的，它是用来评估个体相对于整个群体的优劣的相对值的大小。通常根据具体问题定义适应度函数。

2. 差分进化算法的主要操作

在迭代过程中,每一代G的种群中都包含 N 个个体，这个种群可以用 N个D维的参向量来表示： XiG=(X1,……Xn)对于每个个体进行如下操作：

变异操作：变异操作指算法按照这种策略从父代种群中生成新个体进入中间代。通过式(1) 对每一个个体XiG实施变异操作,得到与其相对应的变异个体VGi=(c1,c2，……cn)

VGi=Xr1+F·(Xr2-Xr3)

(1)

这里r1、r2 和r3是从区间[1 N]上随机选取的互不相同的整数，且不同于下标指数I,变异因子F是[0 2]上的一个实常数，其主要作用是控制差分向量的放大程度。

其中

选择操作：如果新个体X′r优于父代个体Xr，则用X′r来替换Xr，否则保持不变。在差分进化算法中，选择操作采取的是贪婪策略，即只有子代个体优于父代个体时才被保留，否则，父代个体会被保留至下一代。

(二) 单纯形改进局部搜索算法

首先从群体中选择适应值较优的N1个个体作为学习对象，计算质心(式3)，较差的N2=N- N1个个体作为搜索对象，按照流程(图1)对每个个体进行搜索。

二、自适应单纯形差分进化算法

(一) 改进方法

由差分进化算法变异算子(式1)和交叉因子(式2)的随机性使得此算法具有全局搜索，鲁棒性好的特点，但同时也导致了算法收敛速度慢。为了改善其收敛速度，本文提出了使用单纯形快速搜索的方法，利用较好群体形成的单纯形质心对较差个体进行初步优化改进后再用于差分进化，加快算法的收敛。但本文方法与传统的单纯形搜索不同，在每次搜索，不是针对最差个体进行的，而是对每个个体以最佳群体的质心为质心进行优化，这样使每个个体质心或最优个体学习，比传统只针对最差个体提高了搜索的范围，改善了算法的收敛速度(见图1)。

图1 改进的单纯形搜索算法流程(图中X为质心; Xb为群体最优个体)

当群体最好适应值和最差适应值不等时使用文献[3]介绍的方法使用个体信息动态更新F(式4)，差分向量适应能力较近时，F的绝对值较小，使得变异个体VGi相对基向量Xr1变化较小反之变异个体VGi相对基向量Xr1变化较大。概率选择因子使用二项分布模型(式5)进行动态更新。

(二)算法的流程

综上所述，此差分进化算法的约束处理技术的流程可表示如下：

step1. 随机生成群体规模都为N(N1+N2)的种群。

step2. 然后按照适应值大小进行从小到大排序，然后将最优的前N1个优秀个体和底部N2个较差个体分别组成群体X(N1个)和Y(N2)。

step3. 生成X群体的质心，对Y群体进行单纯形搜索，得到较优的个体群Y。

step4. 合并X群体和Y群体为P。

step5. 获得初始化群中最佳个体适应值和最差个体适应值及参数CR。

step6. 随机从P个个体中选择3个与生成的变异个体Vi序号i不同的个体，通过式2计算F值。

step7. 变异算法(式1)。

step8. 交叉算法。按照(2)式进行交叉，生成新的实验个体Vi。

step9. 选择操作。如果新个体Vi优于父代个体Xi、则用Vi来替换Xi，否则保持不变。

step10. 判断是否达到结束搜索条件，如果则输出最佳个体Gbest，否则转向step2

三、数值试验

本文选择9个不同特点的基函数(表1)，维数都为30，在Matlab7环境下进行了算法的实验与验证。

其中f1、f2为只有一个极小值单峰函数，f3-f8为具有无数个局部极小值的多峰函数。本文为验证SADCDE算法的优越性，与标准差分进化算法DE/rand/1及文献[5]算法SADE及文献[4]的算法FEP 、 CEP进行了比较(表2)。为了比较的公平性，SADCDE算法参数设置与文献[5]TABLE III中数据一样。群体规模NP设为100 , 评估次数设为1500。SADCDE算法对表1中9个具有代表性的测试函数分别独立运行50次,求解结果的平均最优值、最优值方差分别和DE、SADE、LEP和BestLevy四种算法进行了比较。表2中除了SADCDE算法外其它算法实验数据都来源于文献[5]。

表1 维数D为30的函数f 1 - f9搜索区间及全局最优值

从表2可看出，相对于其它函数SADCDE具有很明显的优势：对于一个简单的超球面函数f1(Sphere函数),SADCDE具有很明显的优势，其次是SADE、DE算法，但都优于LEP和BestLevy的算法，相同的评估次数,得到了精度更高的解和更小的方差。对于Quadric函数f2，SADCDE算法具有明显的优势，最小适应值求解精度远好于其它四种算法，而且SADE好于DE算法，DE算法好于LEP和BestLevy算法。对于函数f3，SADCDE与SADE算法有相同的精度，都能够求解出全局最大值，好于DE和LEP、BestLevy算法。函数f4和f5是被经常用来测试进化算法全局搜索能力的Rastrigin 函数和Griewank 函数，有许多局部最小点,对于f4函数，只有SADCDE算法得到了全局最小值点，SADE算法精度较高但没有求出全局最小值点。对于函数f5，SADCDE算法和SADE算法都搜索到了全局最小值点，其它算法没有搜索到。f6为有噪音的函数, 有多个局部最优解[6,7],同样SADCDE算法和SADE算法的搜索精度好于其它三种算法，SADCDE算法略好于SADE算法。具有罚项的测试函数f7 和f8，具有多个局部最优解，五种算法中只有SADCDE算法求出了全局最优解，而其它算法都没有求出最优解。

为了比较说明本文SADCDE算法的全局收敛性，本文使用SADCDE算法与文献[5]中的SADE算法、DE算法进行了进化图上得比较(如图2),群体规模NP都设为100,最大迭代次数都为1500，SADCDE算法初始F值设为0.5，CR为0.1，对于DE算法,F为0.5，CR设为0.1。SADE算法(详见文献5)Fl为0.1，Fu为0.9，τ1=τ2=0。

表2 SADCDE算法与DE、SADE、LEP、Bestlevy算法的比较

从图2中分析：对于单峰函数f1和f2。SADC-DE无论在收敛速度还是全局搜索能力上都具有明显的优势；对于函数f3、f4、f5、f7、f8，SADCDE算法都搜索到了最优解，而其它算法都没能找到最优解，同时收敛速度上也比其它算法要快；对函数f6,SADCDE算法收敛速度快于其它算法，全局搜索精度与SADE算法接近。

f1

f2

f3

f4

f5

f6

f7

f8

四、结论

本文借助单纯形搜索算法的基本思想给出了一种基于改进单纯形局部搜索的自适应的差分进化算法，利用改进的单纯形快速收敛的特点改善部分非优良不可行个体，结合参数F和CR的自适应机制，在保持群体多样性的基础上加快了差分进化算法的收敛。结合优秀的自适应参数算子F和CR和单纯形搜索算法，对差分进化算法进行了进一步改进，加快收敛和全局搜索性能。通过与已有研究比较得出此算法相比纯单纯形搜索算法、差分算法、自适应算法都优秀，说明了本文提供的基于单纯形局部搜索自适应算法该算法中集合了几种算法的优点，提高了算法的性能。但任何一种算法不可能在所有的性能方面占尽优势，SADCDE算法计算量要稍高。也就意味着由于增加了局部搜索的使得相同进化代数下，运算时间的延长。这也是此算法需要进一步改进的地方。

参考文献：

[1]Storn R, Price K. Differential evolution —A simple and efficient adaptive scheme for global optimization over continuous spaces [J]. Journal of Global Optimization , 1997，vol. 11, no. 4: 341-359.

[2]Janez Brest. Large Scale Global Optimization using Self-adaptive Differential Evolution Algorithm,WCCI 2010 IEEE World Congress on Computational Intelligence

July, 18-23, 2010:3097-3104.

[3]张晓伟.刘三阳免比例因子F 的差分进化算法[J].电子学报,2009,36(06).

[4]X. Yao, Y. Liu, and G. Lin. Evolutionary programming made faster[J],IEEE Transactions on Evolutionary Com-putation, 1999,vol. 3, no. 2, p. 82:82-102.

[5]Janez Brest.Self-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems[J]，IEEE Transactions on Evolutionary Compu-tation, 2006,vol. 10, no. 6:646-657.

[6]C. Y. Lee and X. Yao.Evolutionary programming using mutations based on the Levy probability distribution， IEEE Transactions on Evolutionary Computation[J], 2004,vol. 8,no. 1:1-13.

[7]张雪霞，陈维荣，戴朝华.带局部搜索的动态多群体自适应差分进化算法及函数优化[J], 电子学报,2010,38(08).