doi:

DOI: 10.3724/SP.J.1001.2010.03486

Journal of Software (软件学报) 2010/21:5 PP.875-885

Convergent Analysis and Algorithmic Improvement of Differential Evolution


Abstract:
To analyze the convergence of differential evolution (DE) and enhance its capability and stability, this paper first defines a differential operator (DO) as a random mapping from the solution space to the Cartesian product of solution space, and proves the asymptotic convergence of DE based on the random contraction mapping theorem in random functional analysis theory. Then, inspired by "quasi-physical personification algorithm", this paper proposes an improved differential evolution with multi-strategy cooperating evolution (MEDE) is addressed based on the fact that each evolution strategy of DE has common peculiarity but different characteristics. Its asymptotic convergence is given with the definition of multi-strategy differential operator (MDO), and the connotative peculiarity of MEDE is analyzed. Compared with the original DE, DEfirDE and DEfirSPX, the simulation results on 5 classical benchmark functions show that MEDE has obvious advantages in the convergence rate, solution-quality and adaptability. It is suitable for solving complex high-dimension numeral optimization problems.

Key words:differential evolution,asymptotic convergence,contraction mapping,random operator,evolution strategy

ReleaseDate:2014-07-21 15:16:56

Funds:Supported by the National Natural Science Foundation of China under Grant Nos.60473045, 60471022 the Hebei Provincial Natural Science Foundation of China under Grant No.F2008000635



[1] Storn R, Price K. Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 1997,11(4):341-359.

[2] Abbass HA. The self-adaptive Pareto differential evolution. In: Proc. of the 2002 Congress on Evolutionary Computation (CEC 2002), Vol.1. New York: IEEE Service Center, 2002. 831-836.

[3] Vesterstrom J, Thomsen R. A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithm on numerical benchmark problems. In: Proc. of the IEEE 2004 Congress on Evolutionary Computation (CEC 2004, Vol.2. New York: IEEE Service Center, 2004. 1980-1987.

[4] Babu BV, Jehan MML. Differential evolution for multiple-objective optimization. Evolutionary Computation, 2003,11(4):8-12.

[5] Zhang LB, Zhou CG, Ma M, Sun CT. A multi-objective differential evolution algorithm based on max-min distance density. Journal of Computer Research and Development, 2007,44(1):177-184 (in Chinese with English abstract). 张利彪,周春光,马铭,孙彩堂.基于极大极小距离密度的多目标微分进化算法.计算机研究与发展,2007,44(1):177-184.

[6] He YC, Wang XZ, Kou YZ. A binary differential evolution algorithm with hybrid encoding. Journal of Computer Research and Development, 2007,44(9):1476-1484 (in Chinese with English abstract). 贺毅朝,王熙照,寇应展.一种具有混合编码的二进制差分演化算法.计算机研究与发展,2007,44(9):1476-1484.

[7] Noman N, Iba H. Enhancing differential evolution performance with local search for high dimensional function optimization. In: Beyer HG, et al., eds. Proc. of the 2005 Conf. on Genetic and Evolutionary Computation (GECCO 2005). New York: ACM Press, 2005. 967-974.

[8] Zhao GQ, Peng XY, Sun N. A modified differential evolution algorithm with hybrid optimization strategy. ACTA Electronica Sinica, 2006,34(12):2402-2405 (in Chinese with English abstract). 赵光权,彭喜元,孙宁.基于混合优化策略的微分进化改进算法.电子学报,2006,34(12):2402-2405.

[9] Qing AY. Dynamic differential evolution strategy and applications in electromagnetic inverse scattering problem. IEEE Trans. on Geoscience and Remote Sensing, 2006,44(1):116-125.

[10] Rahnamayan S. Opposition-Based differential evolution [Ph.D. Thesis]. Waterloo: University of Waterloo, 2007.

[11] Fan HY, Lampinen J. A trigonometric mutation operation to differential evolution. Journal of Global Optimization, 2003,27(1): 105-129.

[12] Noman N, Iba H. Accelerating differential evolution using an adaptive local search. IEEE Trans. on Evolutionary Computation, 2008,12(1):107-125.

[13] Zhang FT, Song JH, Li J, Cheng XL. A hybrid differential evolution method for optimal reactive power optimization. Power System Technology, 2007,31(9):33-37 (in Chinese with English abstract). 张丰田,宋家骅,李鉴,程晓磊.基于混合差异进化优化算法的电力系统无功优化.电网技术,2007,31(9):33-37.

[14] Huang WQ, Xu RH. Introduction to the Theory of Recent Computation-Research on Background, Foreground and Algorithms of NP Hard Problems. Beijing: Science Press, 2004. 47-70 (in Chinese). 黄文奇,许如初.近世计算理论导引——NP难度问题的背景、前景及其求解算法研究.北京:科学出版社,2004.47-70.

[15] Liu Y, Kang LS, Chen YP. Nonnumerical Parallel Algorithms-Genetic Algorithm. Beijing: Science Press, 2003. 22-86 (in Chinese). 刘勇,康立山,陈毓屏.非数值并行算法——遗传算法.北京:科学出版社,2003.22-86.

[16] Li MQ, Kou JS, Lin D, Li SQ. The Foundational Theory and Application of Genetic Algorithms. Beijing: Science Press, 2003. 115-119 (in Chinese). 李敏强,寇纪松,林丹,李书全.遗传算法的基本理论与应用.北京:科学出版社,2003.115-119.

[17] Lu TS. Random Functional Analysis and Its Application. Qingdao: Qingdao Ocean University Press, 1990. 44-100 (in Chinese). 卢同善.随机泛函分析及应用.青岛:青岛海洋大学出版社,1990.44-100.