Workshop Theory of Randomized Search Heuristics

Abstract

Crossover is Provably Useful in Evolutionary Computation

by Benjamin Doerr, Edda Happ, Christian Klein

We present a genetic algorithm for the all-pairs shortest path problem that uses both mutation and crossover. A rigorous runtime analysis shows that the use of crossover significantly improves the optimization time of the algorithm from $\Theta(n^4)$ to $O(n^{3.5+\epsilon})$. This is the first rigorous analysis showing the usefulness of crossover for a non-artificial problem.


Back to mainpage