Rate of convergence of crossover operators

DOI10.1002/RSA.10085MaRDI QIDQ4417003zbMATH OpenOpenAlexFDO

Authors Y. Ollivier

Publication date 6 August 2003

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.10085

zbMATH Keywords

crossovermixing timequadratic dynamical systems

Mathematics Subject Classification ID

Ergodicity, mixing, rates of mixing (37A25) Dynamical systems in biology (37N25) Probability distributions: general theory (60E05) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Randomized algorithms (68W20) Genetics and epigenetics (92D10)

Review text

The paper deals with a mating operator. The mating operator consists in having a stem population replaced by a new one in the following way: An individual from the new populations is obtained by randomly, uniformly sampling two distinct individuals in the stem population and mixing their genomes in some prescribed way. These operations are repeated independently in order to obtain the individuals of the new population. The aim of the paper is to answer questions of \textit{Y. Rabani} et al. [see ibid. 12, 313--334 (1998; Zbl 0955.92023)] on the divergence between finite- and infinite-population processes. To this end results for the infinite case are recalled and, moreover, specific characteristics of finite and infinite cases are explained. To obtain new results also the theory of Markov chains is employed.

Recommendations

• A computational view of population genetics
• Techniques for bounding the convergence rate of genetic algorithms
• scientific article; zbMATH DE number 1263184
• Characterizing crossover in genetic algorithms.
• On the convergence rates of genetic algorithms

Cites work

• scientific article; zbMATH DE number 3657493 (Why is no real title available?)
• Simulating quadratic dynamical systems is PSPACE-complete (preliminary version)

Cited in

(4)

• Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs
• The mixing rate of different crossover operators
• scientific article; zbMATH DE number 1263184 (Why is no real title available?)
• A computational view of population genetics

This page was built for publication: Rate of convergence of crossover operators

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