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
Jansen, Thomas
Sudholt, Dirk
Winzen, Carola
Zarges, Christine
dblp
dblp
dblp
dblp
dblp
Not MPG Author(s):

Jansen, Thomas
Sudholt, Dirk
Zarges, Christine

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*:

DoerrJSWZ10

Title, Booktitle

Title*:

Optimizing Monotone Functions Can Be Difficult

Booktitle*:

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

Event, URLs

URL of the conference:

http://home.agh.edu.pl/~ppsn/

URL for downloading the paper:

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

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:

http://www.springer.com/computer/lncs?SGWID=0-164-0-0-0

Address*:

Berlin
Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

6238
Number:


Month:

September
Pages:

42-51

Year*:

2010
VG Wort Pages:

27

ISBN/ISSN:

978-3-642-15843-8
Sequence Number:


DOI:

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


Note, Abstract, ©


(LaTeX) Abstract:

Extending previous analyses on function classes like linear functions, we analyze how the simple (1+1) evolutionary algorithm optimizes pseudo-Boolean functions that are strictly monotone.
Contrary to what one would expect, not all of these functions are easy to optimize. The choice of the constant $c$ in the mutation probability $p(n) = c/n$ can make a decisive difference.

We show that if $c < 1$, then the \EA finds the optimum of every such function in $\Theta(n \log n)$ iterations. For $c=1$, we can still prove an upper bound of $O(n^{3/2})$.
However, for $c > 33$, we present a strictly monotone function such that the \EA with overwhelming
probability does not find the optimum within $2^{\Omega(n)}$
iterations. This is the first time that we observe that a constant factor change of the mutation probability changes the run-time by more than constant factors.



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{DoerrJSWZ10,
AUTHOR = {Doerr, Benjamin and Jansen, Thomas and Sudholt, Dirk and Winzen, Carola and Zarges, Christine},
 EDITOR = {Schaefer, Robert and Cotta, Carlos and Kolodziej, Joanna and Rudolph, G{\"u}nter},
 TITLE = {Optimizing Monotone Functions Can Be Difficult},
 BOOKTITLE = {Parallel Problem Solving from Nature - PPSN XI. - Pt. 1},
 PUBLISHER = {Springer},
 YEAR = {2010},
 VOLUME = {6238},
 PAGES = {42--51},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Krakow, Poland},
 MONTH = {September},
 ISBN = {978-3-642-15843-8},
 DOI = {10.1007/978-3-642-15844-5_5},
}

Entry last modified by Manuel Lamotte-Schubert, 03/21/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
09/28/2010 02:48:47 PM
Revisions
4.
3.
2.
1.
0.		Editor(s)
Manuel Lamotte-Schubert
Anja Becker
Carola Winzen
Anja Becker
Anja Becker		Edit Dates
21.03.2011 08:40:56
14.02.2011 13:15:42
01/04/2011 10:48:42 AM
03.01.2011 13:18:31
09/28/2010 02:48:47 PM