Effect of strategy adaptation on differential evolution in presence and absence of parameter adaptation: an investigation

• Autorzy: Dawar D. , Ludwig S. A.

Identyfikatory

DOI

10.1515/jaiscr-2018-0014

• Języki publikacji: EN

Abstrakty

EN

Differential Evolution (DE) is a simple, yet highly competitive real parameter optimizer in the family of evolutionary algorithms. A significant contribution of its robust performance is attributed to its control parameters, and mutation strategy employed, proper settings of which, generally lead to good solutions. Finding the best parameters for a given problem through the trial and error method is time consuming, and sometimes impractical. This calls for the development of adaptive parameter control mechanisms. In this work, we investigate the impact and efficacy of adapting mutation strategies with or without adapting the control parameters, and report the plausibility of this scheme. Backed with empirical evidence from this and previous works, we first build a case for strategy adaptation in the presence as well as in the absence of parameter adaptation. Afterwards, we propose a new mutation strategy, and an adaptive variant SA-SHADE which is based on a recently proposed self-adaptive memory based variant of Differential evolution, SHADE. We report the performance of SA-SHADE on 28 benchmark functions of varying complexity, and compare it with the classic DE algorithm (DE/Rand/1/bin), and other state-of-the-art adaptive DE variants including CoDE, EPSDE, JADE, and SHADE itself. Our results show that adaptation of mutation strategy improves the performance of DE in both presence, and absence of control parameter adaptation, and should thus be employed frequently.

Słowa kluczowe

EN

evolutionary algorithms; differential evolution; mutation strategy; adaptive control

• Wydawca: University of Social Sciences
• Czasopismo: Journal of Artificial Intelligence and Soft Computing Research
• Rocznik: 2018
• Tom: Vol. 8, No. 3
• Strony: 211--235
• Opis fizyczny: Bibliogr. 66 poz., rys.

Twórcy

autor

Dawar D.

• Department of Computer and Information Technology, Miami University Hamilton, Ohio, USA

autor

Ludwig S. A.

• Department of Computer Science, North Dakota State University, Fargo, ND, USA

Bibliografia

• [1] A. E. Eiben, R. Hinterding, Z. Michalewicz, Parameter control in evolutionary algorithms, IEEE Transactions on Evolutionary Computation, 3 (2), 124– 141, 1999.
• [2] G. Beni, J. Wang, Swarm Intelligence in Cellular Robotic Systems, in: Proceedings of the NATO Advanced Workshop on Robots and Biological Systems. Tuscany, Italy, 1989.
• [3] P.J. Angeline, Adaptive and self-adaptive evolutionary computation, in: M. Palaniswami, Y. Attikiouzel, R.J. Marks, D.B. Fogel, T. Fukuda (Eds.), Computational Intelligence: A Dynamic System Perspective, IEEE Press, pp. 152–161, 1995.
• [4] J. Gomez, D. Dasgupta, F. Gonazalez, Using adaptive operators in genetic search, in: Proceedings of the Genetic and Evolutionary Computation Conference 2003 (GECCO03), Chicago, Illinois, USA, pp. 1580–1581, 2003.
• [5] B. R. Julstrom, What have you done for me lately? Adapting operator probabilities in a steady-state genetic algorithm, in: Proceedings of the 6th International Conference on Genetic Algorithms, Pittsburgh, PA, USA, pp. 81-87, 1995.
• [6] J. E. Smith, T.C. Fogarty, Operator and parameter adaptation in genetic algorithms, Soft Computing 1, pp. 81-87, 1997.
• [7] A. Tuson, P. Ross, Adapting operator settings in genetic algorithms, Evolutionary Computation 6, pp. 161-184, 1998.
• [8] R. M. Storn, K. V. Price, Differential evolution -A simple and efficient adaptive scheme for global optimization over continuous spaces, International Computer Science Institute, Berkeley, CA, USA, ICSI Technical Report 95-012, 1995.
• [9] S. Das, P. N. Suganthan, Differential evolution – A survey of the state-of-the-art, IEEE Transactions on Evolutionary Computation, 15 (1), pp. 4–31, 2011.
• [10] R. M. Storn, K. V. Price, Minimizing the real functions of the ICEC 1996 contest by differential evolution, in: Proceedings of IEEE International Conference on Evolutionary Computation, pp. 842–844, 1996.
• [11] J. Liu, J. Lampinen, On setting the control parameter of the differential evolution method, in: Proceedings of 8th Int. Conference Soft Computing (MENDEL), pp. 11–18, 2002.
• [12] R. Gamperle, S. D. Muller, P. Koumoutsakos, A parameter study for differential evolution, NNAFSFS-EC 2002, Interlaken, Switzerland, WSEAS, pp. 11–15, 2002.
• [13] A. E. Eiben, J. E. Smith, Introduction to Evolutionary Computing, Natural Computing. Berlin, Germany: Springer-Verlag, 2003.
• [14] K. Price, R. Storn, J. Lampinen, Differential Evolution - A Practical Approach to Global Optimization, Berlin, Germany: Springer, 2005.
• [15] S. Das, A. Konar, U. K. Chakraborty, Two improved Differential Evolution schemes for faster global search, in Proceedings of ACM-SIGEVO GECCO, pp. 991–998, 2005.
• [16] H. A. Abbass, The self-adaptive pareto differential evolution algorithm, in Proceedings of the 2002 IEEE Congress on Evolutionary Computation, Honolulu, Hawaii, USA, 1, pp. 831–836, 2002.
• [17] J. Brest, S. Greiner, B. Boskovic, M. Mernik, V. Zumer, Self adapting control parameters in differential evolution: A comparative study on numerical benchmark problems, IEEE Transactions on Evolutionary Computation, 10 (6), pp. 646–657, 2006.
• [18] A. Zamuda, J. Brest, Self-adaptive control parameters randomization frequency and propagations in differential evolution. Swarm and Evolutionary Computation, 25(1), pp. 72–99, 2015.
• [19] A. K. Qin, V. L. Huang, P. N. Suganthan, Differential evolution algorithm with strategy adaptation for global numerical optimization, IEEE Transactions on Evolutionary Computation 13, pp. 398–417, 2009.
• [20] M. G. H. Omran, A. Salman, A. P. Engelbrecht, Self-adaptive differential evolution, in: Computational Intelligence and Security, PT 1, Proceedings Lecture Notes in Artificial Intelligence, pp. 192-199, 2005.
• [21] D. Zaharie, Control of population diversity and adaptation in differential evolution algorithms, in: Proceedings of the 9th International Conference on Soft Computing, Brno, pp. 41-46, 2003.
• [22] J. Tvrdik, Adaptation in differential evolution: a numerical comparison, Applied Soft Computing 9, pp. 1149–1155, 2009.
• [23] R. Mallipeddi, P. N. Suganthana, Q. K. Pan, M. F. Tasgetiren, Differential evolution algorithm with ensemble of parameters and mutation strategies, Applied Soft Computing, 11 (2), pp. 1679–1696, 2011.
• [24] R. Storn, K. Price, Differential evolution A simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, 11, pp. 341–359, 1997.
• [25] J. Lampinen, I. Zelinka, On stagnation of the differential evolution algorithm, in: Proceedings of MENDEL 2000, 6th International Mendel Conference on Soft Computing, pp. 76–83, 2000.
• [26] J. Ronkkonen, S. Kukkonen, K. V. Price, Real parameter optimization with differential evolution, in Proceedings of IEEE Congress on Evolutionary Computation, 1, pp. 506–513, 2005.
• [27] J. Liu, J. Lampinen, A Fuzzy Adaptive Differential Evolution Algorithm, in: Soft Computing, A Fusion of Foundations, Methodologies and Applications, 9 (6), pp. 448–462, 2005.
• [28] F. Neri, V. Tirronen, Recent advances in differential evolution: a survey and experimental analysis Artificial Intelligence Review, 33 (1-2), pp. 61–106, 2010.
• [29] J. Ronkkonen, J. Lampinen, On using normally distributed mutation step length for the differential evolution algorithm, in: Proceedings of the 9th Int. Conf. on Soft Computuing MENDEL, Brno, Czech Republic, pp. 11–18, 2003.
• [30] A. K. Qin, P. N. Suganthan, Self-adaptive Differential Evolution Algorithm for Numerical Optimization, in: Proceedings of the IEEE Congress on Evolutionary Computation, 2005.
• [31] M. M. Ali, A. Trn, Population set based global optimization algorithms: Some modifications and numerical studies, Journal of Computers and Operations Research, 31 (10), pp. 1703–1725, 2004.
• [32] U. K. Chakraborty, Advances in Differential Evolution, in: Differential Evolution Research-Trends and Open Questions, Springer, pp. 11–12, 2008.
• [33] D. Dawar, S. A. Ludwig, Differential evolution with dither and annealed scale factor, in: Proceedings of the IEEE Symposium Series on Computational Intelligence, Orlando, Florida, U.S.A., pp. 1– 8, 2014.
• [34] J. Teo, Exploring dynamic self-adaptive populations in differential evolution, Soft Computing – A Fusion of Foundations, Methodologies and Applications, 10 (8), pp. 673–686, 2006.
• [35] J. Brest, M. S. Mauec, Population size reduction for the differential evolution algorithm, Applied Intelligence, 29 (3), pp. 228–247, 2008.
• [36] J. Zhang, A. C. Sanderson, JADE: Adaptive differential evolution with optional external archive, IEEE Transaction on Evolutionary Computation, 13 (5), pp. 945-958, 2009.
• [37] E. Mezura-Montes, J. Velazquez-Reyes, C. A. Coello Coello, A comparative study of differential evolution variants for global optimization, in GECCO, pp. 485–492, 2006.
• [38] F. Peng, K. Tang, G. Chen, X. Yao, Multi-start JADE with knowledge transfer for numerical optimization, in: Proceedings of the IEEE CEC, pp. 1889–1895, 2009.
• [39] Z. Yang, J. Zhang, K. Tang, X. Yao, A. C. Sanderson, An adaptive coevolutionary differential evolution algorithm for large-scale optimization, in: Proceedings of the IEEE CEC, pp. 102–109, 2009.
• [40] W. Gong, Z. Cai, C. X. Ling, H. Li, Enhanced differential evolution with adaptive strategies for numerical optimization, IEEE Transactions on Systems, Man, and Cybernetics, PartB, 41 (2), pp. 397–413, 2011.
• [41] J. Zhang, V. Avasarala, A. C. Sanderson, T. Mullen, Differential evolution for discrete optimization: An experimental study on combinatorial auction problems, in: Proceedings of the IEEE CEC, pp. 2794–2800, 2008.
• [42] J. Zhang, A. C. Sanderson, Self-adaptive multiobjective differential evolution with direction information provided by archived inferior solutions, in: Proceedings of the IEEE CEC, pp. 2801–2810, 2008.
• [43] R. Tanabe, A. Fukunaga, Success-History Based Parameter Adaptation for Differential Evolution, in: Proceedings of the IEEE CEC, pp. 71–78, 2013.
• [44] R. Tanabe, A. Fukunaga, Evaluating the performance of SHADE on CEC 2013 benchmark problems, in: Proceedings of the IEEE CEC, pp. 1952–1959, 2013.
• [45] A. Auger, N. Hansen, A Restart CMA Evolution Strategy With Increasing Population Size, in: Proceedings of the IEEE CEC, pp. 1769–1776, 2005.
• [46] C. Garca-Martnez, M. Lozano, F. Herrera, D. Molina, A. M. Sanchez, Global and local realcoded genetic algorithms based on parent-centric crossover operators, European Journal of Operations Research, 185 (3), pp. 1088–1113, 2008.
• [47] M. A. M. de Oca, T. St utzle, K. V. den Enden, M. Dorigo, Incremental Social Learning in Particle Swarms, IEEE Transactions on Systems, Man, and Cybernetics, PartB, 41 (2), pp. 368–384, 2011.
• [48] J. L. J. Laredo, C. Fernandes, J. J. M. Guervos, C. Gagne, Improving Genetic Algorithms Performance via Deterministic Population Shrinkage, in: Proceedings of the GECCO, pp. 819–826, 2009.
• [49] R. Tanabe, A. Fukunaga, Improving the Search Performance of SHADE Using Linear Population Size Reduction, in: Proceedings of the IEEE CEC, pp. 1658–1665, 2014.
• [50] J. Brest, A. Zamuda, B. Boskovic, M. S. Maucec, V. Zumer, Highdimensional real-parameter optimization using self-adaptive differential evolution algorithm with population size reduction, in: Proceedings of the IEEE Congress on Evolutionary Computation, pp. 2032–2039, 2008.
• [51] A. Zamuda, J. Brest. Population Reduction Differential Evolution with Multiple Mutation Strategies in Real World Industry Challenges. Artificial Intelligence and Soft Computing – ICAISC 2012, 7269, pp. 154–161, 2012.
• [52] J. J. Liang, B.Y. Qu, P. N. Suganthan, A. G. Hernandez-Daz, Problem definitions and evaluation criteria for the CEC 2013 special session on realparameter optimization, Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou, China and Nanyang, 2013.
• [53] A. K. Qin, Xiaodong Li, Differential Evolution on the CEC-2013 Single-Objective Continuous Optimization Testbed, IEEE Congress on Evolutionary Computation, Cancun, Mexico, June 20-23, 2013.
• [54] M. Friedman, The use of ranks to avoid the assumption of normality implicit in the analysis of variance, Journal of the American Statistical Association 32, pp. 674–701, 1937.
• [55] D. J. Sheskin, Handbook of Parametric and Nonparametric Statistical Procedures, 4th ed., Chapman and Hall/CRC, 2006.
• [56] J. H. Zar, Biostatistical Analysis, Prentice Hall, 2009.
• [57] Y. Hochberg, A sharper Bonferroni procedure for multiple tests of significance, Biometrika, pp. 800–803, 1988.
• [58] J. Derrac, S. Garca, D. Molina, F. Herrera, A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms, Swarm and Evolutionary Computation, vol 1, pp. 3–18, 2011.
• [59] B. V. Babu, S. A. Munawar, Optimal design of shell-and-tube heat exchangers bu different strategies of Differential Evolution, Technical Report PILANI -333 031, Department of chemical engineering, BITS, Rajasthan, India, 2001.
• [60] J. Vesterstrom, R. A. Thomson, Comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems, in: Proceedings of the IEEE Congress on Evolutionary Computation, 1980–1987, 2004.
• [61] X. F. Xie, W. J. Zhang. SWAF: Swarm algorithm framework for numerical optimization, in: Proceedings of the Genetic Evolutionary Computation Conference, Part I, pp. 238–250, 2004.
• [62] A. Zamuda, J. Brest, B. Bokovic, V. umer. Large scale global optimization using differential evolution with self-adaptation and cooperative coevolution, in: Proceedings of the 2008 IEEE World Congress on Computational Intelligence, pp. 3719–3726, 2008.
• [63] Z. Yang, K. Tang, X. Yao. Self-adaptive differential evolution with neighborhood search. In Proceedings of the IEEE Congress on Evolutionary Computation, pp. 1110–1116, 2008.
• [64] A. Iorio, X. Li, Solving rotated multi-objective optimization problems using differential evolution, in: Australian Conference on Artificial Intelligence, Cairns, Australia, pp. 861–872, 2004.
• [65] S. Das, A. Abraham, U.K. Chakraborthy, Differential evolution using a neighborhood-based mutation operator, IEEE Transactions on Evolutionary Computation 13, pp. 526–553, 2009.
• [66] D. H. Wolpert, W. G. Macready, No Free Lunch Theorems for Optimization, IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 67–82, 1997.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).