Black-Box Complexity of the Binary Value Function
This work addresses a theoretical problem in evolutionary computation by refining complexity bounds for a key function, which is incremental but provides precise mathematical insights for researchers in the field.
The paper tackles the problem of determining the black-box complexity of the binary value function (BinVal) in evolutionary computation, providing a more precise upper bound of log2 n + 2.42141558 - o(1) and a lower bound of log2 n + 1.1186406 - o(1), and proving that BinVal is the easiest function among unimodal pseudo-Boolean functions for unbiased algorithms.
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.