Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: More effective crossover operators for the all-pairs shortest path problem
Author: Doerr, B.
Johannsen, D.
Kotzing, T.
Neumann, F.
Theile, M.
Citation: Parallel Problem Solving from Nature – PPSN XI: 11th International Conference, Kraków, Poland, September 11-15, 2010, Proceedings, Part I / Robert Schaefer, Carlos Cotta, Joanna Kołodziej and Günter Rudolph (eds.): pp.184-193
Publisher: Springer-Verlag
Publisher Place: Berlin
Issue Date: 2010
Series/Report no.: Lecture Notes in Computer Science ; 6238
ISBN: 3642158439
ISSN: 0302-9743
Conference Name: International Conference on Parallel Problem Solving from Nature (11th : 2010 : Krakow, Poland)
Editor: Schaefer, R.
Cotta, C.
Kolodziej, J.
Rudolph, G.
Statement of
Benjamin Doerr, Daniel Johannsen, Timo Kötzing, Frank Neumann and Madeleine Theile
Abstract: The all-pairs 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 Θ(n 3.25(logn)0.25). In this work, we study two variants of the algorithm. These are based on two central concepts in recombination, repair mechanisms and parent selection. We show that repairing infeasible offspring leads to an improved expected optimization time of O(n3 2(logn)0 2). Furthermore, we prove that choosing parents that guarantee feasible offspring results in an optimization time of O(n3logn).
Rights: © Springer-Verlag Berlin Heidelberg 2010
DOI: 10.1007/978-3-642-15844-5_19
Published version:
Appears in Collections:Aurora harvest 5
Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.