title: How Crossover Speeds up Building Block Assembly in Genetic Algorithms.
abstract: We reinvestigate a fundamental question: How effective is crossover in genetic algorithms in combining building blocks of good solutions? Although this has been discussed controversially for decades, we are still lacking a rigorous and intuitive answer. We provide such answers for royal road functions and OneMax, where every bit is a building block. For the latter, we show that using crossover makes every ([Formula: see text]+[Formula: see text]) genetic algorithm at least twice as fast as the fastest evolutionary algorithm using only standard bit mutation, up to small-order terms and for moderate [Formula: see text] and [Formula: see text]. Crossover is beneficial because it can capitalize on mutations that have both beneficial and disruptive effects on building blocks: crossover is able to repair the disruptive effects of mutation in later generations. Compared to mutation-based evolutionary algorithms, this makes multibit mutations more useful. Introducing crossover changes the optimal mutation rate on OneMax from [Formula: see text] to [Formula: see text]. This holds both for uniform crossover and k-point crossover. Experiments and statistical tests confirm that our findings apply to a broad class of building block functions.
authors.affiliation: Department of Computer Science, University of Sheffield, UK d.sudholt@sheffield.ac.uk.
authors.forename: Dirk
authors.initials: D
authors.lastname: Sudholt
mesh_terms: D000465:Algorithms; D005075:Biological Evolution; D003434:Crossing Over, Genetic / Q000235:genetics*; D006801:Humans; D008957:Models, Genetic; D059645:Mutation Rate
keywords: Genetic algorithms; crossover; mutation rate; recombination; runtime analysis; theory.