TY - GEN

T1 - Better fixed-arity unbiased black-box algorithms

AU - Bulanova, Nina

AU - Buzdalov, Maxim

N1 - Publisher Copyright:
© 2018 Copyright held by the owner/author(s).

PY - 2018/7/6

Y1 - 2018/7/6

N2 - In their GECCO'12 paper, Doerr and Doerr proved that the k-ary unbiased black-box complexity of OneMax on n bits is O(n/k) for 2 ≤ k ≤ log2 n. We propose an alternative strategy for achieving this unbiased black-box complexity when 3 ≤ k ≤ log2 n. While it is based on the same idea of block-wise optimization, it uses k-ary unbiased operators in a different way. For each block of size 2k −1 − 1 we set up, in O(k) queries, a virtual coordinate system, which enables us to use an arbitrary unrestricted algorithm to optimize this block. This is possible because this coordinate system introduces a bijection between unrestricted queries and a subset of k-ary unbiased operators. We note that this technique does not depend on OneMax being solved and can be used in more general contexts. This together constitutes an algorithm which is conceptually simpler than the one by Doerr and Doerr, and in the same time achieves better constant multiples in the asymptotic notation. Our algorithm works in (2 + o(1)) · n/(k − 1), where o(1) relates to k. Our experimental evaluation of this algorithm shows its efficiency already for 3 ≤ k ≤ 6.

AB - In their GECCO'12 paper, Doerr and Doerr proved that the k-ary unbiased black-box complexity of OneMax on n bits is O(n/k) for 2 ≤ k ≤ log2 n. We propose an alternative strategy for achieving this unbiased black-box complexity when 3 ≤ k ≤ log2 n. While it is based on the same idea of block-wise optimization, it uses k-ary unbiased operators in a different way. For each block of size 2k −1 − 1 we set up, in O(k) queries, a virtual coordinate system, which enables us to use an arbitrary unrestricted algorithm to optimize this block. This is possible because this coordinate system introduces a bijection between unrestricted queries and a subset of k-ary unbiased operators. We note that this technique does not depend on OneMax being solved and can be used in more general contexts. This together constitutes an algorithm which is conceptually simpler than the one by Doerr and Doerr, and in the same time achieves better constant multiples in the asymptotic notation. Our algorithm works in (2 + o(1)) · n/(k − 1), where o(1) relates to k. Our experimental evaluation of this algorithm shows its efficiency already for 3 ≤ k ≤ 6.

KW - Black-box complexity

KW - OneMax

KW - Unbiased variation

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

U2 - 10.1145/3205651.3205762

DO - 10.1145/3205651.3205762

M3 - Conference Proceeding (Non-Journal item)

AN - SCOPUS:85051552481

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

SP - 322

EP - 323

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

PB - Association for Computing Machinery

T2 - 2018 Genetic and Evolutionary Computation Conference, GECCO 2018

Y2 - 15 July 2018 through 19 July 2018

ER -