The quasispecies regime for the simple genetic algorithm with ranking selection

DOI10.1090/TRAN/7170zbMATH Open1370.92101arXiv1403.5427OpenAlexW2963274118MaRDI QIDQ5267963FDOQ5267963

Raphaël Cerf

Publication date: 14 June 2017

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

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 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 ${\displaystyle }$pi ,=,sigma(1-p_C)(1-p_M)^ell,.${\displaystyle }$ If $pi<1$, then the genetic algorithm operates in a disordered regime: an advantageous mutant disappears with probability larger than $$, where $$ 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{)}^{e}ll$ should be slightly larger than $1$; $p_M$ should be of order $1/ell$; $m$ should be larger than $elllnell$; the running time should be of exponential order in $m$. The first condition requires that $ell{p}_M+p_C<lnsigma$. 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.

Full work available at URL: https://arxiv.org/abs/1403.5427

zbMATH Keywords

stochastic optimizationgenetic algorithmsquasispecies

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Probability Inequalities for Sums of Bounded Random Variables
• Title not available (Why is that?)
• Critical population and error threshold on the sharp peak landscape for the Wright-Fisher model
• The distribution of the quasispecies for the Wright-Fisher model on the sharp peak landscape
• Interacting particle systems. With a new postface.
• Entropy, large deviations, and statistical mechanics.
• Title not available (Why is that?)
• Modeling genetic algorithms with Markov chains.
• Theory of genetic algorithms
• Theory of genetic algorithms. II: Models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling
• Statistical Dynamics of the Royal Road Genetic Algorithm
• Optimizing epochal evolutionary search: Population-size dependent theory
• Title not available (Why is that?)
• A discrete-time version of the Wentzell-Freidlin theory
• A Markov Chain Analysis of Genetic Algorithms: Large Deviation Principle Approach
• Markov chain analysis of genetic algorithms applied to fitness functions perturbed concurrently by additive and multiplicative noise
• Title not available (Why is that?)
• Convergence Criteria for Genetic Algorithms
• Dynamiques recuites de type Feynman-Kac : résultats précis et conjectures
• On the effect of selection in genetic algorithms
• On the Convergence and Applications of Generalized Simulated Annealing
• Finite populations induce metastability in evolutionary search.
• Metastable evolutionary dynamics: crossing fitness barriers or escaping via neutral paths?
• On the convergence of genetic algorithms
• Parallel problem solving from nature. 1st workshop, PPSN 1, Dortmund, Germany, October 1-3, 1990. Proceedings
• Quasispecies and recombination
• Phase transitions and symmetry breaking in genetic algorithms with crossover
• Sharp asymptotics for fixation times in stochastic population genetics models at low mutation probabilities
• Title not available (Why is that?)
• Genealogies and increasing propagation of chaos for Feynman-Kac and genetic models.
• Characteristic analysis and prevention on premature convergence in genetic algorithms
• Title not available (Why is that?)
• Sharp asymptotic results for simplified mutation-selection algorithms
• Optimizing epochal evolutionary search: population-size independent theory.
• Global optimization with exploration/selection algorithms and simulated annealing
• Genetic algorithms: Bridging the convergence gap
• Title not available (Why is that?)
• A new genetic algorithm specifically based on mutation and selection
• Genetic algorithms in random environments: two examples
• A weighted random walk model, with application to a genetic algorithm

Cited In (7)

• Foundations of Genetic Algorithms
• Optimization by hierarchical mutant production
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The quasispecies regime for the simple genetic algorithm with roulette wheel selection

   Recommendations

• The quasispecies regime for the simple genetic algorithm with roulette wheel selection 👍 👎
• Quasi-random initial population for genetic algorithms 👍 👎
• THE DYNAMICS OF A CHANGING RANGE GENETIC ALGORITHM UNDER STABILIZING SELECTION 👍 👎
• Title not available (Why is that?) 👍 👎
• Genetic algorithm and its convergence based on quasi-descent method 👍 👎

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)