Sharp asymptotic results for simplified mutation-selection algorithms. (English) Zbl 1036.60026

The authors study the asymptotic behaviour of a mutation-selection genetic algorithm on the integers with finite population of size \(p\). The mutation is defined by the steps of a simple random walk and the fitness function is linear. The authors prove that the normalized population satisfies an invariance principle, that a large deviations principle holds and that the relative positions converge in law as well as that after \(n\) steps, the population is asymptotically around \(\sqrt{n}\) times the position at time 1 of a Bessel process of dimension \(2p-1\).


60F17 Functional limit theorems; invariance principles
60F10 Large deviations
92D15 Problems related to evolution
60F05 Central limit and other weak theorems


Full Text: DOI


[1] Bérard, J. and Bienvenüe, A. (2000). Convergence of a genetic algorithm with finite population. In Mathematics and Computer Science : Algorithms , Trees , Combinatorics and Probabilities 155–163. Birkhäuser, Basel. · Zbl 0965.68077
[2] Bérard, J. and Bienvenüe, A. (2000). Un principe d’invariance pour un algorithme génétique en population finie. C. R. Acad. Sci. Paris Sér. I Math. 331 469–474. · Zbl 0961.92022
[3] Billingsley, P. (1968). Convergence of Probability Measures . Wiley, New York. · Zbl 0172.21201
[4] Bonnaz, D. (1998). Modèles stochastiques de dynamique des populations. Ph.D. dissertation, Univ. Lausanne. · Zbl 0944.92029
[5] Cerf, R. (1998). Asymptotic convergence of genetic algorithms. Adv. in Appl. Probab. 30 521–550. · Zbl 0911.60018
[6] Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications , 2nd ed. Springer, New York. · Zbl 0896.60013
[7] Durrett, R. (1996). Probability : Theory and Examples , 2nd ed. Duxbury, Belmont, CA. · Zbl 1202.60001
[8] Gradshteyn, I. S. and Ryzhik, I. M. (1996). Table of Integrals , Series , and Products , 5th ed. Academic, San Diego. · Zbl 0918.65001
[9] Holland, J. H. (1975). Adaptation in Natural and Artificial Systems . Univ. Michigan Press, Ann Arbor. · Zbl 0317.68006
[10] Kessler, D., Levine, H., Ridgway, D. and Tsimring, L. (1997). Evolution on a smooth landscape. J. Statist. Phys. 87 519–544. · Zbl 0920.92018
[11] Matsumoto, M. and Nishimura, T. (1998). Mersenne twister a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Modeling Comput. Simulation 8 3–30. · Zbl 0917.65005
[12] Mazza, C. and Piau, D. (2001). On the effect of selection in genetic algorithms. Random Structures Algorithms 18 185–200. · Zbl 0971.68209
[13] Rabinovich, Y. and Wigderson, A. (1999). Techniques for bounding the convergence rate of genetic algorithms. Random Structures Algorithms 14 111–138. · Zbl 0922.90115
[14] Revuz, D. and Yor, M. (1991). Continuous Martingales and Brownian Motion . Springer, Berlin. · Zbl 0731.60002
[15] Tsimring, L. S., Levine, H. and Kessler, D. A. (1996). RNA virus evolution via a fitness-space model. Phys. Rev. Lett. 76 4440.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.