Abstract
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 language | English |
---|---|
Title of host publication | 13th ACM SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA 2015) |
Place of Publication | New York |
Publisher | Association for Computing Machinery |
Pages | 16-24 |
ISBN (Print) | 978-1-4503-3434-1 |
Publication status | Published - Jan 2015 |
Event | FOGA '15 Foundations of Genetic Algorithms XIII - Aberystwyth, United Kingdon, United Kingdom of Great Britain and Northern Ireland Duration: 17 Jan 2015 → 20 Jan 2015 |
Conference
Conference | FOGA '15 Foundations of Genetic Algorithms XIII |
---|---|
Country/Territory | United Kingdom of Great Britain and Northern Ireland |
Period | 17 Jan 2015 → 20 Jan 2015 |