title: Introducing Elitist Black-Box Models: When Does Elitist Behavior Weaken the Performance of Evolutionary Algorithms?
abstract: Black-box complexity theory provides lower bounds for the runtime of black-box optimizers like evolutionary algorithms and other search heuristics and serves as an inspiration for the design of new genetic algorithms. Several black-box models covering different classes of algorithms exist, each highlighting a different aspect of the algorithms under considerations. In this work we add to the existing black-box notions a new elitist black-box model, in which algorithms are required to base all decisions solely on (the relative performance of) a fixed number of the best search points sampled so far. Our elitist model thus combines features of the ranking-based and the memory-restricted black-box models with an enforced usage of truncation selection. We provide several examples for which the elitist black-box complexity is exponentially larger than that of the respective complexities in all previous black-box models, thus showing that the elitist black-box complexity can be much closer to the runtime of typical evolutionary algorithms. We also introduce the concept of p-Monte Carlo black-box complexity, which measures the time it takes to optimize a problem with failure probability at most p. Even for small  p, the p-Monte Carlo black-box complexity of a function class [Formula: see text] can be smaller by an exponential factor than its typically regarded Las Vegas complexity (which measures the expected time it takes to optimize [Formula: see text]).
authors.affiliation: CNRS and Sorbonne Universités, UPMC Univ Paris 06, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France.
authors.forename: Carola
authors.initials: C
authors.lastname: Doerr
authors.affiliation: ETH Zürich, Department of Computer Science, Institute for Theoretical Computer Science, 8092 Zürich, Switzerland.
authors.forename: Johannes
authors.initials: J
authors.lastname: Lengler
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D019143:Evolution, Molecular; D009010:Monte Carlo Method; D011336:Probability
keywords: Black-box complexity; comparison-based algorithms; elitist selection; evolutionary computation