de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Optimizing Monotone Functions Can Be Difficult

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44338

Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45750

Winzen,  Carola
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Locator
There are no locators available
##### Fulltext (public)
There are no public fulltexts available
##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Doerr, B., Jansen, T., Sudholt, D., Winzen, C., & Zarges, C. (2010). Optimizing Monotone Functions Can Be Difficult. In R. Schaefer, C. Cotta, J. Kolodziej, & G. Rudolph (Eds.), Parallel Problem Solving from Nature, PPSN XI (pp. 42-51). Berlin: Springer. doi:10.1007/978-3-642-15844-5_5.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-16AC-C
##### 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 &lt; 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.