Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

The quasispecies regime for the simple genetic algorithm with ranking selection


Author: Raphaël Cerf
Journal: Trans. Amer. Math. Soc. 369 (2017), 6017-6071
MSC (2010): Primary 60J20; Secondary 92D15
DOI: https://doi.org/10.1090/tran/7170
Published electronically: May 1, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the simple genetic algorithm with a ranking selection mechanism (linear ranking or tournament). We denote by $ \ell $ the length of the chromosomes, by $ m$ the population size, by $ p_C$ the crossover probability and by $ p_M$ the mutation probability. We introduce a parameter $ \sigma $, called the strength of the ranking selection, which measures the selection intensity of the fittest chromosome. We show that the dynamics of the genetic algorithm depends in a critical way on the parameter

$\displaystyle \pi \,=\,\sigma (1-p_C)(1-p_M)^\ell \,.$

If $ \pi <1$, then the genetic algorithm operates in a disordered regime: an advantageous mutant disappears with probability larger than $ 1-1/m^\beta $, where $ \beta $ is a positive exponent. If $ \pi >1$, then the genetic algorithm operates in a quasispecies regime: an advantageous mutant invades a positive fraction of the population with probability larger than a constant $ p^*$ (which does not depend on $ m$). We estimate next the probability of the occurrence of a catastrophe (the whole population falls below a fitness level which was previously reached by a positive fraction of the population). The asymptotic results suggest the following rules:

$ \bullet $ $ \pi =\sigma (1-p_C)(1-p_M)^\ell $ should be slightly larger than $ 1$;

$ \bullet $ $ p_M$ should be of order $ 1/\ell $;

$ \bullet $ $ m$ should be larger than $ \ell \ln \ell $;

$ \bullet $ the running time should be at most of exponential order in $ m$.

The first condition requires that $ \ell p_M +p_C< \ln \sigma $. These conclusions must be taken with great care: they come from an asymptotic regime, and it is a formidable task to understand the relevance of this regime for a real-world problem. At least, we hope that these conclusions provide interesting guidelines for the practical implementation of the simple genetic algorithm.


References [Enhancements On Off] (What's this?)

  • [1] K. B. Athreya and P. E. Ney, Branching processes, Dover Publications, Inc., Mineola, NY, 2004. Reprint of the 1972 original [Springer, New York; MR0373040]. MR 2047480
  • [2] Thomas Bäck, Jeannette M. de Graaf, Joost N. Kok, and Walter A. Kosters, Theory of genetic algorithms, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS (1997), no. 63, 161-192. MR 1621601 (99g:68166)
  • [3] J. Bérard and A. Bienvenüe, Sharp asymptotic results for simplified mutation-selection algorithms, Ann. Appl. Probab. 13 (2003), no. 4, 1534-1568. MR 2023888, https://doi.org/10.1214/aoap/1069786510
  • [4] Jean Bérard, Genetic algorithms in random environments: two examples, Probab. Theory Related Fields 133 (2005), no. 1, 123-140. MR 2197140, https://doi.org/10.1007/s00440-004-0419-y
  • [5] Alain Cercueil and Olivier François, Sharp asymptotics for fixation times in stochastic population genetics models at low mutation probabilities, J. Statist. Phys. 110 (2003), no. 1-2, 311-332. MR 1966331, https://doi.org/10.1023/A:1021078914200
  • [6] Raphaël Cerf, Critical control of a genetic algorithm, ArXiv e-prints (2010).
  • [7] Raphaël Cerf, Critical population and error threshold on the sharp peak landscape for the Wright-Fisher model, Ann. Appl. Probab. 25 (2015), no. 4, 1936-1992. MR 3348998, https://doi.org/10.1214/14-AAP1039
  • [8] Raphaël Cerf, Une théorie asymptotique des algorithmes génétiques, Ph.D. thesis, Université Montpellier II, March 1994.
  • [9] Joseba Dalmau, The distribution of the quasispecies for the Wright-Fisher model on the sharp peak landscape, Stochastic Process. Appl. 125 (2015), no. 1, 272-293. MR 3274700, https://doi.org/10.1016/j.spa.2014.08.008
  • [10] P. Del Moral and L. Miclo, On the convergence and applications of generalized simulated annealing, SIAM J. Control Optim. 37 (1999), no. 4, 1222-1250. MR 1691939, https://doi.org/10.1137/S0363012996313987
  • [11] P. Del Moral and L. Miclo, Asymptotic results for genetic algorithms with applications to nonlinear estimation, Theoretical aspects of evolutionary computing (Antwerp, 1999), Nat. Comput. Ser., Springer, Berlin, 2001, pp. 439-493. MR 1937520 (2003h:90119)
  • [12] P. Del Moral and L. Miclo, Genealogies and increasing propagation of chaos for Feynman-Kac and genetic models, Ann. Appl. Probab. 11 (2001), no. 4, 1166-1198. MR 1878294
  • [13] Pierre Del Moral and Laurent Miclo, Dynamiques recuites de type Feynman-Kac: résultats précis et conjectures, ESAIM Probab. Stat. 10 (2006), 76-140 (French, with English and French summaries). MR 2218405, https://doi.org/10.1051/ps:2006003
  • [14] C. Dombry, A weighted random walk model, with application to a genetic algorithm, Adv. in Appl. Probab. 39 (2007), no. 2, 550-568. MR 2343677, https://doi.org/10.1239/aap/1183667623
  • [15] Á. E. Eiben, E. H. L. Aarts, and K. M. van Hee, Global convergence of genetic algorithms: a Markov chain analysis, Parallel problem solving from nature (Dortmund, 1990) Lecture Notes in Comput. Sci., vol. 496, Springer, Berlin, 1991, pp. 4-12. MR 1122625
  • [16] Manfred Eigen, Self-organization of matter and the evolution of biological macromolecules, Naturwissenschaften 58 (1971), no. 10, 465-523.
  • [17] Manfred Eigen, John McCaskill, and Peter Schuster, The molecular quasi-species., Advances in Chemical Physics 75 (1989), 149-263.
  • [18] Richard S. Ellis, Entropy, large deviations, and statistical mechanics, Classics in Mathematics, Springer-Verlag, Berlin, 2006. Reprint of the 1985 original. MR 2189669
  • [19] Olivier Francois, An evolutionary strategy for global minimization and its markov chain analysis, Trans. Evol. Comp 2 (1998), no. 3, 77-90.
  • [20] Olivier François, Global optimization with exploration/selection algorithms and simulated annealing, Ann. Appl. Probab. 12 (2002), no. 1, 248-271. MR 1890064, https://doi.org/10.1214/aoap/1015961163
  • [21] M. I. Freidlin, A. D. Wentzell, and Random perturbations of dynamical systems, 2nd ed., Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 260, Springer-Verlag, New York, 1998. Translated from the 1979 Russian original by Joseph Szücs. MR 1652127
  • [22] David Goldberg, Genetic algorithms in search, optimization and machine learning, Addison-Wesley, 1989.
  • [23] David Greenhalgh and Stephen Marshall, Convergence criteria for genetic algorithms, SIAM J. Comput. 30 (2000), no. 1, 269-282. MR 1762714, https://doi.org/10.1137/S009753979732565X
  • [24] Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13-30. MR 0144363
  • [25] John H. Holland, Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence, University of Michigan Press, Ann Arbor, Mich., 1975. MR 0441393
  • [26] Martin Nilsson Jacobi and Mats Nordahl, Quasispecies and recombination, Theoretical Population Biology 70 (2006), no. 4, 479-485.
  • [27] Yuri Kifer, Random perturbations of dynamical systems, Progress in Probability and Statistics, vol. 16, Birkhäuser Boston, Inc., Boston, MA, 1988. MR 1015933
  • [28] Yuri Kifer, A discrete-time version of the Wentzell-Freidlin theory, Ann. Probab. 18 (1990), no. 4, 1676-1692. MR 1071818
  • [29] Thomas M. Liggett, Interacting particle systems, Classics in Mathematics, Springer-Verlag, Berlin, 2005. Reprint of the 1985 original. MR 2108619
  • [30] Matthias Löwe, On the convergence of genetic algorithms, Exposition. Math. 14 (1996), no. 4, 289-312. MR 1418026
  • [31] J. A. Lozano, P. Larrañaga, M. Graña, and F. X. Albizuri, Genetic algorithms: bridging the convergence gap, Theoret. Comput. Sci. 229 (1999), no. 1-2, 11-22. MR 1719177, https://doi.org/10.1016/S0304-3975(99)00090-0
  • [32] K. L. Mak, J. S. K. Lau, and C. Wei, A Markov chain analysis of genetic algorithms with individuals having different birth and survival rates, Eng. Optim. 37 (2005), no. 6, 571-589. MR 2164917, https://doi.org/10.1080/03052150500114263
  • [33] Christian Mazza and Didier Piau, On the effect of selection in genetic algorithms, Random Structures Algorithms 18 (2001), no. 2, 185-200. MR 1809722, https://doi.org/10.1002/1098-2418(200103)18:2$ \langle $185::AID-RSA1005$ \rangle $3.0.CO;2-7
  • [34] Liang Ming and Yu Ping Wang, Convergence rate of a class of genetic algorithms, Math. Numer. Sin. 29 (2007), no. 1, 15-26 (Chinese, with English and Chinese summaries). MR 2325674
  • [35] Takehiko Nakama, Markov chain analysis of genetic algorithms applied to fitness functions perturbed concurrently by additive and multiplicative noise, Comput. Optim. Appl. 51 (2012), no. 2, 601-622. MR 2891909, https://doi.org/10.1007/s10589-010-9371-1
  • [36] Allen E. Nix and Michael D. Vose, Modeling genetic algorithms with Markov chains, Ann. Math. Artificial Intelligence 5 (1992), no. 1, 79-88. MR 1279417, https://doi.org/10.1007/BF01530781
  • [37] Gabriela Ochoa, Consensus sequence plots and error thresholds: Tools for visualising the structure of fitness landscape, Parallel Problem Solving from Nature - PPSN VI (Berlin), Springer, 2000, pp. 129-138.
  • [38] Gabriela Ochoa, Error thresholds and optimal mutation rates in genetic algorithms, Ph.D. thesis, The University of Sussex, Brighton, 2001.
  • [39] Gabriela Ochoa, Setting the mutation rate: Scope and limitations of the $ 1/{L}$ heuristic, GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference (New York), 9-13 July 2002, pp. 495-502.
  • [40] Gabriela Ochoa, Error thresholds in genetic algorithms, Evol. Comput. 14 (2006), no. 2, 157-182.
  • [41] Gabriela Ochoa, Inman Harey, and Hilary Buxton, Optimal mutation rates and selection pressure in genetic algorithms, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000) (Las Vegas, Nevada, USA), 10-12 July 2000, pp. 315-322.
  • [42] Gabriela Ochoa and Inman Harvey, Recombination and error thresholds in finite populations, Foundations of Genetic Algorithms (FOGA-5). Preliminary Version of the Proceedings, Leiden, 1998, pp. 129-148.
  • [43] Gabriela Ochoa, Inman Harvey, and Hilary Buxton, Error thresholds and their relation to optimal mutation rates, Advances in Artificial Life, 5th European Conference, ECAL'99, Lausanne, Switzerland, September 13-17, 1999, Proceedings, Lecture Notes in Computer Science, vol. 1674, Springer, 1999, pp. 54-63.
  • [44] Gabriela Ochoa, Inman Harvey, and Hilary Buxton, On recombination and optimal mutation rates, Proceedings of the Genetic and Evolutionary Computation Conference (Orlando, Florida, USA), vol. 1, 13-17 July 1999, pp. 488-495.
  • [45] L. Rigal and L. Truffet, A new genetic algorithm specifically based on mutation and selection, Adv. in Appl. Probab. 39 (2007), no. 1, 141-161. MR 2307875, https://doi.org/10.1239/aap/1175266473
  • [46] Miguel Rocha and José Neves, Preventing premature convergence to local optima in genetic algorithms via random offspring generation, Multiple Approaches to Intelligent Systems (Ibrahim Imam, Yves Kodratoff, Ayman El-Dessouki, and Moonis Ali, eds.), Lecture Notes in Computer Science, vol. 1611, Springer Berlin Heidelberg, 1999, pp. 127-136.
  • [47] Alex Rogers, Adam Prügel-Bennett, and Nicholas R. Jennings, Phase transitions and symmetry breaking in genetic algorithms with crossover, Theoret. Comput. Sci. 358 (2006), no. 1, 121-141. MR 2248783, https://doi.org/10.1016/j.tcs.2006.04.010
  • [48] Lothar M. Schmitt, Theory of genetic algorithms, Theoret. Comput. Sci. 259 (2001), no. 1-2, 1-61. MR 1832784, https://doi.org/10.1016/S0304-3975(00)00406-0
  • [49] Lothar M. Schmitt, Theory of genetic algorithms. II. Models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling, Theoret. Comput. Sci. 310 (2004), no. 1-3, 181-231. MR 2020342, https://doi.org/10.1016/S0304-3975(03)00393-1
  • [50] Joe Suzuki, A Markov chain analysis of genetic algorithms: large deviation principle approach, J. Appl. Probab. 47 (2010), no. 4, 967-975. MR 2752897
  • [51] Erik van Nimwegen and James P. Crutchfield, Metastable evolutionary dynamics: Crossing fitness barriers or escaping via neutral paths?, Bulletin of Mathematical Biology 62 (2000), no. 5, 799-848.
  • [52] Erik van Nimwegen and James P. Crutchfield, Optimizing epochal evolutionary search: Population-size independent theory, Computer Methods in Applied Mechanics and Engineering 186 (2000), no. 2-4, 799-848.
  • [53] Erik van Nimwegen and James P. Crutchfield, Optimizing epochal evolutionary search: Population-size dependent theory, Machine Learning Journal 45 (2001), 77-114.
  • [54] Erik van Nimwegen, James P. Crutchfield, and Melanie Mitchell, Finite populations induce metastability in evolutionary search, Phys. Lett. A 229 (1997), no. 3, 144-150. MR 1445497, https://doi.org/10.1016/S0375-9601(97)00192-8
  • [55] Erik van Nimwegen, James P. Crutchfield, and Melanie Mitchell, Statistical dynamics of the royal road genetic algorithm, Theoret. Comput. Sci. 229 (1999), no. 1-2, 41-102. MR 1719169, https://doi.org/10.1016/S0304-3975(99)00119-X
  • [56] Zong Ben Xu, Zan Kan Nie, and Wen Xiu Zhang, Almost sure convergence of genetic algorithms: a martingale approach, Chinese J. Comput. 25 (2002), no. 8, 785-793 (Chinese, with English and Chinese summaries). MR 1945780
  • [57] Zongben Xu and Yong Gao, Characteristic analysis and prevention on premature convergence in genetic algorithms, Sci. China Ser. E 40 (1997), no. 2, 113-125. MR 1449818, https://doi.org/10.1007/BF02916943
  • [58] Xiao-yan Zhao and Zan-kan Nie, The Markov chain analysis of premature convergence of genetic algorithms, Chinese Quart. J. Math. 18 (2003), no. 4, 364-368. MR 2039188

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 60J20, 92D15

Retrieve articles in all journals with MSC (2010): 60J20, 92D15


Additional Information

Raphaël Cerf
Affiliation: Département de Mathématiques et Applications, École Normale Supérieure, 45 rue d’Ulm, F-75230 Paris Cedex 05, France

DOI: https://doi.org/10.1090/tran/7170
Keywords: Genetic algorithms, quasispecies, stochastic optimization
Received by editor(s): April 8, 2015
Published electronically: May 1, 2017
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society