English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

MPS-Authors
/persons/resource/persons44338

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

/persons/resource/persons44705

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

/persons/resource/persons44814

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

/persons/resource/persons45115

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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
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: https://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)$.