MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Doerr, Benjamin
Künnemann, Marvin		dblp
dblp
Editor(s):
BibTeX cite key*:
DoerrK2013a
Title, Booktitle
Title*:
Royal Road Functions and the (1 + λ) Evolutionary Algorithm: Almost no Speed-up from Larger Offspring Populations
Booktitle*:
2013 IEEE Congress on Evolutionary Computation (CEC 2013)
Event, URLs
Conference URL::
http://www.cec2013.org/
Downloading URL:
Event Address*:
Cancun, Mexico
Language:
English
Event Date*
(no longer used):
Organization:
Institute of Electrical and Electronics Engineers (IEEE)
Event Start Date:
20 June 2013
Event End Date:
23 June 2013
Publisher
Name*:
IEEE
URL:
Address*:
Piscataway, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
June
Pages:
424-431
Year*:
2013
VG Wort Pages:
ISBN/ISSN:
978-1-4799-0453-2
Sequence Number:
DOI:
10.1109/CEC.2013.6557600
Note, Abstract, ©
(LaTeX) Abstract:
We analyze the runtime of the $(1 + \lambda)$ evolutionary algorithm (EA) on the classic royal road test function class. For a royal road function defined on bit-strings of length $n$ having block size $d\ge\log n+(c+1+\varepsilon)\log d$, we prove that the $(1 + \lambda)$ EA with $\lambda = \Theta(n^c)$ finds the optimum in an expected number of $O(\frac{2^d}{d^c}\cdot\frac{n}{d} \log \frac{n}{d})$ generations. Together with our lower bound of $\Omega(\frac{2^d}{d^c})$, this shows that for royal road functions even very large offspring populations do not reduce the runtime significantly.
Download
Access Level:
Internal

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DoerrK2013a,
AUTHOR = {Doerr, Benjamin and K{\"u}nnemann, Marvin},
 TITLE = {Royal Road Functions and the (1 + λ) Evolutionary Algorithm: Almost no Speed-up from Larger Offspring Populations},
 BOOKTITLE = {2013 IEEE Congress on Evolutionary Computation (CEC 2013)},
 PUBLISHER = {IEEE},
 YEAR = {2013},
 ORGANIZATION = {Institute of Electrical and Electronics Engineers (IEEE)},
 PAGES = {424--431},
 ADDRESS = {Cancun, Mexico},
 MONTH = {June},
 ISBN = {978-1-4799-0453-2},
 DOI = {10.1109/CEC.2013.6557600},
}

Entry last modified by Marvin Künnemann, 02/17/2014
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
01/07/2014 07:34:26 AM
Revision
0.



Editor
Marvin Künnemann



Edit Date
01/07/2014 07:34:26 AM