@inproceedings{0835ac5310bc482ba4881ded0793023b,
title = "Improved analysis methods for crossover-based algorithms",
abstract = "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(n3.25 log1/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.",
keywords = "Combinatorial optimization, Crossover, Evolutionary algorithm",
author = "Benjamin Doerr and Madeleine Theile",
year = "2009",
month = dec,
day = "31",
doi = "10.1145/1569901.1569937",
language = "English",
isbn = "9781605583259",
series = "Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009",
pages = "247--253",
booktitle = "Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009",
note = "11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009 ; Conference date: 08-07-2009 Through 12-07-2009",
}