Hostname: page-component-7b7567c8c-kwt9d Total loading time: 0 Render date: 2026-11-14T12:03:58.348Z Has data issue: false hasContentIssue false
  • English
  • Français

The quasispecies regime for the simple genetic algorithm with roulette wheel selection

Part of:Markov processes

Published online by Cambridge University Press:  08 September 2017

Raphaël Cerf
Raphaël Cerf*
Affiliation:
École Normale Supérieure
*
* Postal address: Département de Mathématiques et Applications, École Normale Supérieure, 45 rue d'Ulm, 75005 Paris, France. Email address: raphael.cerf@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We introduce a new parameter to discuss the behavior of a genetic algorithm. This parameter is the mean number of exact copies of the best-fit chromosomes from one generation to the next. We believe that the genetic algorithm operates best when this parameter is slightly larger than 1 and we prove two results supporting this belief. We consider the case of the simple genetic algorithm with the roulette wheel selection mechanism. We denote by ℓ the length of the chromosomes, m the population size, p C the crossover probability, and p M the mutation probability. Our results suggest that the mutation and crossover probabilities should be tuned so that, at each generation, the maximal fitness multiplied by (1 - p C)(1 - p M)ℓ is greater than the mean fitness.

Keywords

Genetic algorithmquasispeciesstochastic optimization

MSC classification

Primary:60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
Secondary:92D15: Problems related to evolution

Information

Type
Research Article
Information
Advances in Applied Probability , Volume 49 , Issue 3 , September 2017, pp. 903 - 926
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Athreya, K. B. and Ney, P. E. (2004). Branching Processes. Dover, Mineola, NY. Google Scholar
[2] Cerf, R. (2014). The quasispecies regime for the simple genetic algorithm with ranking selection. Preprint. Available at https://arxiv.org/abs/1403.5427. Google Scholar
[3] Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications, 2nd edn. Springer, New York. Google Scholar
[4] Eigen, M., McCaskill, J. and Schuster, P. (1989). The molecular quasi-species. In Advances in Chemical Physics, Vol. 75. John Wiley, Hoboken, NJ, pp. 149–263. Google Scholar
[5] Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA. Google Scholar
[6] Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58, 13–30. Google Scholar
[7] Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor. Google Scholar
[8] Liggett, T. M. (2005). Interacting Particle Systems. Springer, Berlin. CrossRefGoogle Scholar
[9] Mills, K. L., Filliben, J. J. and Haines, A. L. (2015). Determining relative importance and effective settings for genetic algorithm control parameters. Evolutionary Comput. 23, 309–342. Google Scholar