MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Doerr, Benjamin
Johannsen, Daniel
Winzen, Carola		dblp
dblp
dblp
Editor(s):
BibTeX cite key*:
DoerrJW10b
Title, Booktitle
Title*:
Drift Analysis and Linear Functions Revisited
Booktitle*:
Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2010). - Pt. 3
Event, URLs
Conference URL::
http://wcci2010.org/home
Downloading URL:
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5586097&tag=1
Event Address*:
Barcelona, Spain
Language:
English
Event Date*
(no longer used):
Organization:
IEEE
Event Start Date:
18 July 2010
Event End Date:
23 July 2010
Publisher
Name*:
IEEE
URL:
http://www.ieee.org/index.html
Address*:
Piscataway, NJ
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
1967-1974
Year*:
2010
VG Wort Pages:
30
ISBN/ISSN:
978-1-4244-6909-3
Sequence Number:
DOI:
10.1109/CEC.2010.5586097
Note, Abstract, ©
(LaTeX) Abstract:
We regard the classical problem how the (1+1)~Evolutionary Algorithm optimizes an arbitrary linear pseudo-Boolean function. We show that any such function is optimized in time ${(1+o(1)) 1.39 e n\ln (n)}$, where ${n}$ is the length of the bit string. We also prove a lower bound of ${(1-o(1))e n\ln(n)}$, which in fact holds for all functions with a unique global optimum.
This shows that for linear functions, even though the optimization behavior might differ, the resulting runtimes are very similar. Our experimental results suggest that the true optimization times are even closer than what the theoretical guarantees promise.
Keywords:
Theory of Randomized Search Heuristics, Runtime Analysis, Evolutionary Computation, Bio-inspired Computation
Download
Access Level:
Internal

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{DoerrJW10b,
AUTHOR = {Doerr, Benjamin and Johannsen, Daniel and Winzen, Carola},
 TITLE = {Drift Analysis and Linear Functions Revisited},
 BOOKTITLE = {Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2010). - Pt. 3},
 PUBLISHER = {IEEE},
 YEAR = {2010},
 ORGANIZATION = {IEEE},
 PAGES = {1967--1974},
 ADDRESS = {Barcelona, Spain},
 ISBN = {978-1-4244-6909-3},
 DOI = {10.1109/CEC.2010.5586097},
}

Entry last modified by Anja Becker, 01/14/2011
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/07/2010 03:00:55 PM
Revisions
4.
3.
2.
1.
0.		Editor(s)
Anja Becker
Daniel Johannsen
Carola Winzen
Anja Becker
Anja Becker		Edit Dates
14.01.2011 09:30:00
01/09/2011 04:09:52 PM
01/04/2011 10:49:14 AM
03.01.2011 13:34:50
12/07/2010 03:00:55 PM