Black-box search by unbiased variation

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

Authors

Colleges, School and Institutes

External organisations

  • Technical University of Denmark

Abstract

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.

Details

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

Conference

Conference12th Annual Genetic and Evolutionary Computation Conference, GECCO-2010
CountryUnited States
CityPortland, OR
Period7/07/1011/07/10

Keywords

  • Black-Box complexity, Runtime analysis