Black-box complexity of the binary value function

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

Abstract

The binary value function, or BinVal, has appeared in several studies in theory of evolutionary computation as one of the extreme examples of linear pseudo-Boolean functions. Its unbiased black-box complexity was previously shown to be at most ?log2 n? + 2, where n is the problem size. We augment it with an upper bound of log2 n+2.42141558-o(1), which is more precise for roughly a half of values of n. We also present a lower bound of log2 n + 1.1186406 - o(1) and provide an algorithm to compute the exact black-box complexity of BinVal for a given n.

Original languageEnglish
Title of host publicationGECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion
PublisherAssociation for Computing Machinery, Inc
Pages423-424
Number of pages2
ISBN (Electronic)9781450367486
DOIs
Publication statusPublished - 13 Jul 2019
Externally publishedYes
Event2019 Genetic and Evolutionary Computation Conference, GECCO 2019 - Prague, Czech Republic
Duration: 13 Jul 201917 Jul 2019

Publication series

NameGECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion

Conference

Conference2019 Genetic and Evolutionary Computation Conference, GECCO 2019
Country/TerritoryCzech Republic
CityPrague
Period13 Jul 201917 Jul 2019

Keywords

  • BinVal
  • Linear functions
  • Unbiased black-box complexity

Fingerprint

Dive into the research topics of 'Black-box complexity of the binary value function'. Together they form a unique fingerprint.

Cite this