홈 › Papers

The quasispecies regime for the simple genetic algorithm with ranking selection

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 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 $$\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: $\pi=\sigma(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\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.

Code (0)

등록된 구현이 없습니다.

Similar Papers 제목 키워드 기반