title: The Unrestricted Black-Box Complexity of Jump Functions.
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 [Formula: see text] fitness evaluations. This, together with our upper bound, shows that the black-box complexity of extreme jump functions is [Formula: see text].
authors.affiliation: ITMO University, 49 Kpohbepkckuŭ npocnekt, Saint Petersburg, 197101, Russia mbuzdalov@gmail.com.
authors.forename: Maxim
authors.initials: M
authors.lastname: Buzdalov
authors.affiliation: LIX, École Polytechnique, 91126 Palaiseau Cedex, France doerr@lix.polytechnique.fr.
authors.forename: Benjamin
authors.initials: B
authors.lastname: Doerr
authors.affiliation: ITMO University, 49 Kpohbepkckuŭ npocnekt, Saint Petersburg, 197101, Russia mikhail.kever@gmail.com.
authors.forename: Mikhail
authors.initials: M
authors.lastname: Kever
mesh_terms: D000465:Algorithms; D005075:Biological Evolution; D000067508:Computer Heuristics; D003198:Computer Simulation
keywords: Black-box complexity; information theory.; jump functions