改进的组合差分进化优化算法董明刚

计算机仿真

2013年1月

文章编号：1006－9348（2013）01－0389－04

改进的组合差分进化优化算法

董明刚

1，2

21

，王宁，程小辉

（1．桂林理工大学信息科学与工程学院，广西桂林541004；2．浙江大学工业控制技术国家重点实验室，浙江杭州310027）摘要：组合差分进化算法CoDE是一新的具有竞争力的算法，但收敛速度和寻优性能仍有待改进。为解决上述问题，提出对组合差分进化算法CoDE从生成策略和控制参数两个方面进行改进，提出了两种改进的CoDE版本MCoDE和MCoDE－P，并利用6个典型的测试函数对改进性能进行检验。结果表明结合了最好个体信息的MCoDE方法能够改善CoDE的寻优性能，而采用控制参数扩展的MCoDE－P方法却难以达到期望的效果。关键词：组合差分进化；改进；优化算法；生成策略；控制参数中图分类号：TP202．7

文献标识码：A

ImprovedCompositeDifferentialEvolutionAlgorithms

DONGMing－gang1，2，WANGNing2，CHENGXiao－hui1

（1．CollegeofInformationScienceandEngineering，GuilinUniversityofTechnology，GuilinGangxi541004，China；2．NationalLaboratoryofIndustrialControlTechnology，ZhejiangUniversity，HangzhouZhejiang310027，China）ABSTRACT：CoDE，thecompositedifferentialevolutionalgorithm，isanewcompetitivealgorithm，buttheconver-gencespeedandoptimizationperformancestillneedtobeimproved．TwoimprovedCoDEversions，MCoDEandMCoDE－P，wereproposed．TheMCoDEcanmodifythegenerationstrategyofCoDE，andtheMCoDE－Pcanex-pandthecontrolparametersofCoDE．Sixtypicalbenchmarkfunctionswereusedtotesttheperformancesoftheim-provedapproaches．ThecomparedresultsshowthatthecombinationofthebestindividualinformationMCoDEmethodcanimprovetheperformanceofCoDE，whiletheproposedcontrolparameterexpansionmethodMCoDE－Pisdifficulttoachievethedesiredeffect．

KEYWORDS：Compositedifferentialevolution；Improvement；Optimizationalgorithms；Generationstrategy；Controlparameters

1引言

Storn和Price为求解切比雪夫多项式拟合问题时发明了

的向量产生策略和不同的参数设置在处理不同的类型各有优势，但遗憾的是这些重要信息并没有被充分利用，大部分DE算法仅采用一种向量产生策略和一组参数设置值。因此，最近有研究人员提出将各种向量产生策略和参数设置策略相融合的思想，以便改进单一向量产生策略和参数设置的DE算法的性能。典型的有，Mallipeddi等人提出了具有学习能力的装配差分进化算法EPSDE

［5］

［1］

差分进化算法（differentialevolution，简称DE）。类似于其

DE也是一种基于群体的随机搜索算法，它进化计算方法，它主要采用变异、交叉、替换等操作迭代来指导群体进化；但与DE主要采用候选解间的差异作为干扰量来其它方法不同，

DE执行简产生新的个体。同时与其它进化计算方法相比，

单，在收敛速度和搜索性能方面都具有一定的优势。近年DE在IEEE进化计算大会举办的各种竞赛中屡创佳绩，因而倍受关注，成为进化计算领域研究的热点之一

［2，3，4］

。Wang等人利用已有的

研究成果，建立向量产生策略知识库和参数设置知识库，并在此基础上提出了一种组合差分进化算法（Compositediffer-entialevolution，简称CoDE）［6］。研究结果验证了此方法对提高DE性能是可行性和有效性的，与现有的几种自适应DE相比，获得了极具竞争力的结果。但在CoDE中，其参数设置库中仅选择三组特定的个体产生策略和三组特殊参数设置，还有其它一些常见的个体产生策略和参数设置并没有涉及。因此，本文考虑从个体产生策略和控制参数两个方面对CoDE进行改进，并通过仿真研究，探讨提出改进方法可行性和有效性。

。

DE的向量产生策略和控制参数选择是影响DE性能的两个关键因素。在DE的向量产生策略和参数选择方面已进行了大量的研究，并取得一些较重要定性的结论

［3，4］

。不同

基金项目：国家自然科学基金项目（61203109）；广西教育厅科研项目

（201204LX155）

收稿日期：2012－09－06

—389—

2CoDE差分

鉴于矢量产生策略和控制参数对DE的性能具有重要影

响，且各有优势，Wang等人提出了一个新的自适应DE算法CoDE［6］，该方法组合了几种矢量产生策略和特定的控制参数用于产生新的矢量。在CoDE算法中包含有三种矢量产生策略和三组控制参数。采用的三种矢量产生策略分别为：“rand/1/bin”、“rand/2/bin”和“current－to－rand/1”。三组控制参数分别为：［

F=1．0，Cr=0．1］，［F=1．0，Cr=0．9］和［F=0．8，Cr=0．2］。其中F表示缩放因子Cr表示交叉概率。

上述策略和参数设置经常用于许多版本的DE中，并且它们的属性已经被深入的研究。借助于从控制参数集中随机选择的一组参数，新个体产生策略候选池中的每个策略都用来产生新的矢量，再从三者中选择最好的个体。这种方法的思想可以用图1来表示。更多的信息可以在文献［6］中找到。

图1CoDE算法的新个体产生方式

3

改进的组合差分进化算法

3．1

改变生成策略法

尽管CoDE在连续优化领域已经显示出优异的优化性

能，但从文献［6］的研究结果中可以看出，文献［7］提出JADE的性能仅次于提出的CoDE算法，特别是对于5个单模函数，除1个与CoDE相当外，其它4个均优于CoDE。JADE的优异性能主要在于它采用一种贪婪的变异操作

：“DE/cur-rent－to－best/1”，该操作利用了当前群体最优解的信息，加速了种群的快速收敛

［2］

。而CoDE在求解单模函数时效果

不佳。而在CoDE的三种变异策略中，

并没有利用最优解的信息。因此，考虑从向量产生策略方面进行改进，以期望得到好的结果。对CoDE的新个体产生策略集进行调整，将“current－to－best/1”操作引入进来。因“current－to－best/1”与CoDE原始个体产生策略集中的“current－to－rand/1”在形式上具有极大的相似性，因此，这里采用替换方式，即将个体产生策略集中的“current－to－rand/1”替换成“current－to－best/1”，其它保持不变。

3．2控制参数扩展法

CoDE中控制参数只选择了3组且是随机选择的，文献

—390—

［6］对控制参数的选择问题进行了研究。对引入学习机制建立自适应参数选择方法和采用固定参数设置两种情况下算法的性能进行检验，结果显示这两种参数选择方法都不能超过采用随机方式的CoDE。不同于从参数选择方面进行改进，提出一种增加控制参数的方式，以检查其改进效果，称这种从参数方面进行扩展的CoDE为MCoDE－P。根据EPS-DE［5］算法中参数的设置范围：F在0．4至0．9之间以0．1的步长进行选择，

Cr在0．1至0．9之间以0．1的步长进行选择。本章在原有CoDE控制参数库的基础上，再增加了另外三组参数：［

F=0．7，Cr=0．3］，［F=0．6，Cr=0．4］和［F=0．5，Cr=0．5］。

从以上描述可以看出，除向量产生策略和控制参数选择方法不同外，

CoDE，MCoDE和MCoDE－P三种组合差分进化算法采用的整体结构都是一样的。在这里仅以MCoDE算法为例介绍其主要实现步骤。

步骤1：初始化控制参数库和终止条件，设置种群大小（通常等于决策变量的个数），随机产生初始化种群；

步骤2：对初始种群进行评估，并记录最好个体信息，设置进化代数G=0；

步骤3：对每个个体随机从控制参数集中选择一组控制参数，调用“rand/1/bin”、“rand/2/bin”和“current－to－best/1”三种新个体产生策略产生三个新的向量；

步骤4：计算三个新向量的目标函数值，将最优个体作

为尝试向量u珗

；步骤5：比较目标向量珒x和新产生的向量u珗的目标函数值，若u珗优于珒x，则用u珗来替换珒x加入到下一代种群中；

步骤6：判断是否种群中所有的个体都执行完。若未执行完，则转步骤3继续执行。否则，执行步骤7；

步骤7：找出下一代种群中的最好个体，更新最好个体信息，

G=G+1；步骤8：判断是否满足终止条件，若满足，则输出最好个体信息及对应的目标函数值，执行完成。否则，转步骤3继续执行。

通用的组合差分进化算法流程图可采用图2来描述。

4

计算仿真

4．1

测试函数

采用2005年IEEE进化计算大会上公布的25个标准测

试函数中的6个典型函数：F2，

F3，F4，F8，F13，F14作为测试函数

［8］

。这些函数的维数是可以扩展的，都是极具挑战性的

问题。在这6个函数中包括：三个单模函数F2，F3，F4；一个基本多模函数F8和二个扩展多模函数F13，F14。为表示方便，本文将F2，

F3，F4，F8，F13和F14分别用f1，f2，……，f6来表示。这里仅给出f1的定义，其它测试函数仅给出其特征，有关它们的详细信息请参见文献［

8］。1）f1：偏移Schwefel问题1．2（F2）。

特征：单模，偏移，非独立，可扩展，x∈［－100，100］D

，全

2）f2：偏移旋转高条件Elliptic函数1．2（F3）。

x∈［－100，特征：单模，偏移，旋转，非独立，可扩展，

珒珒珒100］D，*=o，f1（x*）=全局最优解和全局最优值xf_bias。

3）f3：带有噪声的偏移Schwefel’s问题1．2（F4）。x∈［－特征：单模，偏移，非独立，可扩展，带有噪声，

D

珒珒珒100，100］，*=o，f3（x*）=全局最优解和全局最优值xf_bias。

4）f4：最优值在边界的偏移旋转Ackley函数（F8）。特征：多模，偏移，旋转，非独立，可扩展，全局最优解位

D

珒珒x∈［－32，32］，*=o，于边界，全局最优解和全局最优值x珒f4（x*）=f_bias。

5）f5：偏移扩展的Griewank加Rosenbrock函数（F13）。特征：多模，偏移，非独立，可扩展，全局最优解位于边

D

珒珒x∈［－3，1］，全局最优解和全局最优值x*=o，界，

珒f5（x*）=f_bias。

6）f6：偏移旋转扩展的Scaffer’sF6函数（F14）。特征：多模，偏移，旋转，非独立，可扩展，全局最优解位

D

珒x∈［－100，100］，*=于边界，全局最优解和全局最优值x珒珒o，f6（x*）=f_bias

利用它们对MCoDE和MCoDE－P的寻优性能进行了测试，并与最近相关文献中提出的CoDE和EPSDE两种采用组合思想的典型算法进行比较。4．2

实验结果与讨论

为保证比较结果的公正性，在实验中，对上述CoDE和EPSDE种算法均采用与原始文献完全相同的参数设置。采用Matlab进行编码，并且所有的实验都是在PentiumDual－

图2

组合差分进化算法的流程图

Core2．7GHzCPU和2GB内存的个人计算机上进行的。与文6］中的类似，献［将决策变量个数D设置为30，所有函数的f_bias都设置为0。当函数评价次数达到300000次后，算法结束运行。四种算法的种群规模NP都设置为30。为了统计性能

局最优解和全局最优值

珒f1（x）=

z）∑（∑珒

j

i=1

j=1

D

i

2

+f_bias，

（1）

和比较不同的算法，实验中记录了在25次独立实验中每种平均值、最差值和标准差。计算结算法获得的函数的最好值、果如表1所示。

珒珒－o珒珒=［z=x，xx1，x2，…，xD］

珒珒珒珒ox*=o，f1（x*）=f_bias。为随机产生的向量，

表1

函数f1f2f3f4f5f6

最坏解3．21E－14233920．530．032278620．6421942．445244913．156153

平均解4．51E－15115942．050．004503320．153011．585601212．318889

CoDE

最好解2．50E－1735178．5152．05E－0520．0027931．210634111．421112

标准差8．14E－1554325．8960．0072020．16331310．29958120．4686231

四种算法的优化结果

EPSDE

最坏解2．18E－242019025．1182．1890321．0109332．218404613．812026

平均解1．48E－25138318．738．814248120．9274591．983182113．348078

最好解4．16E－2710269．9941．05E－0520．7715451．693895712．634192

标准差4．48E－25396186．5936．4918990．05971080．15534740．2680242

—391—

（续）函数f1f2f3f4f5f6

最坏解1．36E－15330467．560．608042920．9890255．03713112．744379

MCoDE－P平均解8．09E－17105617．650．06445720．5107822．209600612．133863

最好解1．14E－1929301．5411．26E－0520．0168931．170834110．922678

标准差2．70E－1668602．560．14567670．34714930．95742230．4931714

最坏解4．90E－22115577．820．048622621．0159953．131992813．385109

平均解8．02E－2353119．2820．004038320．8944921．862586612．686496

MCoDE

最好解1．26E－2410315．6042．01E－0620．0088491．321677311．906742

标准差1．24E－2225812．460．01020050．19312330．43326190．3698627

1）单模函数f1，f2，f3：从表1可以看出，就单模函数而言，MCoDE在四种算法中取得了最好的性能，f3个测试它在f2，EPSDE和MCoDE－P。函数上均要明显优于CoDE、而在f1上获得比EPSDE相当的性能，但要明显优化CoDE和MCoDE－P，这说明对于单模函数而言，在向量产生过程中采用最好个体信息有助于提高CoDE的性能。同时也注意到对于MCoDE－P在单模函数中不仅没有改善，反而对于f3其性能变差了。这说明采用本文提出的控制参数扩展法来提高CoDE的在单模函数上的寻优性能并不能改进CoDE的性能。

2）多模函数f4，f5，f6：对于这3个测试函数，除MCoDE－P在f5上表现稍逊于其它三种算法外，四种算法都表现出相同的性能。这说明本文提出的对改进策略不会影响CoDE在多模函数上的寻优性能。

总体上来看，上述比较结果显示MCoDE对于这6个典型的测试函数表现出最好的性能。而MCoDE－P不仅不能提高MCoDE的寻优性能，反而会使CoDE的性能变坏。

［2］王勇．基于进化算法求解复杂连续优化问题的研究［D］．中南

2011．大学博士学位论文，

［3］刘波，．控制与决王凌，金以慧．差分进化算法研究进展［J］

2007，22（7）：721－729．策，

［4］SDas，PNSuganthan．Differentialevolution：Asurveyofthestate

－of－the－art［J］．IEEETransactionsonEvolutionaryComputa-2011，15（1）：4－31．tion，

［5］RMallipeddi，PNSuganthan，QKPan，MFTasgetiren．Differ-entialevolutionalgorithmwithensembleofparametersandmutation．AppliedSoftComputing，2011，11（2）：1679－strategies［J］1696．

［6］YWang，ZCai，QZhang．Differentialevolutionwithcomposite

trialvectorgenerationstrategiesandcontrolparameters［J］．IEEETransactionsonEvolutionaryComputation，2011，15（1）：55－66．

［7］JZhang，ACSanderson．JADE：adaptivedifferentialevolution

．IEEETransactionsonEvolu-withoptionalexternalarchive［J］

tionaryComputation，2009，13（5）：945－958．

［8］PNSuganthan，NHansen，JJLiang，KDeb，YPChen．A．Au-ger，TiwariS．ProblemdefinitionsandevaluationcriteriafortheCEC2005specialsessiononreal－parameteroptimization［R］．NanyangTechnologyUniversity，Singapore，TechnologyReportKanGAL#2005005，May2005，IITKanpur，India，2005．

5小结

本文从新个体产生策略和控制参数策略两个方面提出

了组合差分进化算法的改进方法，并通过典型测试函数对方法的有效性进行了检验，结果表明，在个体产生策略中引入最好个体信息有助于改善CoDE的寻优性能。而对于控制参数的扩展方法却难以得到期望的效果。本文只是对CoDE性能的改进方法进行了初步尝试，如何发现更科学的个体产生将策略库和控制参数库仍是有待进一步研究的内容。此外，本文提出改进方法应用于实际复杂问题的优化，以检验其实用性也是下一步需要研究的内容。参考文献：

［1］RStorn，KPrice．Differentialevolution－Asimpleandefficient

heuristicforglobaloptimizationovercontinuousspaces［J］．Journal1997，11（4）：341－359．ofGlobalOptimization，

［作者简介］

董明刚（1977－），男（汉族），湖北省安陆人，副教

授，硕士研究生导师，主要研究领域为智能计算；

王

算；

宁（1961－），男（汉族），湖南省衡阳人，教授，

博士研究生导师，主要研究领域为智能优化、仿生计

程小辉（1961－），男（汉族），江西省樟树人，教授，硕士研究生导

主要研究领域为嵌入式系统、计算机网络。师，

—392—