Crossover speeds up building-block assembly
Dirk Sudholt · 2012
We re-investigate a fundamental question: how effective is crossover in combining building blocks? 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 prove that a simple GA with uniform crossover is twice as fast as the fastest EA using only standard bit mutation, up to small-order terms. The reason is that crossover effectively turns neutral mutations into improvements by combining the right building blocks at a later stage. Compared to mutation-based EAs, 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 H 1.618/n. Similar results are proved for k-point crossover. Experiments and statistical tests confirm that our findings apply to a broad class of building-block functions.