The dynamics of mutation-selection algorithms with large population sizes. (English) Zbl 0861.60038

Cerf, Raphaël

Ann. Inst. Henri Poincaré, Probab. Stat. 32, No. 4, 455-508 (1996).

Summary: We build the mutation-selection algorithm by randomly perturbing a very simple selection scheme. Our process belongs to the class of the generalized simulated annealing algorithms studied by Trouvé. When the population size \(m\) is large, the various quantities associated with the algorithm are affine functions of \(m\) and the hierarchy of cycles on the set of uniform populations stabilizes. If the mutation kernel is symmetric, the limiting distribution is the uniform distribution over the set of the global maxima of the fitness function. The optimal convergence exponent defined by Azencott, Catoni and Trouvé is an affine strictly increasing function of \(m\).

MSC:

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

Keywords:

Freidlin-Wentzell theory; evolutionary algorithms; stochastic optimization