# How Crossover Speeds Up Building-Block Assembly in Genetic Algorithms

arXiv: https://arxiv.org/abs/1403.6600 · HTML: https://mlsanity.com/paper/1403.6600/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2014.

## Built on by (most cited first, 3 of 3)

- [An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics](https://mlsanity.com/paper/2105.03090/) (2021)
- [Many Objective Problems Where Crossover is Provably Essential](https://mlsanity.com/paper/2412.18375/) (2024)
- [Frequency Fitness Assignment: Optimization without Bias for Good Solutions can be Efficient](https://mlsanity.com/paper/2112.00229/) (2021)

## Abstract (arXiv)

We re-investigate 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 (μ+λ) 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 μ and λ. Crossover is beneficial because it effectively turns fitness-neutral mutations into improvements by combining the right building blocks at a later stage. Compared to mutation-based evolutionary algorithms, this makes multi-bit mutations more useful. Introducing crossover changes the optimal mutation rate on OneMax from 1/n to (1+√5)/2 · 1/n ≈ 1.618/n. 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.