Raphaël Cerf

Raphaël Cerf

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 argue that the genetic algorithm should operate efficiently when this parameter is slightly larger than $1$. We consider the case of the simple genetic algorithm with the roulette--wheel selection mechanism. 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 start the genetic algorithm with an initial population whose maximal fitness is equal to $f_0^*$ and whose mean fitness is equal to ${\overline{f_0}}$. We show that, in the limit of large populations, the dynamics of the genetic algorithm depends in a critical way on the parameter $π\,=\,\big({f_0^*}/{\overline{f_0}}\big) (1-p_C)(1-p_M)^\ell\,.$ Our results suggest that the mutation and crossover probabilities should be tuned so that, at each generation, $\text{maximal fitness} \times (1-p_C) (1-p_M)^\ell > \text{mean fitness}$.

Raphaël Cerf

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 $σ$, called the selection drift, which measures the selection intensity of the fittest chromosome. We show that the dynamics of the genetic algorithm depend in a critical way on the parameter $$π\,=\,σ(1-p_C)(1-p_M)^\ell\,.$$ If $π<1$, then the genetic algorithm operates in a disordered regime: an advantageous mutant disappears with probability larger than $1-1/m^β$, where $β$ is a positive exponent. If $π>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: $π=σ(1-p_C)(1-p_M)^\ell$ should be slightly larger than $1$; $p_M$ should be of order $1/\ell$; $m$ should be larger than $\ell\ln\ell$; the running time should be of exponential order in $m$. The first condition requires that $ \ell p_M +p_C< \lnσ$. 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.