TY - GEN
T1 - Reducing the arity in unbiased black-box complexity
AU - Doerr, Benjamin
AU - Winzen, Carola
PY - 2012/8/13
Y1 - 2012/8/13
N2 - We show that for all 1 k d log n the k-ary unbiased black-box complexity of the n-dimensional OneMax function class is O(n/k). This indicates that the power of higher arity operators is much stronger than what the previous O(n/log k) bound by Doerr et al. (Faster black-box algorithms through higher arity operators, Proc. of FOGA 2011, pp. 163 - 172, ACM, 2011) suggests. The key to this result is an encoding strategy, which might be of independent interest. We show that, using k-ary unbiased variation operators only, we may simulate an unrestricted memory of size O(2 k) bits.
AB - We show that for all 1 k d log n the k-ary unbiased black-box complexity of the n-dimensional OneMax function class is O(n/k). This indicates that the power of higher arity operators is much stronger than what the previous O(n/log k) bound by Doerr et al. (Faster black-box algorithms through higher arity operators, Proc. of FOGA 2011, pp. 163 - 172, ACM, 2011) suggests. The key to this result is an encoding strategy, which might be of independent interest. We show that, using k-ary unbiased variation operators only, we may simulate an unrestricted memory of size O(2 k) bits.
KW - black-box complexity
KW - running time analysis
KW - theory
UR - https://www.scopus.com/pages/publications/84864708493
U2 - 10.1145/2330163.2330345
DO - 10.1145/2330163.2330345
M3 - Conference contribution
AN - SCOPUS:84864708493
SN - 9781450311779
T3 - GECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation
SP - 1309
EP - 1316
BT - GECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation
T2 - 14th International Conference on Genetic and Evolutionary Computation, GECCO'12
Y2 - 7 July 2012 through 11 July 2012
ER -