Visible to the public The (1+1) Elitist Black-Box Complexity of LeadingOnes

TitleThe (1+1) Elitist Black-Box Complexity of LeadingOnes
Publication TypeConference Paper
Year of Publication2016
AuthorsDoerr, Carola, Lengler, Johannes
Conference NameProceedings of the Genetic and Evolutionary Computation Conference 2016
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-4206-3
Keywordsblack box, black box encryption, black-box complexity, composability, cryptography, elitist algorithm, Encryption, Entropy, information, leadingones, memory-restriction, Metrics, pubcrawl, Resiliency, truncation selection

One important goal of black-box complexity theory is the development of complexity models allowing to derive meaningful lower bounds for whole classes of randomized search heuristics. Complementing classical runtime analysis, black-box models help us understand how algorithmic choices such as the population size, the variation operators, or the selection rules influence the optimization time. One example for such a result is the O(n log n) lower bound for unary unbiased algorithms on functions with a unique global optimum [Lehre/Witt, GECCO 2010], which tells us that higher arity operators or biased sampling strategies are needed when trying to beat this bound. In lack of analyzing techniques, almost no non-trivial bounds are known for other restricted models. Proving such bounds therefore remains to be one of the main challenges in black-box complexity theory. With this paper we contribute to our technical toolbox for lower bound computations by proposing a new type of information-theoretic argument. We regard the permutation- and bit-invariant version of LeadingOnes and prove that its (1+1) elitist black-box complexity is O(n2), a bound that is matched by (1+1)-type evolutionary algorithms. The (1+1) elitist complexity of LeadingOnes is thus considerably larger than its unrestricted one, which is known to be of order n log log n [Afshani et al., 2013].

Citation Keydoerr_1+1_2016