improved analysis methods for crossover-based algorithms
We deepen the theoretical analysis of the genetic algorithm for the all-pairs shortest path problem proposed by Doerr, Happ and Klein (GECCO 2008). We show that the growth of the paths through crossover operations can be analyzed without the previously used approach of waiting until all paths of a certain length are present in the population. This allows to prove an improved guarantee for the optimization time of O (n 3.25 log 1/4 (n) . We also show that this bound is asymptotically tight. Besides the mere run-time result, our analysis is a step towards understanding how crossover works and how it can be analyzed with rigorous methods.
crossover evolutionary algorithm combinatorial optimization