›› 2012, Vol. 27 ›› Issue (5): 1035-1055.doi: 10.1007/s11390-012-1283-3

• Special Issue on Evolutionary Computation • Previous Articles     Next Articles

Differential Evolution with Adaptive Mutation and Parameter Control Using Lévy Probability Distribution

Ren-Jie He (贺仁杰) and Zhen-Yu Yang (杨振宇), Member, CCF, ACM, IEEE   

  1. Department of Management Science and Engineering, College of Information System and Management, National University of Defense Technology, Changsha 410073, China
  • Received:2011-10-14 Revised:2012-02-23 Online:2012-09-05 Published:2012-09-05
  • Supported by:

    This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 71071106 and 70801062.

Differential evolution (DE) has become a very popular and effective global optimization algorithm in the area of evolutionary computation. In spite of many advantages such as conceptual simplicity, high e眂iency and ease of use, DE has two main components, i.e., mutation scheme and parameter control, which significantly influence its performance. In this paper we intend to improve the performance of DE by using carefully considered strategies for both of the two components. We first design an adaptive mutation scheme, which adaptively makes use of the bias of superior individuals when generating new solutions. Although introducing such a bias is not a new idea, existing methods often use heuristic rules to control the bias. They can hardly maintain the appropriate balance between exploration and exploitation during the search process, because the preferred bias is often problem and evolution-stage dependent. Instead of using any fixed rule, a novel strategy is adopted in the new adaptive mutation scheme to adjust the bias dynamically based on the identified local fitness landscape captured by the current population. As for the other component, i.e., parameter control, we propose a mechanism by using the Lévy probability distribution to adaptively control the scale factor F of DE. For every mutation in each generation, an Fi is produced from one of four different Lévy distributions according to their historical performance. With the adaptive mutation scheme and parameter control using Lévy distribution as the main components, we present a new DE variant called Lévy DE (LDE). Experimental studies were carried out on a broad range of benchmark functions in global numerical optimization. The results show that LDE is very competitive, and both of the two main components have contributed to its overall performance. The scalability of LDE is also discussed by conducting experiments on some selected benchmark functions with dimensions from 30 to 200.

[1] Storn R, Price K. Differential evolution —— A simple and e±-cient heuristic for global optimization over continuous spaces.Journal of Global Optimization, 1997, 11(4): 341-359.
[2] Price K, Storn R, Lampinen J. Differential Evolution: APractical Approach to Global Optimization. Springer-Verlag,2005.
[3] Chakraborty (ed.) U K. Advances in Differential Evolution.Springer-Verlag, 2008.
[4] Das S, Suganthan P N. Differential evolution: A survey ofthe state-of-the-art. IEEE Trans. Evolutionary Computa-tion, 2011, 15(1): 4-31.
[5] Das S, Abraham A, Chakraborty U K, Konar A. Differen-tial evolution using a neighborhood-based mutation operator.IEEE Trans. Evolutionary Computation, 2009, 13(3): 526-553.
[6] Zhang J, Sanderson A C. JADE: Adaptive differential evolu-tion with optional external archive. IEEE Trans. Evolution-ary Computation, 2009, 13(5): 945-958.
[7] Qin A K, Huang V L, Suganthan P N. Differential evolutionalgorithm with strategy adaptation for global numerical op-timization. IEEE Trans. Evolutionary Computation, 2009,13(2): 398-417.
[8] Yang Z, Tang K, Yao X. Self-adaptive differential evolutionwith neighborhood search. In Proc. the 2008 IEEE Congresson Evolutionary Computation, June 2008, pp.1110-1116.
[9] Gämperle R, Müller S D, Koumoutsakos P. A Parameterstudy for differential evolution. In Proc. WSEAS Interna-tional Conference on Advances in Intelligent Systems, FuzzySystems, Evolutionary Computation, 2002, pp.293-298.
[10] Wang Y, C Z, Zhang Q. Differential evolution with compo-site trial vector generation strategies and control parameters.IEEE Trans. Evolutionary Computation, 2011, 15(1): 55-66.
[11] Brest J, Greiner S, Boskovic B, Mernik M, Zumer V. Self-adapting control parameters in differential evolution: A com-parative study on numerical benchmark problems. IEEETrans. Evolutionary Computation, 2006, 10(6): 646-657.
[12] Das S, Konar A, Chakraborty U K. Two improved differentialevolution schemes for faster global search. In Proc. the 2005Conf. Genetic and Evolutionary Computation, June 2005,pp.991-998.
[13] Abbass H A. The self-adaptive Pareto differential evolutionalgorithm. In Proc. the 2002 IEEE Congress on Evolution-ary Computation, May 2002, pp.831-836.
[14] Salman A, Engelbrecht A, Omran M. Empirical analysis ofself-adaptive differential evolution. European Journal of Ope-rational Research, 2007, 183(2): 785-804.
[15] Yang Z, He J, Yao X. Making a difference to differential evo-lution. In Advances in Metaheuristics for Hard Optimization,Michalewicz, Z, Siarry P (eds.), Springer, 2008, pp.397-414.
[16] Bäck T, Schwefel H P. An overview of evolutionary algo-rithms for parameter optimization. Evolutionary Computa-tion, 1993, 1(1): 1-23.
[17] Yao X, Liu Y, Lin G. Evolutionary programming made faster.IEEE Trans. Evolutionary Computation, 1999, 3(2): 82-102.
[18] Lee C Y, Yao X. Evolutionary programming using mutationsbased on the Lévy probability distribution. IEEE Trans.Evolutionary Computation, 2004, 8(1): 1-13.
[19] Storn R. System design by constraint adaptation and diffe-rential evolution. IEEE Trans. Evolutionary Computation,1999, 3(1): 22-34.
[20] Yang Z, Tang K, Yao X. Scalability of generalized adaptivedifferential evolution for large-scale continuous optimization.Soft Computing, 2011, 15(11): 2141-2155.
[21] Wang Y, Cai Z, Zhang Q. Enhancing the search ability of dif-ferential evolution through orthogonal crossover. InformationSciences, 2012, 185(1): 153-177.
[22] Lévy P. Théorie de l'addition des variables aléatoires.Gauthier-Villars Paris, 1937.
[23] Gnedenko B, Kolmogorov A. Limit Distribution for Sumsof Independent Random Variables. Cambridge, MA, USA:Addition-Wesley, 1954.
[24] Qin A K, Suganthan P N. Self-adaptive differential evolu-tion algorithm for numerical optimization. In Proc. the2005 IEEE Congress on Evolutionary Computation, Vol.2,September 2005, pp.1785-1791.
[25] Peng F, Tang K, Chen G, Yao X. Population-based algorithmportfolios for numerical optimization. IEEE Trans. Evolu-tionary Computation, 2010, 14(5): 782-800.
[26] Shen L, He J. A mixed strategy for evolutionary programmingbased on local fitness landscape. In Proc. the 2010 IEEECongress on Evolutionary Computation, July 2010, pp.1-8.
[27] Yao X, Lin G, Liu Y. An analysis of evolutionary algorithmsbased on neighbourhood and step sizes. In Proc. the 6thInternational Conference on Evolutionary Programming VI,April 1997, pp.297-307.
[28] Schwefel H P. Evolution and Optimum Seeking. John Wiley& Sons, 1995.
[29] Suganthan P N, Hansen N, Liang J J, Deb K, Chen Y P, AugerA, Tiwari S. Problem definitions and evaluation criteria forthe CEC 2005 special session on real-parameter optimization.Technical Report, Nanyang Technological University, Singa-pore, 2005.
[30] Yang Z, Tang K, Yao X. Large scale evolutionary optimizationusing cooperative coevolution. Information Sciences, 2008,178(15): 2985-2999.
[31] Hansen N, Auger A, Finck S, Ros R. Real-parameter black-box optimization benchmarking 2010: Experimental setup.Institut National de Recherche en Informatique et en Automa-tique (INRIA), 2010.
[32] Hansen N. Compilation of results on the 2005 CEC bench-mark function set. Technical Report, Computational Labora-tory, Institute of Computational Science, ETH Zurich, 2005.
[33] Liu Y, Yao X, Zhao Q, Higuchi T. Scaling up fast evolu-tionary programming with cooperative coevolution. In Proc.the 2001 IEEE Congress on Evolutionary Computation, May2001, pp.1101-1108.
[34] van den Bergh F, Engelbrecht A P. A cooperative approachto particle swarm optimization. IEEE Trans. EvolutionaryComputation, 2004, 8(3): 225-239.
[35] Li X, Yao X. Cooperatively coevolving particle swarms forlarge scale optimization. IEEE Trans. Evolutionary Compu-tation, 2012, 16(2): 210-224.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Cai Shijie; Zhang Fuyan;. A Fast Algorithm for Polygon Operations[J]. , 1991, 6(1): 91 -96 .
[2] Jiang Wenbin;. A Method for Minimization Design of Two-Level Logic Networks Using Multiplexer Universal Logic Modules[J]. , 1994, 9(1): 92 -96 .
[3] Huang Guoyong; Li Sanli;. TSP: A Heterogeneous Multiprocessor Supercomputing System Based on i860XP[J]. , 1994, 9(3): 285 -288 .
[4] Ju-Hum Kwon, Chee-Yang Song, Chang-Joo Moon, and Doo-Kwon Baik. Bridging Real World Semantics to Model World Semantics for Taxonomy Based Knowledge Representation System[J]. , 2005, 20(3): 296 -308 .
[5] Bo Yan, You-Xing Qu, Feng-Lou Mao, Victor N. Olman, and Ying Xu. PRIME: A Mass Spectrum Data Mining Tool for De Novo Sequencing and PTMs Identification[J]. , 2005, 20(4): 483 -490 .
[6] I-Shyan Hwang, I-Feng Huang, and Shin-Cheng Yu. Dynamic Fuzzy Controlled RWA Algorithm for IP/GMPLS over WDM Networks[J]. , 2005, 20(5): 717 -727 .
[7] Ian Foster. Globus Toolkit Version 4: Software for Service-Oriented Systems[J]. , 2006, 21(4): 513 -520 .
[8] Jie Liang and Xue-Jia Lai. Improved Collision Attack on Hash Function MD5[J]. , 2007, 22(1): 79 -87 .
[9] Li-Guo Yu and Srini Ramaswamy. Component Dependency in Object-Oriented Software[J]. , 2007, 22(3): 379 -386 .
[10] Jia Li, Li-Yong Shen, and Xiao-Shan Gao. Proper Reparametrization of Rational Ruled Surface[J]. , 2008, 23(2): 290 -297 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved