Global optimization with exploration/selection algorithms and simulated annealing. (English) Zbl 1012.60066

François, Olivier

Ann. Appl. Probab. 12, No. 1, 248-271 (2002).

Summary: This article studies a stochastic model of an evolutionary algorithm that evolves a “population” of potential solutions to a minimization problem. The minimization process is based on two operators. First, each solution is regarded as an individual that attempts a random search on a graph, involving a probabilistic operator called exploration. The second operator is called selection. This deterministic operator creates interaction between individuals. The convergence of the evolutionary process is described within the framework of simulated annealing. It can be quantified by means of two quantities called the critical height and the optimal convergence exponent, which both measure the difficulty of the algorithm to deal with the minimization problem. This work describes the critical height for large enough population sizes. Explicit bounds are given for the optimal convergence exponent, using a few geometric quantities. As an application, this work allows comparisons of the evolutionary strategy with independent parallel runs of the simulated annealing algorithm, and it helps deciding when one method should be preferred to the other.

MSC:

60J10	Markov chains (discrete-time Markov processes on discrete state spaces)
92D15	Problems related to evolution

Keywords:

evolutionary algorithms; generalized simulated annealing

References:

[1]	AARTS, E. H. L and KORST, J. H. M. (1988). Simulated Annealing and Boltzmann Machines. Wiley, New York. · Zbl 0674.90059
[2]	BÄCK, T. (1996). Evolutionary Algorithms in Theory and Practice. Oxford Univ. Press. · Zbl 0877.68060
[3]	CATONI, O. (1997). Simulated annealing algorithms and Markov chains with rare transitions. Lectures notes, Univ. Paris XI. · Zbl 0944.90053
[4]	CERF, R. (1994). Une théorie asymptotique des algorithmes génétiques. Ph.D. thesis, Montpellier II.
[5]	CERF, R. (1996a). The dynamics of mutation-selection algorithms with large population sizes. Ann. Inst. H. Poincaré Probab. Statist. 32 455-508. · Zbl 0861.60038
[6]	CERF, R. (1996b). A new genetic algorithm. Ann. Appl. Probab. 6 778-817. · Zbl 0860.60017 · doi:10.1214/aoap/1034968228
[7]	CHAKRABORTY, U. K., KALYANMOY, D. and CHAKRABORTY, M. (1996). Analysis of selection algorithms: a Markov chain approach. Evol. Comput. 4 133-167.
[8]	DAVIS, T. E. and PRINCIPE, J. C. (1991). A simulated annealing like convergence theory for the simple genetic algorithm. In Proceedings of the Fourth International Conference on Genetic Algorithms (R. K. Belew and L. B. Booker, eds.) 174-181. Morgan Kauffman, San Mateo, CA.
[9]	DAWSON, D. A. (1987). Stochastic models of parallel systems for global optimization. IMA Vol. Math. Appl. 9 25-44. · Zbl 0648.60104
[10]	DEL MORAL, P. and MICLO, L. (1999). On the convergence and the applications of the generalized simulated annealing. SIAM J. Control Optim. 37 1222-1250. · Zbl 0928.60046 · doi:10.1137/S0363012996313987
[11]	FOGEL, D. B. (1995). Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. IEEE Press, Piscataway, NJ.
[12]	FRANÇOIS, O. (1998). An evolutionary strategy for global minimization and its Markov chain analysis. IEEE Trans. Evolutionary Comput. 2 77-90.
[13]	FREIDLIN, M. I. and WENTZELL, A. D. (1984). Random Perturbations of Dynamical Systems. Springer, New York. · Zbl 0522.60055
[14]	GOLDBERG, D. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA. · Zbl 0721.68056
[15]	HAJEK, B. (1988). Cooling schedules for optimal annealing. Math. Oper. Res. 13 311-329. JSTOR: · Zbl 0652.65050 · doi:10.1287/moor.13.2.311
[16]	NIX, A. and VOSE, M. (1992). Modeling genetic algorithms with Markov chains. Ann. Math. Artificial Intelligence 5 79-88. · Zbl 1034.68534 · doi:10.1007/BF01530781
[17]	RABINOVITCH, Y. and WIGDERSON, A. (1999). Techniques for bounding the convergence rate of genetic algorithms. Random Structures Algorithms 14 111-137. · Zbl 0922.90115 · doi:10.1002/(SICI)1098-2418(199903)14:2<111::AID-RSA1>3.0.CO;2-6
[18]	RUDOLPH, G. (1994). Convergence analysis of canonical genetic algorithms. IEEE Trans. Neural Networks 5 96-101.
[19]	SUZUKI, J. (1993). A Markov chain analysis on a genetic algorithm. In Proceedings of the Fifth International Conference on Genetic Algorithms (S. Forrest, ed.) 146-153. Morgan Kauffman, San Mateo, CA.
[20]	TROUVÉ, A. (1995). Asymptotical behaviour of several interacting annealing processes. Probab. Theory Related Fields 102 123-143. · Zbl 0855.60029 · doi:10.1007/BF01295225
[21]	TROUVÉ, A. (1996). Cycle decomposition and simulated annealing. SIAM J. Control Optim. 34 966- 986. · Zbl 0852.60031 · doi:10.1137/S0363012993258586
[22]	WOLPERT, D. H. and MACREADY, W. G. (1997). No free lunch theorems for optimization. IEEE Trans. Evolutionary Comput. 1 67-82.