Global optimization via differential evolution with automatic termination

Bun Theang Ong; Masao Fukushima

doi:10.3934/naco.2012.2.57

Article Contents

2012, Volume 2, Issue 1: 57-67. Doi: 10.3934/naco.2012.2.57

This issue Previous Article An AIS-based optimal control framework for longevity and task achievement of multi-robot systems Next Article Univariate geometric Lipschitz global optimization algorithms

Global optimization via differential evolution with automatic termination

Bun Theang Ong^1, and
Masao Fukushima^2,

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

Received: March 31, 2011

Revised: June 30, 2011

Published: February 2012

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C26, 90C59.

Citation:

Related Papers

Cited by

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.