TY - GEN

T1 - Black-box complexity of the binary value function

AU - Bulanova, Nina

AU - Buzdalov, Maxim

N1 - Publisher Copyright:
© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.

PY - 2019/7/13

Y1 - 2019/7/13

N2 - 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.

AB - 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.

KW - BinVal

KW - Linear functions

KW - Unbiased black-box complexity

UR - http://www.scopus.com/inward/record.url?scp=85070632669&partnerID=8YFLogxK

U2 - 10.1145/3319619.3322070

DO - 10.1145/3319619.3322070

M3 - Conference Proceeding (Non-Journal item)

AN - SCOPUS:85070632669

T3 - GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion

SP - 423

EP - 424

BT - GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion

PB - Association for Computing Machinery, Inc

T2 - 2019 Genetic and Evolutionary Computation Conference, GECCO 2019

Y2 - 13 July 2019 through 17 July 2019

ER -