Black-Box Complexity of the Binary Value Function
share
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 _2 n + 2, where n is the problem size. We augment it with an upper bound of _2 n + 2.42141558 - o(1), which is more precise for many values of n. We also present a lower bound of _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.
READ FULL TEXT
