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.  doi: 10.1109/TEVC.2010.2059031.  Google Scholar

[2]

R. Gamperle, S. D. Muller and P. Koumoutsakos, A Parameter Study for Differential Evolution,, in, (2002), 293.   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, (2006), 2580.   Google Scholar

[4]

N. Hansen, The CMA evolution strategy: a comparing review ,, in, (2006), 75.   Google Scholar

[5]

A. R. Hedar and M. Fukushima, Minimizing multimodal functions by simplex coding genetic algorithm,, Optimization Methods and Software, 18 (2003), 265.   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.  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, (2007).   Google Scholar

[8]

B. J. Jain, H. Pohlheim and J. Wegener, On termination criteria of evolutionary algorithms,, in, (2001).   Google Scholar

[9]

R. Joshi and A. C. Sanderson, Minimal representation multisensor fusion using differential evolution,, IEEE Transactions on Systems, 29 (1999), 63.  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.  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, (2007), 25.  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.  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.  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.   Google Scholar

[15]

B. T. Ong and M. Fukushima, Genetic algorithm with automatic termination and search space rotation,, Memetic Computing, 3 (2011), 111.  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, (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, (2005).   Google Scholar

[18]

A. K. Qin and P. N. Suganthan, Self-adaptive differential evolution algorithm for numerical optimization,, in, 2 (2005), 1785.   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, (1995), 95.   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.  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, (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, (2008), 2794.  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.  doi: 10.1109/TEVC.2010.2059031.  Google Scholar

[2]

R. Gamperle, S. D. Muller and P. Koumoutsakos, A Parameter Study for Differential Evolution,, in, (2002), 293.   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, (2006), 2580.   Google Scholar

[4]

N. Hansen, The CMA evolution strategy: a comparing review ,, in, (2006), 75.   Google Scholar

[5]

A. R. Hedar and M. Fukushima, Minimizing multimodal functions by simplex coding genetic algorithm,, Optimization Methods and Software, 18 (2003), 265.   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.  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, (2007).   Google Scholar

[8]

B. J. Jain, H. Pohlheim and J. Wegener, On termination criteria of evolutionary algorithms,, in, (2001).   Google Scholar

[9]

R. Joshi and A. C. Sanderson, Minimal representation multisensor fusion using differential evolution,, IEEE Transactions on Systems, 29 (1999), 63.  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.  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, (2007), 25.  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.  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.  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.   Google Scholar

[15]

B. T. Ong and M. Fukushima, Genetic algorithm with automatic termination and search space rotation,, Memetic Computing, 3 (2011), 111.  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, (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, (2005).   Google Scholar

[18]

A. K. Qin and P. N. Suganthan, Self-adaptive differential evolution algorithm for numerical optimization,, in, 2 (2005), 1785.   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, (1995), 95.   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.  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, (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, (2008), 2794.  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, 2018, 0 (0) : 1-12. 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, 2017, 13 (5) : 1-21. 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]

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

[5]

A. Damlamian, Nobuyuki Kenmochi. Evolution equations generated by subdifferentials in the dual space of $(H^1(\Omega))$. Discrete & Continuous Dynamical Systems - A, 1999, 5 (2) : 269-278. doi: 10.3934/dcds.1999.5.269

[6]

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

[7]

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

[8]

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

[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]

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

[13]

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

[14]

Vural Bayrak, Emil Novruzov, Ibrahim Ozkol. Local-in-space blow-up criteria for two-component nonlinear dispersive wave system. Discrete & Continuous Dynamical Systems - A, 2019, 39 (10) : 6023-6037. doi: 10.3934/dcds.2019263

[15]

Giselle A. Monteiro, Milan Tvrdý. Generalized linear differential equations in a Banach space: Continuous dependence on a parameter. Discrete & Continuous Dynamical Systems - A, 2013, 33 (1) : 283-303. doi: 10.3934/dcds.2013.33.283

[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]

Igor Kukavica. On Fourier parametrization of global attractors for equations in one space dimension. Discrete & Continuous Dynamical Systems - A, 2005, 13 (3) : 553-560. doi: 10.3934/dcds.2005.13.553

[18]

Ö. 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

[19]

Zhen Lei. Rotation-strain decomposition for the incompressible viscoelasticity in two dimensions. Discrete & Continuous Dynamical Systems - A, 2014, 34 (7) : 2861-2871. doi: 10.3934/dcds.2014.34.2861

[20]

Yong Xia, Ruey-Lin Sheu, Shu-Cherng Fang, Wenxun Xing. Double well potential function and its optimization in the $N$ -dimensional real space-part Ⅱ. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1307-1328. doi: 10.3934/jimo.2016074

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]