# American Institute of Mathematical Sciences

2012, 2(1): 57-67. doi: 10.3934/naco.2012.2.57

## Global optimization via differential evolution with automatic termination

 1 Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan 2 Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto, 606-8501

Received  April 2011 Revised  July 2011 Published  March 2012

Evolutionary Algorithms (EAs) provide a very powerful tool for solving optimization problems. In the last decades, numerous studies have been focusing on improving the performance of EAs. However, there is a lack of studies that tackle the question of the termination criteria. Indeed, EAs still need termination criteria prespecified by the user. In this paper, we propose to combine the Differential Evolution (DE) method with novel elements, i.e., the Gene Matrix'' (GM), the Space Decomposition'' (SD) and Space Rotation'' (SR) mechanisms, in order to equip DE with an automatic termination criterion without resort to predefined conditions. We name this algorithm Differential Evolution with Automatic Termination'' (DEAT). Numerical experiments using a test bed of widely used benchmark functions in 10, 50 and 100 dimensions show the effectiveness of the proposed method.
Citation: Bun Theang Ong, Masao Fukushima. Global optimization via differential evolution with automatic termination. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 57-67. doi: 10.3934/naco.2012.2.57
##### References:
 [1] S. Das and P. N. Suganthan, Differential evolution: A survey of the state-of-the-art, IEEE Transactions on Evolutionary Computation, 15 (2011), 4-31. doi: 10.1109/TEVC.2010.2059031.  Google Scholar [2] R. Gamperle, S. D. Muller and P. Koumoutsakos, A Parameter Study for Differential Evolution, in "Advances in intelligent systems, fuzzy systems, evolutionary computation" (eds. A. Grmela and N.E. Mastorakis), WSEAS Press, Interlaken, Switzerland, (2002), 293-298. Google Scholar [3] M. S. Giggs, H. R. Maier, G. C. Dandy and J. B. Nixon, Minimum number of generations required for convergence of genetic algorithms, in "Proceedings of 2006 IEEE Congress on Evolutionary Computation," Vancouver, BC, Canada, (2006), 2580-2587. Google Scholar [4] N. Hansen, The CMA evolution strategy: a comparing review , in "Towards a New Evolutionary Computation. Advances on Estimation of Distribution Algorithms"(eds. J.A. Lozano, P. Larranaga, I. Inza and E. Bengoetxea), Springer, (2006), 75-102. Google Scholar [5] A. R. Hedar and M. Fukushima, Minimizing multimodal functions by simplex coding genetic algorithm, Optimization Methods and Software, 18 (2003), 265-282.  Google Scholar [6] A. R. Hedar and M. Fukushima, Tabu search directed by direct search methods for nonlinear global optimization, European Journal of Operational Research, 170 (2006), 329-349. doi: 10.1016/j.ejor.2004.05.033.  Google Scholar [7] A. R. Hedar, B. T. Ong and M. Fukushima, Genetic algorithms with automatic accelerated termination, Technical report, Dept. of Applied Mathematics and Physics, Kyoto University, (2007). Google Scholar [8] B. J. Jain, H. Pohlheim and J. Wegener, On termination criteria of evolutionary algorithms, in "Proceedings of the Genetic and Evolutionary Computation Conference," Morgan Kaufmann Publishers, (2001), 768. Google Scholar [9] R. Joshi and A. C. Sanderson, Minimal representation multisensor fusion using differential evolution, IEEE Transactions on Systems, Man and Cybernetics (Part A), 29 (1999), 63-76. doi: 10.1109/3468.736361.  Google Scholar [10] C. T. Kelley, Detection and remediation of stagnation in the nelder-mead algorithm using a sufficient decrease condition, SIAM J. on Optimization, 10 (1999), 43-55. doi: 10.1137/S1052623497315203.  Google Scholar [11] N. M. Kwok, Q. P. Ha, D. K. Liu, G. Fang and K. C. Tan, Efficient particle swarm optimization: a termination condition based on the decision-making approach, in "Proceedings of the IEEE Congress on Evolutionary Computation," Singapore, (2007), 25-28. doi: 10.1109/CEC.2007.4424905.  Google Scholar [12] R. Mallipeddi, P. N. Suganthan, Q. K. Pan and M. F. Tasgetiren, Differential evolution algorithm with ensemble of parameters and mutation strategies, Applied Soft Computing, 11 (2011), 1679-1696. doi: 10.1016/j.asoc.2010.04.024.  Google Scholar [13] P. McMinn, Search-based software test data generation: A survey, Softw. Test. Verif. Reliab., 14 (2004), 105-156. doi: 10.1002/stvr.294.  Google Scholar [14] J. A. Nelder and R. Mead, A simplex method for function minimization, Computer Journal, 7 (1965), 308-313. Google Scholar [15] B. T. Ong and M. Fukushima, Genetic algorithm with automatic termination and search space rotation, Memetic Computing, 3 (2011), 111-127. doi: 10.1007/s12293-011-0057-8.  Google Scholar [16] M. O'Sullivan, S. Vssner and J. Wegener, Testing temporal correctness of real-time systems, in "EuroSTAR'98: Proceedings of the Sixth International Conference on Software Testing Analysis and Review," Munich, Germany, (1998). Google Scholar [17] K. V. Price, R. M. Storn and J. A. Lampinen, "Differential Evolution A Practical Approach to Global Optimization," Natural Computing Series, Springer-Verlag, Berlin, Germany, (2005). Google Scholar [18] A. K. Qin and P. N. Suganthan, Self-adaptive differential evolution algorithm for numerical optimization, in "The 2005 IEEE Congress on Evolutionary Computation," 2 (2005), 1785-1791. Google Scholar [19] R. Storn and K. Price, Differential evolution - a simple and efficient adaptive scheme for global optimization over continuous spaces, Technical Report TR-95-012, Online, (1995). Google Scholar [20] R. Storn and K. Price, Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces, J. of Global Optimization, 11 (1997), 341-359. doi: 10.1023/A:1008202821328.  Google Scholar [21] P. N. Suganthan, N. Hansen, J. J. Liang, K. Deb, Y. P. Chen, A. Auger and S. Tiwari, Problem definitions and evaluation criteria for the CEC -2005 special session on real-parameter optimization , Technical report, Singapore: Nanyang Technol. Univ., (2005). Google Scholar [22] J. Zhang, V. Avasarala, A. C. Sanderson and T. Mullen, Differential evolution for discrete optimization: An experimental study on combinatorial auction problems, in "Proceedings of the 10th IEEE Congress on Evolutionary Computation CEC 2008 (IEEE World Congress on Computational Intelligence)," (2008), 2794-2800. doi: 10.1109/CEC.2008.4631173.  Google Scholar

show all references

##### References:
 [1] S. Das and P. N. Suganthan, Differential evolution: A survey of the state-of-the-art, IEEE Transactions on Evolutionary Computation, 15 (2011), 4-31. doi: 10.1109/TEVC.2010.2059031.  Google Scholar [2] R. Gamperle, S. D. Muller and P. Koumoutsakos, A Parameter Study for Differential Evolution, in "Advances in intelligent systems, fuzzy systems, evolutionary computation" (eds. A. Grmela and N.E. Mastorakis), WSEAS Press, Interlaken, Switzerland, (2002), 293-298. Google Scholar [3] M. S. Giggs, H. R. Maier, G. C. Dandy and J. B. Nixon, Minimum number of generations required for convergence of genetic algorithms, in "Proceedings of 2006 IEEE Congress on Evolutionary Computation," Vancouver, BC, Canada, (2006), 2580-2587. Google Scholar [4] N. Hansen, The CMA evolution strategy: a comparing review , in "Towards a New Evolutionary Computation. Advances on Estimation of Distribution Algorithms"(eds. J.A. Lozano, P. Larranaga, I. Inza and E. Bengoetxea), Springer, (2006), 75-102. Google Scholar [5] A. R. Hedar and M. Fukushima, Minimizing multimodal functions by simplex coding genetic algorithm, Optimization Methods and Software, 18 (2003), 265-282.  Google Scholar [6] A. R. Hedar and M. Fukushima, Tabu search directed by direct search methods for nonlinear global optimization, European Journal of Operational Research, 170 (2006), 329-349. doi: 10.1016/j.ejor.2004.05.033.  Google Scholar [7] A. R. Hedar, B. T. Ong and M. Fukushima, Genetic algorithms with automatic accelerated termination, Technical report, Dept. of Applied Mathematics and Physics, Kyoto University, (2007). Google Scholar [8] B. J. Jain, H. Pohlheim and J. Wegener, On termination criteria of evolutionary algorithms, in "Proceedings of the Genetic and Evolutionary Computation Conference," Morgan Kaufmann Publishers, (2001), 768. Google Scholar [9] R. Joshi and A. C. Sanderson, Minimal representation multisensor fusion using differential evolution, IEEE Transactions on Systems, Man and Cybernetics (Part A), 29 (1999), 63-76. doi: 10.1109/3468.736361.  Google Scholar [10] C. T. Kelley, Detection and remediation of stagnation in the nelder-mead algorithm using a sufficient decrease condition, SIAM J. on Optimization, 10 (1999), 43-55. doi: 10.1137/S1052623497315203.  Google Scholar [11] N. M. Kwok, Q. P. Ha, D. K. Liu, G. Fang and K. C. Tan, Efficient particle swarm optimization: a termination condition based on the decision-making approach, in "Proceedings of the IEEE Congress on Evolutionary Computation," Singapore, (2007), 25-28. doi: 10.1109/CEC.2007.4424905.  Google Scholar [12] R. Mallipeddi, P. N. Suganthan, Q. K. Pan and M. F. Tasgetiren, Differential evolution algorithm with ensemble of parameters and mutation strategies, Applied Soft Computing, 11 (2011), 1679-1696. doi: 10.1016/j.asoc.2010.04.024.  Google Scholar [13] P. McMinn, Search-based software test data generation: A survey, Softw. Test. Verif. Reliab., 14 (2004), 105-156. doi: 10.1002/stvr.294.  Google Scholar [14] J. A. Nelder and R. Mead, A simplex method for function minimization, Computer Journal, 7 (1965), 308-313. Google Scholar [15] B. T. Ong and M. Fukushima, Genetic algorithm with automatic termination and search space rotation, Memetic Computing, 3 (2011), 111-127. doi: 10.1007/s12293-011-0057-8.  Google Scholar [16] M. O'Sullivan, S. Vssner and J. Wegener, Testing temporal correctness of real-time systems, in "EuroSTAR'98: Proceedings of the Sixth International Conference on Software Testing Analysis and Review," Munich, Germany, (1998). Google Scholar [17] K. V. Price, R. M. Storn and J. A. Lampinen, "Differential Evolution A Practical Approach to Global Optimization," Natural Computing Series, Springer-Verlag, Berlin, Germany, (2005). Google Scholar [18] A. K. Qin and P. N. Suganthan, Self-adaptive differential evolution algorithm for numerical optimization, in "The 2005 IEEE Congress on Evolutionary Computation," 2 (2005), 1785-1791. Google Scholar [19] R. Storn and K. Price, Differential evolution - a simple and efficient adaptive scheme for global optimization over continuous spaces, Technical Report TR-95-012, Online, (1995). Google Scholar [20] R. Storn and K. Price, Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces, J. of Global Optimization, 11 (1997), 341-359. doi: 10.1023/A:1008202821328.  Google Scholar [21] P. N. Suganthan, N. Hansen, J. J. Liang, K. Deb, Y. P. Chen, A. Auger and S. Tiwari, Problem definitions and evaluation criteria for the CEC -2005 special session on real-parameter optimization , Technical report, Singapore: Nanyang Technol. Univ., (2005). Google Scholar [22] J. Zhang, V. Avasarala, A. C. Sanderson and T. Mullen, Differential evolution for discrete optimization: An experimental study on combinatorial auction problems, in "Proceedings of the 10th IEEE Congress on Evolutionary Computation CEC 2008 (IEEE World Congress on Computational Intelligence)," (2008), 2794-2800. doi: 10.1109/CEC.2008.4631173.  Google Scholar
 [1] Viorel Barbu, Gabriela Marinoschi. An identification problem for a linear evolution equation in a banach space. Discrete & Continuous Dynamical Systems - S, 2020, 13 (5) : 1429-1440. doi: 10.3934/dcdss.2020081 [2] Ming Huang, Cong Cheng, Yang Li, Zun Quan Xia. The space decomposition method for the sum of nonlinear convex maximum eigenvalues and its applications. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1885-1905. doi: 10.3934/jimo.2019034 [3] Mahmoud M. El-Borai. On some fractional differential equations in the Hilbert space. Conference Publications, 2005, 2005 (Special) : 233-240. doi: 10.3934/proc.2005.2005.233 [4] Alexander S. Bratus, Vladimir P. Posvyanskii, Artem S. Novozhilov. A note on the replicator equation with explicit space and global regulation. Mathematical Biosciences & Engineering, 2011, 8 (3) : 659-676. doi: 10.3934/mbe.2011.8.659 [5] Alfredo Lorenzi, Ioan I. Vrabie. An identification problem for a linear evolution equation in a Banach space and applications. Discrete & Continuous Dynamical Systems - S, 2011, 4 (3) : 671-691. doi: 10.3934/dcdss.2011.4.671 [6] A. Damlamian, Nobuyuki Kenmochi. Evolution equations generated by subdifferentials in the dual space of $(H^1(\Omega))$. Discrete & Continuous Dynamical Systems, 1999, 5 (2) : 269-278. doi: 10.3934/dcds.1999.5.269 [7] Andrei Korobeinikov, Conor Dempsey. A continuous phenotype space model of RNA virus evolution within a host. Mathematical Biosciences & Engineering, 2014, 11 (4) : 919-927. doi: 10.3934/mbe.2014.11.919 [8] Matthew A. Fury. Regularization for ill-posed inhomogeneous evolution problems in a Hilbert space. Conference Publications, 2013, 2013 (special) : 259-272. doi: 10.3934/proc.2013.2013.259 [9] Tran Ngoc Thang, Nguyen Thi Bach Kim. Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1417-1433. doi: 10.3934/jimo.2016.12.1417 [10] Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069 [11] John R. Tucker. Attractors and kernels: Linking nonlinear PDE semigroups to harmonic analysis state-space decomposition. Conference Publications, 2001, 2001 (Special) : 366-370. doi: 10.3934/proc.2001.2001.366 [12] Vural Bayrak, Emil Novruzov, Ibrahim Ozkol. Local-in-space blow-up criteria for two-component nonlinear dispersive wave system. Discrete & Continuous Dynamical Systems, 2019, 39 (10) : 6023-6037. doi: 10.3934/dcds.2019263 [13] Baoquan Yuan, Xiao Li. Blow-up criteria of smooth solutions to the three-dimensional micropolar fluid equations in Besov space. Discrete & Continuous Dynamical Systems - S, 2016, 9 (6) : 2167-2179. doi: 10.3934/dcdss.2016090 [14] Jinbo Geng, Xiaochun Chen, Sadek Gala. On regularity criteria for the 3D magneto-micropolar fluid equations in the critical Morrey-Campanato space. Communications on Pure & Applied Analysis, 2011, 10 (2) : 583-592. doi: 10.3934/cpaa.2011.10.583 [15] Ö. Uğur, G. W. Weber. Optimization and dynamics of gene-environment networks with intervals. Journal of Industrial & Management Optimization, 2007, 3 (2) : 357-379. doi: 10.3934/jimo.2007.3.357 [16] Vianney Perchet, Marc Quincampoix. A differential game on Wasserstein space. Application to weak approachability with partial monitoring. Journal of Dynamics & Games, 2019, 6 (1) : 65-85. doi: 10.3934/jdg.2019005 [17] Giselle A. Monteiro, Milan Tvrdý. Generalized linear differential equations in a Banach space: Continuous dependence on a parameter. Discrete & Continuous Dynamical Systems, 2013, 33 (1) : 283-303. doi: 10.3934/dcds.2013.33.283 [18] Abbas Ja'afaru Badakaya, Aminu Sulaiman Halliru, Jamilu Adamu. Game value for a pursuit-evasion differential game problem in a Hilbert space. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021019 [19] Igor Kukavica. On Fourier parametrization of global attractors for equations in one space dimension. Discrete & Continuous Dynamical Systems, 2005, 13 (3) : 553-560. doi: 10.3934/dcds.2005.13.553 [20] Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems & Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048

Impact Factor:

## Metrics

• PDF downloads (45)
• HTML views (0)
• Cited by (1)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]