de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### More Effective Crossover Operators for the All-pairs Shortest Path Problem

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44338

Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44705

Johannsen,  Daniel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44814

Kötzing,  Timo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45115

Neumann,  Frank
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Locator
There are no locators available
##### Fulltext (public)
There are no public fulltexts available
##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Doerr, B., Johannsen, D., Kötzing, T., Neumann, F., & Theile, M. (2010). More Effective Crossover Operators for the All-pairs Shortest Path Problem. In R. Schaefer, C. Cotta, J. Kolodziej, & G. Rudolph (Eds.), Parallel Problem Solving from Nature, PPSN XI (pp. 184-193). Berlin: Springer. doi:10.1007/978-3-642-15844-5_19.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-168A-7
##### Abstract
The All-Pairs Shortest Path problem is the first non-artificial problem for which it was shown that adding crossover can significantly speed up a mutation-only evolutionary algorithm. Recently, the analysis of this algorithm was refined and it was shown to have an expected optimization time of $\Theta(n^{3.25}(\log n)^{0.25})$. In this work, we study two variants of the algorithm. These are based on two central concepts in recombination, \emph{repair mechanisms} and \emph{parent selection}. We show that repairing infeasible offspring leads to an improved expected optimization time of $\mathord{O}(n^{3.2}(\log n)^{0.2})$. Furthermore, we prove that choosing parents that guarantee feasible offspring results in an optimization time of $\mathord{O}(n^{3}\log n)$.