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

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

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

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

[5]

A. R. Hedar and M. Fukushima, Minimizing multimodal functions by simplex coding genetic algorithm, Optimization Methods and Software, 18 (2003), 265-282.

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

[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).

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

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

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

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

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

[13]

P. McMinn, Search-based software test data generation: A survey, Softw. Test. Verif. Reliab., 14 (2004), 105-156. doi: 10.1002/stvr.294.

[14]

J. A. Nelder and R. Mead, A simplex method for function minimization, Computer Journal, 7 (1965), 308-313.

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

[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).

[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).

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

[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).

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

[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).

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

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.

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

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

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

[5]

A. R. Hedar and M. Fukushima, Minimizing multimodal functions by simplex coding genetic algorithm, Optimization Methods and Software, 18 (2003), 265-282.

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

[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).

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

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

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

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

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

[13]

P. McMinn, Search-based software test data generation: A survey, Softw. Test. Verif. Reliab., 14 (2004), 105-156. doi: 10.1002/stvr.294.

[14]

J. A. Nelder and R. Mead, A simplex method for function minimization, Computer Journal, 7 (1965), 308-313.

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

[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).

[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).

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

[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).

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

[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).

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

[1]

Qianqian Xia. On embedding of subcartesian differential space and application. Journal of Geometric Mechanics, 2022  doi: 10.3934/jgm.2022007

[2]

Viorel Barbu, Gabriela Marinoschi. An identification problem for a linear evolution equation in a banach space. Discrete and Continuous Dynamical Systems - S, 2020, 13 (5) : 1429-1440. doi: 10.3934/dcdss.2020081

[3]

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 and Management Optimization, 2020, 16 (4) : 1885-1905. doi: 10.3934/jimo.2019034

[4]

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

[5]

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

[6]

Alfredo Lorenzi, Ioan I. Vrabie. An identification problem for a linear evolution equation in a Banach space and applications. Discrete and Continuous Dynamical Systems - S, 2011, 4 (3) : 671-691. doi: 10.3934/dcdss.2011.4.671

[7]

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

[8]

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

[9]

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

[10]

Tran Ngoc Thang, Nguyen Thi Bach Kim. Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1417-1433. doi: 10.3934/jimo.2016.12.1417

[11]

Xiaoqing Ou, Suliman Al-Homidan, Qamrul Hasan Ansari, Jiawei Chen. Image space analysis for uncertain multiobjective optimization problems: Robust optimality conditions. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021199

[12]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems and Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[13]

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

[14]

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

[15]

Baoquan Yuan, Xiao Li. Blow-up criteria of smooth solutions to the three-dimensional micropolar fluid equations in Besov space. Discrete and Continuous Dynamical Systems - S, 2016, 9 (6) : 2167-2179. doi: 10.3934/dcdss.2016090

[16]

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 and Applied Analysis, 2011, 10 (2) : 583-592. doi: 10.3934/cpaa.2011.10.583

[17]

Ö. Uğur, G. W. Weber. Optimization and dynamics of gene-environment networks with intervals. Journal of Industrial and Management Optimization, 2007, 3 (2) : 357-379. doi: 10.3934/jimo.2007.3.357

[18]

Vianney Perchet, Marc Quincampoix. A differential game on Wasserstein space. Application to weak approachability with partial monitoring. Journal of Dynamics and Games, 2019, 6 (1) : 65-85. doi: 10.3934/jdg.2019005

[19]

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

[20]

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 and Games, 2022, 9 (1) : 1-12. doi: 10.3934/jdg.2021019

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]