Quarterly (spring, summer, fall, winter)
176 pp. per issue
7 x 10
ISSN
1063-6560
E-ISSN
1530-9304
2014 Impact factor:
2.37

Evolutionary Computation

Winter 2016, Vol. 24, No. 4, Pages 719-744
(doi: 10.1162/EVCO_a_00185)
© 2016 Massachusetts Institute of Technology
The Unrestricted Black-Box Complexity of Jump Functions
Article PDF (361.7 KB)
Abstract

We analyze the unrestricted black-box complexity of the Jump function classes for different jump sizes. For upper bounds, we present three algorithms for small, medium, and extreme jump sizes. We prove a matrix lower bound theorem which is capable of giving better lower bounds than the classic information theory approach. Using this theorem, we prove lower bounds that almost match the upper bounds. For the case of extreme jump functions, which apart from the optimum reveal only the middle fitness value(s), we use an additional lower bound argument to show that any black-box algorithm does not gain significant insight about the problem instance from the first fitness evaluations. This, together with our upper bound, shows that the black-box complexity of extreme jump functions is .