Black-Box Complexity of the Binary Value Function

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 $\lceil {\log }_{2}n\rceil +2$, where $n$ is the problem size. We augment it with an upper bound of ${\log }_{2}n+2.42141558-o(1)$, which is more precise for many values of $n$. We also present a lower bound of ${\log }_{2}n+1.1186406-o(1)$. Additionally, we prove that BinVal is an easiest function among all unimodal pseudo-Boolean functions at least for unbiased algorithms.

24 pages, one figure. An extended two-page abstract of this work will appear in proceedings of the Genetic and Evolutionary Computation Conference, GECCO'19