2014/03/21 by Raphaël Cerf, Cerf, Raphaël
Computer Science · #60J10 (Primary) 92D15 (Secondary) #Data Mining Algorithms and Applications #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE) #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1403.5427
openalex publication_date 2014/03/21 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
We study the simple genetic algorithm with a ranking selection mechanism\n(linear ranking or tournament). We denote by \ℓ the length of the\nchromosomes, by m the population size, by pC the crossover probability and\nby pM the mutation probability. We introduce a parameter \σ, called\nthe selection drift, which measures the selection intensity of the fittest\nchromosome. We show that the dynamics of the genetic algorithm depend in a\ncritical way on the parameter
pi
,=
,
sigma(1-pC)(1-pM)^
ell
,. If\n\π<1, then the genetic algorithm operates in a disordered regime: an\nadvantageous mutant disappears with probability larger than 1-1/m^\β,\nwhere \β is a positive exponent. If \π>1, then the genetic algorithm\noperates in a quasispecies regime: an advantageous mutant invades a positive\nfraction of the population with probability larger than a constant p^* (which\ndoes not depend on m). We estimate next the probability of the occurrence of\na catastrophe (the whole population falls below a fitness level which was\npreviously reached by a positive fraction of the population). The asymptotic\nresults suggest the following rules: \π=\σ(1-pC)(1-pM)^\ℓ should be\nslightly larger than 1; pM should be of order 1/\ℓ; m should be\nlarger than \ℓ\ln\ℓ; the running time should be of exponential order in\nm. The first condition requires that \ℓ pM +pC< \ln\σ. These\nconclusions must be taken with great care: they come from an asymptotic regime,\nand it is a formidable task to understand the relevance of this regime for a\nreal-world problem. At least, we hope that these conclusions provide\ninteresting guidelines for the practical implementation of the simple genetic\nalgorithm.\n