Black-box search by unbiased variation

Per Kristián Lehre, Carsten Witt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

40 Citations (Scopus)


The complexity theory for black-box algorithms, introduced by Droste et al. (2006), describes common limits on the efficiency of a broad class of randomised search heuristics. There is an obvious trade-off between the generality of the black-box model and the strength of the bounds that can be proven in such a model. In particular, the original blackbox model allows polynomial complexity for certain NPcomplete problems and provides for well-known benchmark problems relatively small lower bounds, which are typically not met by popular search heuristics. In this paper, we introduce a more restricted black-box model which we claim captures the working principles of many randomised search heuristics including simulated annealing, evolutionary algorithms, randomised local search and others. The key concept worked out is an unbiased variation operator. Considering this class of algorithms, significantly better lower bounds on the black-box complexity are proved, amongst them an (n log n) bound for functions with unique optimum. Moreover, a simple unimodal function and gap functions are considered. We show that a simple (1+1) EA is able to match the runtime bounds in several cases.

Original languageEnglish
Title of host publicationProceedings of the 12th Annual Genetic and Evolutionary Computation Conference, GECCO '10
Number of pages8
Publication statusPublished - 2010
Event12th Annual Genetic and Evolutionary Computation Conference, GECCO-2010 - Portland, OR, United States
Duration: 7 Jul 201011 Jul 2010


Conference12th Annual Genetic and Evolutionary Computation Conference, GECCO-2010
Country/TerritoryUnited States
CityPortland, OR


  • Black-Box complexity
  • Runtime analysis

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Theoretical Computer Science


Dive into the research topics of 'Black-box search by unbiased variation'. Together they form a unique fingerprint.

Cite this