de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Reducing the Arity in Unbiased Black-Box Complexity

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., & Winzen, C. (2012). Reducing the Arity in Unbiased Black-Box Complexity. In T. Soule, & J. H. Moore (Eds.), GECCO'12 (pp. 1309-1316). New York, NY: ACM.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-BC79-3
Abstract
We show that for all 1<k ≤q \log n the k-ary unbiased black-box complexity of the n-dimensional \onemax function class is O(n/k). This indicates that the power of higher arity operators is much stronger than what the previous O(n/\log k) bound by Doerr et al. (Faster black-box algorithms through higher arity operators, Proc. of FOGA 2011, pp. 163--172, ACM, 2011) suggests. The key to this result is an encoding strategy, which might be of independent interest. We show that, using k-ary unbiased variation operators only, we may simulate an unrestricted memory of size O(2^k) bits.