Solving the all-pairs shortest path problem with genetic algorithms

Doerr, Happ and Klein proposed a genetic algorithm for the all-pairs shortest path problem proving for the first time that a genetic algorithm (using crossover) can beat an evolutionary algorithm (using only mutation) on a non-artificial combinatorial optimization problem.

In this talk, we give a tight analysis of the optimization time of this algorithm, which we prove to be $\Theta(n^{3.25} \log^{0.25} n)$. Besides the mere run-time result, such an analysis is a step towards understanding how crossover works. This is joint work with Benjamin Doerr.