The (1+1) Elitist Black-Box Complexity of LeadingOnes

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