An Algorithm for Computing Lower Bounds for Unrestricted Black-Box Complexities

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

Abstract

Finding and proving lower bounds on black-box complexities is one of the hardest problems in theory of randomized search heuristics. Until recently, there were no general ways of doing this, except for information theoretic arguments similar to the one of Droste, Jansen and Wegener.

In a recent paper by Buzdalov, Kever and Doerr, a theorem is proven which may yield tighter bounds on unrestricted black-box complexity using certain problem-specific information. To use this theorem, one should split the search process into a finite number of states, describe transitions between states, and for each state specify (and prove) the maximum number of different answers to any query.

We augment these state constraints by one more kind of constraints on states, namely, the maximum number of different currently possible optima. An algorithm is presented for computing the lower bounds based on these constraints. We also empirically show improved lower bounds on black-box complexity of OneMax and Mastermind.
Original languageEnglish
Title of host publicationGECCO '16 Companion
Subtitle of host publicationProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion
EditorsTobias Friedrich, Frank Neumann, Andrew M. Sutton
PublisherInstitute of Electrical and Electronics Engineers
Pages147-148
Number of pages2
ISBN (Print)9781450343237, 1450343236
DOIs
Publication statusPublished - 20 Jul 2016
Externally publishedYes
EventGECCO 2016 - Genetic and Evolutionary Computation Conference - Denver, United States of America
Duration: 20 Jul 201624 Jul 2016

Conference

ConferenceGECCO 2016 - Genetic and Evolutionary Computation Conference
Country/TerritoryUnited States of America
CityDenver
Period20 Jul 201624 Jul 2016

Keywords

  • black-box complexity
  • lower bounds
  • mastermind
  • onemax

Fingerprint

Dive into the research topics of 'An Algorithm for Computing Lower Bounds for Unrestricted Black-Box Complexities'. Together they form a unique fingerprint.

Cite this