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?)


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