Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-25T07:34:16.690Z 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: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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, pC the crossover probability, and pM 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 - pC)(1 - pM)ℓ 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
Type
Research Article
Information
Advances in Applied Probability , Volume 49 , Issue 3 , September 2017 , pp. 903 - 926
Copyright
Copyright © Applied Probability Trust 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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