Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Doerr, Benjamin
Johannsen, Daniel
Kötzing, Timo
Neumann, Frank
Theile, Madeleine

dblp
dblp
dblp
dblp
dblp

Not MPG Author(s):

Theile, Madeleine

Editor(s):

Schaefer, Robert
Cotta, Carlos
Kolodziej, Joanna
Rudolph, Günter

dblp
dblp
dblp
dblp

Not MPII Editor(s):

Schaefer, Robert
Cotta, Carlos
Kolodziej, Joanna
Rudolph, Günter

BibTeX cite key*:

Doe-Joh-Koe-Neu-The:c:10:APSPCrossover

Title, Booktitle

Title*:

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

Booktitle*:

Parallel Problem Solving from Nature - PPSN XI. - Pt. 1

Event, URLs

URL of the conference:


URL for downloading the paper:

http://dx.doi.org/10.1007/978-3-642-15844-5_19

Event Address*:

Krakow, Poland

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

11 September 2010

Event End Date:

15 September 2010

Publisher

Name*:

Springer

URL:


Address*:

Berlin

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

6238

Number:


Month:


Pages:

184-193

Year*:

2010

VG Wort Pages:

19

ISBN/ISSN:

978-3-642-15843-8

Sequence Number:


DOI:

10.1007/978-3-642-15844-5_19



Note, Abstract, ©


(LaTeX) 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)$.



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Doe-Joh-Koe-Neu-The:c:10:APSPCrossover,
AUTHOR = {Doerr, Benjamin and Johannsen, Daniel and K{\"o}tzing, Timo and Neumann, Frank and Theile, Madeleine},
EDITOR = {Schaefer, Robert and Cotta, Carlos and Kolodziej, Joanna and Rudolph, G{\"u}nter},
TITLE = {More Effective Crossover Operators for the All-Pairs Shortest Path Problem},
BOOKTITLE = {Parallel Problem Solving from Nature - PPSN XI. - Pt. 1},
PUBLISHER = {Springer},
YEAR = {2010},
VOLUME = {6238},
PAGES = {184--193},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Krakow, Poland},
ISBN = {978-3-642-15843-8},
DOI = {10.1007/978-3-642-15844-5_19},
}


Entry last modified by Anja Becker, 02/14/2011
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
12/15/2010 12:05:31 PM
Revisions
3.
2.
1.
0.
Editor(s)
Anja Becker
Anja Becker
Timo Kötzing
Timo Kötzing
Edit Dates
14.02.2011 13:12:25
03.01.2011 13:20:29
12/15/2010 03:59:10 PM
12/15/2010 12:05:31 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section