自适应二次变异差分进化算法

第21卷第8期

Vol.21No.8

　控　制　与　决　策

Control

and

Decision　

　2006年8月

　　Aug.2006

　　文章编号:100120920(2006)0820898205

自适应二次变异差分进化算法

吴亮红1,2,王耀南1,袁小芳1,周少武2

(1.湖南大学电气与信息工程学院,长沙410082;2.湖南科技大学信息与电气工程学院,湖南湘潭411201)

摘　要:提出一种基于群体适应度方差自适应二次变异的差分进化算法.该算法在运行过程中根据群体适应度方差的大小,增加一种新的变异算子对最优个体和部分其他个体同时进行变异操作,以提高种群多样性,增强差分进化算法跳出局部最优解的能力.对几种典型Benchmarks函数进行了测试,实验结果表明,该方法能有效避免早熟收敛,显著提高算法的全局搜索能力.

关键词:差分进化;自适应二次变异;时变概率;早熟收敛中图分类号:TP391　　　　文献标识码:A

DifferentialEvolutionSecondMutation

WULiang2hong

1,2

2

,aoNXiao2fang1,ZHOUShao2wu

(1.SchoolofandronEngineering,Hu’nanUniversity,Changsha410082,China;2.SchoolofInformationandEngineering,Hu’nanUniversityofScienceandTechnology,Xiangtan411201,China.Correspondent:WULiang2hong,E2mail:[email protected])

Abstract:Anewadaptivesecondmutationdifferentialevolutionalgorithm(ASMDE)basedonthevarianceofthepopulation’sfitnessispresented.Inordertoimprovethepopulation’sdiversityandtheabilityofbreakingawayfromthelocaloptimum,accordingtothevalueofthevarianceofthepopulation’sfitnessduringtherunningtime,anewmutationoperatorisadaptedtomutateboththebestindividualandpartialotherindividuals.convergenceandimprovestheglobalconvergenceabilityremarkably.

Keywords:Differentialevolution;Adaptivesecondmutation;Timevaryingprobability;Prematureconvergence

Severalclassic

Benchmarksfunctionsaretestedandtheresultsshowthattheproposedalgorithmcanavoidthepremature

1　引　　言

　　差分进化(Differentialevolution,DE)算法是

一种采用浮点矢量编码在连续空间中进行随机搜索的优化算法[1].DE的原理简单,受控参数少,实施随机、并行、直接的全局搜索,易于理解和实现.在日本召开的第一届国际进化优化计算竞赛(ICEO)中[2],DE表现突出,已成为进化算法(EA)的一个重要分支.近年来,DE在约束优化计算,模糊控制器优化设计,神经网络优化,滤波器设计等方面得到了广泛的应用.

DE是根据父代个体间的差分矢量进行变异、交叉和选择操作,与其他进化算法(如遗传算法)一

　　收稿日期:2005206211;修回日期:2005209221.

样易陷入局部最优,存在早熟收敛现象.目前的解决方法主要是增加种群的规模,但这样会增加算法的运算量,而且也不能从根本上克服早熟收敛的问题.为提高DE的性能,很多学者提出了改进的方法.文献[3]在算法中加入了迁移算子和加速算子,提高了算法的种群多样性和收敛速率,但要计算适应度函数的梯度信息,实现较为麻烦,应用会受到限制.文献[4]针对差分矢量的缩放因子F和交叉概率CR两参数对算法的影响,提出了一种模糊自适应差分进化算法,但要选择模糊隶属函数,实现较为困难.文献[5]将缩放因子F由固定数值设计为随机函数,减少了需调整的参数,实现了一个简化的DE版

　　基金项目:国家自然科学基金项目(60375001);高校博士点基金项目([1**********]).

　　作者简介:吴亮红(1978—),男,湖南宁乡人,硕士生,从事智能控制、计算智能等研究;王耀南(1957—),男,昆明人,

教授,博士生导师,从事智能控制、智能信息处理、智能图像处理等研究.

第8期

本,但并不能解决早熟收敛问题.

吴亮红等:自适应二次变异差分进化算法899

CR越大,xm对xT的贡献越多,当CR=1时,xT=

xm,有利于局部搜索和加速收敛速率;CR越小,xi

g

产生早熟收敛的根本原因是随迭代次数的增加和种群多样性的快速下降.为克服早熟现象,跳出局部最优解,本文提出了一种基于群体适应度方差自适应二次变异的差分进化算法(ASMDE).对几种典型的Benchmarks函数测试表明,与遗传算法和进化算法相比,本文提出的算法能有效地避免早熟收敛,全局收敛能力得到了显著提高.

2　差分进化算法及其早熟收敛问题

2.1　差分进化算法

DE与其他进化算法如遗传算法(GA),进化规

对xT的贡献越多,当CR=0时,xT=xgi,有利于保

持种群的多样性和全局搜索.由此可见,保持种群多样性和收敛速率是矛盾的.2.1.3　选择操作

DE采用“贪婪”的搜索策略,经过变异和交叉操作后生成的试验个体xT与xg.只有当i进行竞争

g

xT的适应度较xi更优时才被选作子代;否则,直接将xg.i作为子代

g

xT,f(xT)

xi=gg

xi,f(xT)≥f(xi).2.2　划(EP),进化策略(ES)及其它们的变种不同.首先由父代个体间的差分矢量构成变异算子;接着按一定的概率,父代个体与变异个体之间进行交叉操作,生成一试验个体;然后在父代个体与试验个体之间根据适应度的大小进行选择操作,选择适应度更优的个体作为子代.2.1.1　变异操作

DE,每个

(4)

矢量对包括父代)g

(xga,xb).Dab=xa-g

xb.

g

(1)

　　根据变异个体的生成方法不同,形成了多种不同的差分进化算法方案[1,6].本文选择从种群中随机选择4个不同个体生成差分矢量对每代最优个体进行变异操作的方案.这种方案既能提高算法的收敛速度,又能在一定程度上保持较高的种群多样性.个体变异操作的方程为

xm=xgbest+F[(xa-g

g

g

g

gg

xb)+(xc-

xd)].

g

(2)

由于E,可以加快收敛,.由式(2)可gg随着进化的进行,其他个体.如果xggbest为一局部最优点,随着,个体之间的差异越来越小,变异矢量Dab趋于0,交叉和选择操作不能改变种群的多样性,最后所有个体都趋向于xggbest,种群便无法在解空间内重新搜索.因此,算法陷入局部最优,出现了所谓的早熟收敛现象.由于差分进化算法是一种随机搜索策略,如果问题是多峰函数,则存在多个局部最优点,算法很容易陷入局部最优,难以找到全局最优.即使进行变异的个体不采用xggbest,而是种群中任一其他个体,若某一个体是局部最优解,也同样有陷入该局部最优的可能,而且收敛速度会变慢.因此,DE与其他进化算法(如GA)一样,容易早熟收敛,陷入局部最优.

ggg

式中:xggbest为种群中适应度最好的个体;xa,xb,xc和

3　自适应二次变异差分进化算法设计

3.1　自适应二次变异思想

xd为与xgbest不同的4个互不相同的个体;F为缩放

因子,其取值范围为(0,1.2];xm相当于xggbest的一个噪音版本,F越大,xggbest变异越多,对xm的影响越大.

2.1.2　交叉操作

对于群体中第i个个体xgi,将与xm进行交叉操作,产生试验个体xT.为保证个体xgi的进化,首先通过随机选择,使得xT至少有一位由xm贡献,而对于其他位,可利用一个交叉概率因子CR决定xT中哪位由xm贡献,哪位由x贡献.交叉操作的方程为

xmj,rand()≤CR;

xTj=

xij,rand()>CR;j=1,2,…,D.

ggi

产生早熟收敛的根本原因是随迭代次数的增加和种群多样性的快速下降,形成了“聚集”现象.这表现在种群个体的适应度之间的差异越来越小.为定量描述种群的状态,下面给出群体适应度方差的定义[7].

定义1　设群体规模为NP,fi为第i个个体的适应度,favg为种群目前的平均适应度,则∆2可定义为

∆=

2

∑

第21卷第8期

Vol.21No.8

　控　制　与　决　策

Control

and

Decision　

　2006年8月

　　Aug.2006

　　文章编号:100120920(2006)0820898205

自适应二次变异差分进化算法

吴亮红1,2,王耀南1,袁小芳1,周少武2

(1.湖南大学电气与信息工程学院,长沙410082;2.湖南科技大学信息与电气工程学院,湖南湘潭411201)

摘　要:提出一种基于群体适应度方差自适应二次变异的差分进化算法.该算法在运行过程中根据群体适应度方差的大小,增加一种新的变异算子对最优个体和部分其他个体同时进行变异操作,以提高种群多样性,增强差分进化算法跳出局部最优解的能力.对几种典型Benchmarks函数进行了测试,实验结果表明,该方法能有效避免早熟收敛,显著提高算法的全局搜索能力.

关键词:差分进化;自适应二次变异;时变概率;早熟收敛中图分类号:TP391　　　　文献标识码:A

DifferentialEvolutionSecondMutation

WULiang2hong

1,2

2

,aoNXiao2fang1,ZHOUShao2wu

(1.SchoolofandronEngineering,Hu’nanUniversity,Changsha410082,China;2.SchoolofInformationandEngineering,Hu’nanUniversityofScienceandTechnology,Xiangtan411201,China.Correspondent:WULiang2hong,E2mail:[email protected])

Abstract:Anewadaptivesecondmutationdifferentialevolutionalgorithm(ASMDE)basedonthevarianceofthepopulation’sfitnessispresented.Inordertoimprovethepopulation’sdiversityandtheabilityofbreakingawayfromthelocaloptimum,accordingtothevalueofthevarianceofthepopulation’sfitnessduringtherunningtime,anewmutationoperatorisadaptedtomutateboththebestindividualandpartialotherindividuals.convergenceandimprovestheglobalconvergenceabilityremarkably.

Keywords:Differentialevolution;Adaptivesecondmutation;Timevaryingprobability;Prematureconvergence

Severalclassic

Benchmarksfunctionsaretestedandtheresultsshowthattheproposedalgorithmcanavoidthepremature

1　引　　言

　　差分进化(Differentialevolution,DE)算法是

一种采用浮点矢量编码在连续空间中进行随机搜索的优化算法[1].DE的原理简单,受控参数少,实施随机、并行、直接的全局搜索,易于理解和实现.在日本召开的第一届国际进化优化计算竞赛(ICEO)中[2],DE表现突出,已成为进化算法(EA)的一个重要分支.近年来,DE在约束优化计算,模糊控制器优化设计,神经网络优化,滤波器设计等方面得到了广泛的应用.

DE是根据父代个体间的差分矢量进行变异、交叉和选择操作,与其他进化算法(如遗传算法)一

　　收稿日期:2005206211;修回日期:2005209221.

样易陷入局部最优,存在早熟收敛现象.目前的解决方法主要是增加种群的规模,但这样会增加算法的运算量,而且也不能从根本上克服早熟收敛的问题.为提高DE的性能,很多学者提出了改进的方法.文献[3]在算法中加入了迁移算子和加速算子,提高了算法的种群多样性和收敛速率,但要计算适应度函数的梯度信息,实现较为麻烦,应用会受到限制.文献[4]针对差分矢量的缩放因子F和交叉概率CR两参数对算法的影响,提出了一种模糊自适应差分进化算法,但要选择模糊隶属函数,实现较为困难.文献[5]将缩放因子F由固定数值设计为随机函数,减少了需调整的参数,实现了一个简化的DE版

　　基金项目:国家自然科学基金项目(60375001);高校博士点基金项目([1**********]).

　　作者简介:吴亮红(1978—),男,湖南宁乡人,硕士生,从事智能控制、计算智能等研究;王耀南(1957—),男,昆明人,

教授,博士生导师,从事智能控制、智能信息处理、智能图像处理等研究.

第8期

本,但并不能解决早熟收敛问题.

吴亮红等:自适应二次变异差分进化算法899

CR越大,xm对xT的贡献越多,当CR=1时,xT=

xm,有利于局部搜索和加速收敛速率;CR越小,xi

g

产生早熟收敛的根本原因是随迭代次数的增加和种群多样性的快速下降.为克服早熟现象,跳出局部最优解,本文提出了一种基于群体适应度方差自适应二次变异的差分进化算法(ASMDE).对几种典型的Benchmarks函数测试表明,与遗传算法和进化算法相比,本文提出的算法能有效地避免早熟收敛,全局收敛能力得到了显著提高.

2　差分进化算法及其早熟收敛问题

2.1　差分进化算法

DE与其他进化算法如遗传算法(GA),进化规

对xT的贡献越多,当CR=0时,xT=xgi,有利于保

持种群的多样性和全局搜索.由此可见,保持种群多样性和收敛速率是矛盾的.2.1.3　选择操作

DE采用“贪婪”的搜索策略,经过变异和交叉操作后生成的试验个体xT与xg.只有当i进行竞争

g

xT的适应度较xi更优时才被选作子代;否则,直接将xg.i作为子代

g

xT,f(xT)

xi=gg

xi,f(xT)≥f(xi).2.2　划(EP),进化策略(ES)及其它们的变种不同.首先由父代个体间的差分矢量构成变异算子;接着按一定的概率,父代个体与变异个体之间进行交叉操作,生成一试验个体;然后在父代个体与试验个体之间根据适应度的大小进行选择操作,选择适应度更优的个体作为子代.2.1.1　变异操作

DE,每个

(4)

矢量对包括父代)g

(xga,xb).Dab=xa-g

xb.

g

(1)

　　根据变异个体的生成方法不同,形成了多种不同的差分进化算法方案[1,6].本文选择从种群中随机选择4个不同个体生成差分矢量对每代最优个体进行变异操作的方案.这种方案既能提高算法的收敛速度,又能在一定程度上保持较高的种群多样性.个体变异操作的方程为

xm=xgbest+F[(xa-g

g

g

g

gg

xb)+(xc-

xd)].

g

(2)

由于E,可以加快收敛,.由式(2)可gg随着进化的进行,其他个体.如果xggbest为一局部最优点,随着,个体之间的差异越来越小,变异矢量Dab趋于0,交叉和选择操作不能改变种群的多样性,最后所有个体都趋向于xggbest,种群便无法在解空间内重新搜索.因此,算法陷入局部最优,出现了所谓的早熟收敛现象.由于差分进化算法是一种随机搜索策略,如果问题是多峰函数,则存在多个局部最优点,算法很容易陷入局部最优,难以找到全局最优.即使进行变异的个体不采用xggbest,而是种群中任一其他个体,若某一个体是局部最优解,也同样有陷入该局部最优的可能,而且收敛速度会变慢.因此,DE与其他进化算法(如GA)一样,容易早熟收敛,陷入局部最优.

ggg

式中:xggbest为种群中适应度最好的个体;xa,xb,xc和

3　自适应二次变异差分进化算法设计

3.1　自适应二次变异思想

xd为与xgbest不同的4个互不相同的个体;F为缩放

因子,其取值范围为(0,1.2];xm相当于xggbest的一个噪音版本,F越大,xggbest变异越多,对xm的影响越大.

2.1.2　交叉操作

对于群体中第i个个体xgi,将与xm进行交叉操作,产生试验个体xT.为保证个体xgi的进化,首先通过随机选择,使得xT至少有一位由xm贡献,而对于其他位,可利用一个交叉概率因子CR决定xT中哪位由xm贡献,哪位由x贡献.交叉操作的方程为

xmj,rand()≤CR;

xTj=

xij,rand()>CR;j=1,2,…,D.

ggi

产生早熟收敛的根本原因是随迭代次数的增加和种群多样性的快速下降,形成了“聚集”现象.这表现在种群个体的适应度之间的差异越来越小.为定量描述种群的状态,下面给出群体适应度方差的定义[7].

定义1　设群体规模为NP,fi为第i个个体的适应度,favg为种群目前的平均适应度,则∆2可定义为

∆=

2

∑