The quasispecies regime for the simple genetic algorithm with ranking selection

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

Abstract: We study the simple genetic algorithm with a ranking selection mechanism (linear ranking or tournament). We denote by

e l l

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

s i g m a

, 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

p i < 1

, then the genetic algorithm operates in a disordered regime: an advantageous mutant disappears with probability larger than

, where

is a positive exponent. If

p i > 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:

p i = s i g m a (1 - p_{C}) (1 - p_{M})^{e} l l

should be slightly larger than

1

;

p_{M}

should be of order

1 / e l l

;

m

should be larger than

e l l l n e l l

; the running time should be of exponential order in

m

. The first condition requires that

e l l p_{M} + p_{C} < l n s i g m a

. 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.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: The quasispecies regime for the simple genetic algorithm with ranking selection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5267963)