On the black-box complexity of example functions: The Real Jump function

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

18 Citations (SciVal)


Black-box complexity measures the difficulty of classes of functions with respect to optimisation by black-box algorithms. Comparing the black-box complexity with the worst case performance of a best know randomised search heuristic can help to assess if the randomised search heuristic is efficient or if there is room for improvement. When considering an example function it is necessary to extend it to a class of functions since single functions always have black-box complexity 1. Different kinds of extensions of single functions to function classes have been considered. In cases where the gap between the performance of the best randomised search heuristic and the black-box complexity is still large it can help to consider more restricted black-box complexity notions like unbiased black-box complexity. For the well-known Jump function neither considering different extensions nor considering more restricted notions of black-box complexity have been successful so far. We argue that the problem is not with the notion of black-box complexity but with the extension to a function class. We propose a different extension and show that for this extension there is a much better agreement even between the performance of an extremely simple evolutionary algorithm and the most general notion of black-box complexity.
Original languageEnglish
Title of host publication13th ACM SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA 2015)
Place of PublicationNew York
PublisherAssociation for Computing Machinery
ISBN (Print)978-1-4503-3434-1
Publication statusPublished - Jan 2015
EventFOGA '15 Foundations of Genetic Algorithms XIII - Aberystwyth, United Kingdon, United Kingdom of Great Britain and Northern Ireland
Duration: 17 Jan 201520 Jan 2015


ConferenceFOGA '15 Foundations of Genetic Algorithms XIII
Country/TerritoryUnited Kingdom of Great Britain and Northern Ireland
Period17 Jan 201520 Jan 2015


Dive into the research topics of 'On the black-box complexity of example functions: The Real Jump function'. Together they form a unique fingerprint.

Cite this