Improving differential evolution with a new selection method of parents for mutation

doi:10.1007/s11704-015-4480-8

Front. Comput. Sci.

2016, Vol. 10

Issue (2) : 246-269 https://doi.org/10.1007/s11704-015-4480-8

RESEARCH ARTICLE

Improving differential evolution with a new selection method of parents for mutation

Yiqiao CAI(

),Yonghong CHEN,Tian WANG,Hui TIAN

College of Computer Science and Technology, Huaqiao University, Xiamen 361021, China

Download: PDF(1158 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

In differential evolution (DE), the salient feature lies in its mutationmechanismthat distinguishes it from other evolutionary algorithms. Generally, for most of the DE algorithms, the parents for mutation are randomly chosen from the current population. Hence, all vectors of population have the equal chance to be selected as parents without selective pressure at all. In this way, the information of population cannot be fully exploited to guide the search. To alleviate this drawback and improve the performance of DE, we present a new selection method of parents that attempts to choose individuals for mutation by utilizing the population information effectively. The proposed method is referred as fitnessand- position based selection (FPS), which combines the fitness and position information of population simultaneously for selecting parents in mutation of DE. In order to evaluate the effectiveness of FPS, FPS is applied to the original DE algorithms, as well as several DE variants, for numerical optimization. Experimental results on a suite of benchmark functions indicate that FPS is able to enhance the performance of most DE algorithms studied. Compared with other selection methods, FPS is also shown to be more effective to utilize information of population for guiding the search of DE.

Keywords differential evolution mutation operator parents selection population information numerical optimization

Corresponding Author(s): Yiqiao CAI

Just Accepted Date: 22 April 2015 Issue Date: 16 March 2016

Cite this article:

Yiqiao CAI,Yonghong CHEN,Tian WANG, et al. Improving differential evolution with a new selection method of parents for mutation[J]. Front. Comput. Sci., 2016, 10(2): 246-269.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-015-4480-8
https://academic.hep.com.cn/fcs/EN/Y2016/V10/I2/246

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 https://doi.org/10.1023/A:1008202821328
2	Das S, Suganthan P N. Differential evolution: a survey of the state-ofthe-art. IEEE Transactions on Evolutionary Computation, 2011, 15(1):4–31 https://doi.org/10.1109/TEVC.2010.2059031
3	Plagianakos V, Tasoulis D, Vrahatis M. A review of major application areas of differential evolution. Advances in Differential Evolution,2008, 143: 197–238 https://doi.org/10.1007/978-3-540-68830-3_8
4	Zhou Y, Wang J. A local search-based multiobjective optimization algorithm for multiobjective vehicle routing problem with time windows. IEEE Systems Journal, 2014, 99: 1–14
5	Wang J, Cai Y. Multiobjective evolutionary algorithm for frequency assignment problem in satellite communications. Soft Computing, 2015,19(5): 1229–1253 https://doi.org/10.1007/s00500-014-1337-2
6	Neri F, Tirronen V. Recent advances in differential evolution: a survey and experimental analysis. Artificial Intelligence Review, 2010, 33(1/2): 61–106 https://doi.org/10.1007/s10462-009-9137-2
7	Qin A, Huang V, Suganthan PN. Differential evolution algorithm withstrategy adaptation for global numerical optimization. IEEE Transactionson Evolutaionry Computation, 2009, 13(2): 398–417 https://doi.org/10.1109/TEVC.2008.927706
8	Brest J, Greiner S, Boskovíc B, Mernik M, Zumer V. Self-adaptingcontrol parameters in differential evolution: a comparative study onnumerical benchmark problems. IEEE Transactions on EvolutionaryComputation, 2006, 10(6): 646–657 https://doi.org/10.1109/TEVC.2006.872133
9	Yu W, Shen M, Chen W, Zhan Z, Gong Y, Lin Y, Liu O, Zhang J. Differential evolution with two-level parameter adaptation. IEEE Transactionson Cybernetics, 2014, 44(7): 2168–2267
10	Tang L, Dong Y, Liu J. Differential evolution with an individualdependent mechanism. IEEE Transactions on Evolutionary Computation, 2014, 99
11	Zhang J, Sanderson A. JADE: adaptive differential evolution with optional external archive. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 945–958 https://doi.org/10.1109/TEVC.2009.2014613
12	Cai Y, Wang J. Differential evolution with neighborhood and directioninformation for numerical optimization. IEEE Transactions on Cybernetics, 2013, 43 (6): 2202–2215 https://doi.org/10.1109/TCYB.2013.2245501
13	Das S, Abraham A, Chakraborty U K, Konar K. Differential evolutionusing a neighborhood-based mutation operator. IEEE Transactions on Evolutionary Computation, 2009, 13(3): 526–553 https://doi.org/10.1109/TEVC.2008.2009457
14	Wang J, Liao J, Zhou Y, Cai Y. Differential evolution enhanced with multiobjective sorting based mutation operators. IEEE Transactions on Cybernetics, 2014, 46(12): 2792–2805 https://doi.org/10.1109/TCYB.2014.2316552
15	Wang Y, Cai Z, Zhang Q. Differential evolution with composite trialvector generation strategies and control parameters. IEEE Transactionson Evolutionary Computation, 2011, 15(1): 55–66 https://doi.org/10.1109/TEVC.2010.2087271
16	Sun J, Zhang Q, Tsang EPK. DE/EDA: a new evolutionary algorithm for global optimization. Information Sciences, 2005, 169(3): 249–262 https://doi.org/10.1016/j.ins.2004.06.009
17	Xin B, Chen J, Zhang J, Fang H, Peng Z. Hybridizing differential evolution and particle swarm optimization to design powerful optimizers: a review and taxonomy. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2012, 42(5): 744–767 https://doi.org/10.1109/TSMCC.2011.2160941
18	Li Y, Zhan Z, Gong Y, Chen W, Zhang J, Li Y. Differential evolution with an evolution path: a deep evolutionary algorithm. IEEE Transactionson Cybernetics, 2014, 99
19	Dorronsoro B, Bouvry P. Improving classical and decentralized differential evolution with new mutation operator and population topologies. IEEE Transactions on Evolutionary Computation, 2011, 15(1): 67–98 https://doi.org/10.1109/TEVC.2010.2081369
20	Weber M, Tirronen V, Neri F. Scale factor inheritance mechanismin distributed differential evolution. Soft Computing, 2010, 14(11):1187–1207 https://doi.org/10.1007/s00500-009-0510-5
21	Noman N, Iba H. Accelerating differential evolution using an adaptivelocal search. IEEE Transactions on Evolutionary Computation, 2008,12(1): 107–125 https://doi.org/10.1109/TEVC.2007.895272
22	Epitropakis MG, Tasoulis DK, Pavlidis NG, Plagianakos PV, Vrahatis MN. Enhancing differential evolution utilizing proximity based mutation operators. IEEE Transactions on Evolutioanry Computation, 2011,15(1): 99–119 https://doi.org/10.1109/TEVC.2010.2083670
23	Gong W, Cai Z. Differential evolution with ranking-based mutation operators. IEEE Transactions on Cybernetics, 2013, 43(6): 2066–2081 https://doi.org/10.1109/TCYB.2013.2239988
24	Wang H, Rahnamayan S, Hui S, Omran MG. Gaussian barebones differential evolution. IEEE Transactions on Cybernetics, 2013, 43(2):634–647 https://doi.org/10.1109/TSMCB.2012.2213808
25	Cai Y, Wang J, Chen Y, Tian W, Hui T. Adaptive direction informationin differential evolution for numerical optimization. Soft Computing, 2014
26	Mallipeddi R, Suganthan P N, Pan Q, Tasgetiren M. Differential evolution algorithm with ensemble of parameters and mutation strategies. Applied Soft Computing, 2011, 11(2): 1679–1696 https://doi.org/10.1016/j.asoc.2010.04.024
27	Gong W, Cai Z, Ling CX, Li H. Enhanced differential evolution with adaptive strategies for numerical optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2011, 41(2):397–413 https://doi.org/10.1109/TSMCB.2010.2056367
28	García-Martínez C, Rodríguez F, Lozano M. Role differentiation andmalleable mating for differential evolution: an analysis on large-scale optimization. Soft Computing, 2011, 15(11): 2109–2126 https://doi.org/10.1007/s00500-010-0641-8
29	Chen G, Low C, Yang Z. Preserving and exploiting genetic diversityin evolutionary programming algorithms. IEEE Transactions on Evolutionary Computation, 2009, 13(3): 661–673 https://doi.org/10.1109/TEVC.2008.2011742
30	Cai Y, Wang J, Yin J. Learning-enhanced differential evolution for numerical optimization. Soft Computing, 2012, 16(2): 303–330 https://doi.org/10.1007/s00500-011-0744-x
31	Baeck T, Fogel D B, Michalewicz Z. Handbook of evolutionary computation. New York: Taylor & Francis, 1997 https://doi.org/10.1887/0750308958
32	Suganthan P N, Hansen N, Liang J, Deb K, Chen Y, Auger A, Tiwari S. Problem definitions and evaluation criteria for the CEC 2005 specialsession on real-parameter optimization. KanGAL Report Number2005005. 2005
33	Rahnamayan S, Tizhoosh H R, Salama M M A. Opposition based differential evolution. IEEE Transactions on Evolutionary Computation, 2008, 12(1): 64–79 https://doi.org/10.1109/TEVC.2007.894200
34	Wilcoxon F. Individual comparisons by ranking methods. Biometrics, 1945, 1(6): 80–83 https://doi.org/10.2307/3001968
35	García S,Fernández A, Luengo J, Herrera F. A study of statistical techniques and performance measures for genetics-based machine learning: accuracy and interpretability. Soft Computing, 2009, 13(10): 959–977 https://doi.org/10.1007/s00500-008-0392-y
36	Derrac J, García S, Molina D, Herrera F. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation, 2011, 1(1): 3–18 https://doi.org/10.1016/j.swevo.2011.02.002
37	Alcalá-Fdez J, Sánchez L, García S. KEEL: A software tool to assess evolutionary algorithms to data mining problems. Soft Computing, 2009, 13(3): 307–318 https://doi.org/10.1007/s00500-008-0323-y
38	Das S, Suganthan P N. Problem definitions and evaluation criteria for CEC 2011 competition on testing evolutionary algorithms on realworld optimization problems. Technical Report. 2010
39	Chow C K, Yuen S Y. An evolutionary algorithm that makes decisionbased on the entire previous search history. IEEE Transactions on Evolutionary Computation, 2011, 15(6): 741–769 https://doi.org/10.1109/TEVC.2010.2040180
40	Zhou X, Wu Z, Wang H, Rahnamayan S. Enhancing differential evolution with role assignment scheme. Soft Computing, 2013, 18(11): 2209–2225 https://doi.org/10.1007/s00500-013-1195-3
41	Guo WZ, Liu G G, Chen G L, Peng S J. A hybrid multi-objective PSOalgorithm with local search strategy for VLSI partitioning. Frontiers of Computer Science, 2014, 8(2): 203–216 https://doi.org/10.1007/s11704-014-3008-y
42	Zhang Y, Gong D W. Generating test data for both paths coverage and faults detection using genetic algorithms: multi-path case. Frontiers of Computer Science, 2014, 8(5): 726–740 https://doi.org/10.1007/s11704-014-3372-7

[1]

FCS-0246-14480-YQC_suppl_1

Download

[1]	Wenting ZHAO, Lijin WANG, Yilong YIN, Bingqing WANG, Yuchun TANG. Sequential quadratic programming enhanced backtracking search algorithm[J]. Front. Comput. Sci., 2018, 12(2): 316-330.
[2]	Yong WANG, Zhi-Zhong LIU, Jianbin LI, Han-Xiong LI, Jiahai WANG. On the selection of solutions for mutation in differential evolution[J]. Front. Comput. Sci., 2018, 12(2): 297-315.
[3]	Yu HAN,Guozhu JIA. Optimizing product manufacturability in 3D printing[J]. Front. Comput. Sci., 2017, 11(2): 347-357.
[4]	Xiaojun BI, Jing XIAO. Classification-based self-adaptive differential evolution and its application in multi-lateral multi-issue negotiation[J]. Front Comput Sci, 2012, 6(4): 442-461.
[5]	Maryjane TREMAYNE, Samantha Y. CHONG, Duncan BELL. Optimisation of algorithm control parameters in cultural differential evolution applied to molecular crystallography[J]. Front Comput Sci Chin, 2009, 3(1): 101-108.
[6]	Yong WANG, Zixing CAI. A hybrid multi-swarm particle swarm optimization to solve constrained optimization problems[J]. Front Comput Sci Chin, 2009, 3(1): 38-52.

Viewed

Full text

Abstract

Cited

Shared

Discussed