Finite Markov chain analysis of classical differential evolution algorithm. (English) Zbl 1293.65013
Summary: Theoretical analyses of algorithms are important to understand their search behaviors and develop more efficient algorithms. Compared with the plethora of works concerning the empirical study of the differential evolution (DE), little theoretical research has been done to investigate the convergence properties of DE so far. This paper focuses on theoretical researches on the convergence of DE and presents a convergent DE algorithm. First of all, it is proved that the classical DE cannot converge to the global optimal set with probability 1 by using the property that it cannot escape from a local optimal set. Inspired by the characteristics of the elitist genetic algorithm, this paper proposed a modified DE to overcome the disadvantage. The proposed algorithm employs two operators that assist it in escaping from a local optimal set and enhance the diversity of the population. And it is then verified that the proposed algorithm is capable of converging to global optima with probability 1. The theoretical research of this paper is undertaken in a finite discrete set, and the analysis tool used is the Markov chain. The numerical experiments are conducted on a deceptive function and a set of benchmark functions. The experimental results support the theoretical analyses on the convergence performances of the classical and modified DE algorithm.
MSC:
| 65C40 | Numerical analysis or methods applied to Markov chains |
| 60J22 | Computational methods in Markov chains |
Keywords:
convergence in probability; continuous optimization; differential evolution algorithm; Markov chainReferences:
| [1] | Storn, R.; Price, K. V., Differential Evolution: A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces. Technical Report (1995), International Computer Science Institute |
| [2] | Lampinen, Price, K. V., Differential Evolution: A Practical Approach to Global Optimization (2005), Springer press: Springer press Berlin · Zbl 1186.90004 |
| [3] | Das, S.; Suganthan, P. N., Differential evolution: a survey of the state-of- the-art, IEEE Trans. Evol. Comput., 1, 4-31 (2011) |
| [4] | Das, S.; Suganthan, P. N.; Coello Coello, C. A., Guest editorial: special issue on differential evolution, IEEE Trans. Evol. Comput., 1, 1-3 (2011) |
| [5] | Storn, R.; Price, K. V., Differential evolution: a simple and efficient heuristic for global optimization over continuous spaces, J. Global Optim., 4, 341-359 (1997) · Zbl 0888.90135 |
| [8] | Wang, X. S.; Hao, M. L.; Cheng, Y. H., On the use of differential evolution for forward kinematics of parallel manipulators, J. Appl. Math. Comput., 2, 760-769 (2008) · Zbl 1157.65392 |
| [9] | Falco, I. D.; Cioppa, A. D.; Maisto, D.; Tarantino, E., Differential evolution as a viable tool for satellite image registration, J. Appl. Soft Comput., 4, 1453-1462 (2008) |
| [10] | Cruz, I. L.L.; Van Willigenburg, L. G.; Van Straten, G.; Tarantino, E., Efficient differential evolution algorithms for multimodal optimal control problems, J. Appl. Soft Comput., 2, 97-122 (2003) |
| [11] | Neri, F.; Tirronen, V., Recent advances in differential evolution: a survey and experimental analysis, J. Artif. Intell. Rev., 33, 61-106 (2010) |
| [12] | Noman, N.; Iba, H., Accelerating differential evolution using an adaptive local search, IEEE Trans. Evol. Comput., 1, 107-125 (2008) |
| [13] | Das, S.; Abraham, A.; Chakraborty, U. K.; Konar, A., Differential evolution with a neighborhood-based mutation operator, IEEE Trans. Evol. Comput., 3, 526-553 (2009) |
| [14] | Michael, G. E.; Dimitris, K. T.; Nicos, G. P.; Vassilis, P. P.; Michael, N. V., Enhancing differential evolution utilizing proximity-based mutation operators, IEEE Trans. Evol. Comput., 1, 99-119 (2011) |
| [15] | Dorroonsoro, E.; Bouvry, P., Improving classical and decentralized differential evolution with new mutation operator and population topologies, IEEE Trans. Evol. Comput., 1, 67-98 (2011) |
| [16] | Wang, Y.; Cai, Z. X.; Zhang, Q. F., Differential evolution with composite trial vector generation strategies and control parameters, IEEE Trans. Evol. Comput., 15, 1, 55-66 (2011) |
| [17] | Fan, H. Y.; Lampinen, J., A trigonometric mutation operation to differential evolution, J. Global Optim., 1, 105-129 (2003) · Zbl 1142.90509 |
| [18] | Chiang, C. E.; Lee, W. P.; Heh, G. P., A 2-opt based differential evolution for global optimization, J. Appl. Soft Comput., 10, 1200-1207 (2010) |
| [19] | Mininno, E.; Neri, F.; Cupercesco, F., Compact differential evolution, IEEE Trans. Comput., 1, 32-54 (2011) |
| [20] | Brest, J.; Maučec, M. S., Population size reduction for the differential evolution algorithm, J. Appl. Intell., 3, 228-247 (2008) |
| [21] | Neri, F.; Tirronen, V., Scale factor local search in differential evolution, J. Memet. Comput. J., 2, 153-171 (2009) |
| [22] | Qin, A. K.; Huang, V. L.; Suganthan, P. N., Differential evolution algorithm with strategy adaptation for global numerical optimization, IEEE Trans. Evol. Comput., 2, 398-417 (2009) |
| [23] | Hu, Z. B.; Su, Q. H.; Xiong, S. W.; Hu, F. G., Self-adaptive hybrid differential evolution with simulated annealing algorithm for numerical optimization, (IEEE World Congress Computational Intelligence (2008), IEEE Press: IEEE Press Hongkong), 1189-1194 |
| [24] | Xue, F.; Sanderson, A. C.; Graves, R. J., Modeling and convergence analysis of a continuous multiobjective differential evolution algorithm, (IEEE Cong. Evol. Comput. (2005), IEEE Press: IEEE Press Edinburgh), 228-235 |
| [26] | ter Braak, C. J.F., A Markov chain Monte Carlo version of the genetic algorithm differential evolution: easy Bayesian computing for real parameter spaces, Statist. Comput., 16, 239-249 (2006) |
| [27] | Robert, M. B., Pointwise properties of convergence in probability, Statist. Probab. Lett., 6, 315-316 (1985) · Zbl 0571.60040 |
| [28] | Xu, Z. B., Computational Intelligence: Simulating Evolution Computation (2004), Higher Education Press: Higher Education Press Beijing, (in Chinese) |
| [30] | Suzuki, J., A Markov chain analysis on simple genetic algorithms, IEEE Trans. Syst. Man Cybern., 4, 655-659 (1995) |
| [32] | Weber, M.; Neri, F.; Tirronen, V., A study on scale factor in distributed differential evolution, J. Inf. Sci., 2488-2511 (2011) |
| [33] | Rudolph, G., Convergence analysis of canonical genetic algorithms, IEEE Trans. Neural Netw., 1, 96-101 (1994) |
| [34] | Xu, Z. B.; Nie, Z. K.; Zhang, W. C., Almost sure convergence of genetic algorithms: a martingale approach, J. Comput., 8, 785-794 (2002), (in Chinese) |
| [35] | Sheldon, M. R., Stochastic Processes (1996), Wiley: Wiley New York · Zbl 0888.60002 |
| [37] | Goudos, S. K., A comparative study of common and self-adaptive differential evolution strategies on numerical benchmark problems, Procedia Comput. Sci., 3, 83-88 (2011) |
| [38] | Suganthan, P. N., Problem Definition and Evaluation Criteria for the CEC2005 Special Session on Real-Parameter Optimization. Technical Report (2005), Institute of Electrical and Electronics Engineers |
| [39] | Brest, J.; GrFESer, S.; Boskovic, B.; Mernik, M.; Zumer, V., Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems, IEEE Trans. Evol. Comput., 6, 646-657 (2006) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
