基于锦标赛选择变异策略的改进差分进化算法及函数优化

摘要/Abstract

摘要： 针对差分进化算法传统变异策略在全局收敛鲁棒性和搜索效率上不能达到一个很好的折衷,并且算法的操作算子固定,导致搜索效率低、易早熟收敛等问题,文中在差分进化算法变异策略性能分析的基础上,提出了一种基于锦标赛选择的变异策略。该策略采用“锦标赛选择”对随机选取的变异向量排序选出基向量,差分向量选择有利于搜索的方向并对其 “强化”,以提高收敛速率和维持种群多样性；同时操作算子采用随机正态缩放因子F和时变交叉概率因子CR,以平衡局部搜索和全局搜索；最后,利用4个典型Benchmarks测试函数对改进算法进行测试。实验结果表明,该改进型差分进化算法能有效避免早熟收敛,较好地提高算法的全局收敛能力和搜索效率。

关键词: 差分进化算法,锦标赛选择,变异策略,可变操作算子

Abstract: The traditional mutation strategy of differential evolution algorithm can not reach a good tradeoff between robustness in global convergence and the search efficiency．The operators are constants,and the differential evolution algorithm leads to many problems,such as the low search efficiency and the premature convergence．Based on analysis of performance of the mutation strategies,a new mutation strategy with tournament selection rule taking the best individual vector from the random individual vectors as the base vector was proposed in this paper．Meanwhile,selecting the direction for the difference vector beneficial to search and making strengthen on the difference vectors is to improve the convergence rate and maintain the diversity of population．The random normal scaling factor F and the time-varying crossover probability factor CR are used synchronously to advance the local search and global search．Finally,the improved differential evolution algorithm was tested on four benchmark functions．The simulation results show that the improved algorithm can effectively avoid the premature convergence,as well as improve the global convergence ability and the search efficiency remarkably.

Key words: Differential evolution algorithm,Tournament selection,Mutation strategy,Variable operator

傅嗣鹏,乔俊飞,韩红桂. 基于锦标赛选择变异策略的改进差分进化算法及函数优化[J]. 计算机科学, 2013, 40(Z6): 15-18. https://doi.org/

FU Si-peng,QIAO Jun-fei and HAN Hong-gui. Improved Differential Evolution Algorithm Based on Mutation Strategy of Tournament Selection for Function Optimization[J]. Computer Science, 2013, 40(Z6): 15-18. https://doi.org/

参考文献

[2] Das S,Suganthan P N．Differential Evolution:A Survey of theState-of-the-Art[J]．IEEE Transactions on evolutionary computation,2011,15(1):4-28
[3] 吴亮红,王耀南,袁小芳,等．自适应二次变异差分进化算法[J]．控制与决策,2006,21(8):898-902
[4] 张雪霞,陈维荣,戴朝华．带局部搜索的动态多群体自适应差分进化算法及函数优化[J]．电子学报,2010,38(8):1825-1830
[5] Dorronsoro B,Ferrante N,David N．Compact Differential Evolution[J]．IEEE Transactions On Evolutionary computation,2011,15(1):67-98
[6] Ali M M,Kajee-Bagdadi Z．A local exploration-based differential evolution algorithm for constrained global optimization[J]．Applied Mathematics and Computation,2009,208(1):31-48
[7] 刘波,王凌,金以慧．差分进化算法研究进展[J]．控制与决策,2007,22(7):721-727
[8] Schafer函数数值相差1,故f4栏数据为文献[8]中数据各自加1后所得。表2 TSIDE、ACPFDE、ASMDE、DE1、DE2各运行20次求平均值函数算法最优解平均解迭代步数方差成功次数f₁ TSIDE4.06×10－68.27×10－64215.36×10－1320 ACPFDE6.22×10－69.09×10－63658.85×10－1320 ASMDE6.47×10－69.01×10－610878.21×10－1820 DE/rand/17.12×10－69.18×10－621785.14×10－1320 DE/best/27.42×10－69.02×10－623634.80×10－1320f₂ TSIDE8.01×10－77.95×10－610874.46×10－1320 ACPFDE6.29×10－69.20×10－619277.46×10－1320 ASMDE3.92×10－37.31×10－380009.51×10－60 DE/rand/16.18×10－68.92×10－661701.19×10－1220 DE/best/27.58×10－61.99×10－159707.95×10－119f₃ TSIDE4.80×10－77.86×10－73031.61×10－1420 ACPFDE7.45×10－69.10×10－62974.45×10－1320 ASMDE6.85×10－69.04×10－611597.19×10－1820 DE/rand/15.93×10－63.78×10－421702.73×10－620 DE/best/27.86×10－66.28×10－351107.05×10－510f₄ TSIDE001272.07×10－1420 ACPFDE008097.90×10－1220 ASMDE01.00×10－315228.93×10－619 DE/rand/101.01×10－276154.95×10－52 DE/best/207.38×10－257102.08×10－55 通过分析表2中仿真数据,对比采用两种传统变异策略的DE1和DE2算法,TSIIDE兼具了两者的优点,并且无论在迭次步数、收敛精度上都要明显优于两者,因此文中的改进方案在保证算法成功率的同时也大大提高了算法的搜索效率,很好地解决了算法传统变异策略在全局收敛性与搜索效率上不能很好折衷的矛盾。另外对比其他的两种改进方案,ASMDE算法在f3函数出现了早熟,原因是在与ACPFDE算法比较上,TSIDE算法只在函数f1、f3迭代步数上稍大于方,但依然是有可比较性的；而在其他算法性能上都要优于对比对方,同时由方差可知,文中提出的改进算法兼具了DE算法鲁棒性较好的特点。 从测试数据中,随机抽取一组实验结果作图对比。为了便于观察,取收敛值的对数为纵坐标,横坐标为迭代步数。各函数优化图形如图1－图4所示。图1 f1目标函数收敛曲线  图2 f2目标函数收敛曲线  图3 f3目标函数收敛曲线  图4 f4目标函数收敛曲线  结束语文中在差分进化算法传统变异策略及操作算子对算法性能的影响分析的基础上,提出了一种基于锦标赛选择变异策略的改进差分进化算法—TSIDE算法,该变异策略选择有利于搜索的方向并对差分向量“强化”,以提高收敛速度和维持种群多样性。采用随机正态缩放因子F和时变交叉概率因子CR,平衡局部搜索和全局搜索。通过4个Benchmarks测试函数进行测试,并与其他算法进行比较。实验结果表明TSIDE算法有很强的全局搜索能力,能有效避免早熟收敛,并且大大提高了搜索效率,稳定性良好,较好地解决了DE算法在全局收敛鲁棒性和搜索效率上不能达到一个很好的折衷的矛盾。 Storn R,Price K．Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces[J]．Journal of Global Optimization,1997,11(4):341-359[2]Das S,Suganthan P N．Differential Evolution:A Survey of theState-of-the-Art[J]．IEEE Transactions on evolutionary computation,2011,15(1):4-28[3]吴亮红,王耀南,袁小芳,等．自适应二次变异差分进化算法[J]．控制与决策,2006,21(8):898-902[4]张雪霞,陈维荣,戴朝华．带局部搜索的动态多群体自适应差分进化算法及函数优化[J]．电子学报,2010,38(8):1825-1830[5]Dorronsoro B,Ferrante N,David N．Compact Differential Evolution[J]．IEEE Transactions On Evolutionary computation,2011,15(1):67-98[6]Ali M M,Kajee-Bagdadi Z．A local exploration-based differential evolution algorithm for constrained global optimization[J]．Applied Mathematics and Computation,2009,208(1):31-48[7]刘波,王凌,金以慧．差分进化算法研究进展[J]．控制与决策,2007,22(7):721-727[8]杨卫东,姚峰,张明．基于自适应交叉概率因子的差分进化算法及其应用[J]．信息与控制,2010,39(2):187-193
[9] Ernesto M,Price K,Lampine J．Differential Evolution—A Practical Approach to Global Optimization[M]．New York:Sprin-ger,2005
[10] Beyer H G,Deb K．On self-adapting features in real-parameter evolutionary algorithms[J]．IEEE Transactions on Evolutionary Computation,2001,5(3):250-270
[11] Brest J,Greiner S,Bo B,et al．Self adapting control parameters in differential evolution:A comparative study on numerical benchmark problems[J].IEEE Transactions on Evolutionary Computation,2006,10(6):646-657
[12] 杨启文,蔡亮,薛云灿．差分进化算法综述[J]．模式识别与人工智能,2008,21(4):506-512
[13] Qin A K,Suganthan P N．Self-adaptive differential evolution algorithm for numerical optimization[A]∥Proceedings of the IEEE Congress on Evolutionary Computation [C].Edinburgh,USA:Institute of Electrical and Electronics Engineers Computer Society,2005:1785-1791
[14] Zaharie D．Critical values for the control parameters of differential evolution algorithms[A]∥Eighth International MENDEL Conference on Soft Computing[C]．Brno,Czech Republic:Brno University of Technology,2002:62-67
[15] Kim H K,Chong J K,Park K Y,et al．Differential evolution strategy for Constrained global optimization and application to practical engineering problems[J]．IEEE Transactions on Magnetics,2007,43(4):1565-1568
[16] 刘荣辉,郑建国．分区交叉差分进化算法及其约束优化[J]．计算机科学,2008,39(2):283-304
[17] Dob K．An efficient constraint handling method for genetic algorithms[J]．Computer Methods in Applied Mechanics and Engineering,2000,186(2-4):311-338

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed