zbMATH — the first resource for mathematics

Black-box complexity for bounding the performance of randomized search heuristics. (English) Zbl 1328.68197
Borenstein, Yossi (ed.) et al., Theory and principled methods for the design of metaheuristics. Berlin: Springer (ISBN 978-3-642-33205-0/hbk; 978-3-642-33206-7/ebook). Natural Computing Series, 85-110 (2014).
Summary: In black-box optimization a search algorithm looks for a global optimum of an unknown objective function that can only be explored by sampling the function values of some points in the search space. Black-box complexity measures the number of such function evaluations that any search algorithms needs to make in the worst case to locate a global optimum of any objective function from some class of functions. The black-box complexity of a function class thus yields a lower bound on the performance for all algorithms. This chapter gives a precise and accessible introduction to the notion of black-box complexity, explains important properties and discusses several concrete examples. Starting with simple examples and proceeding step-wise to more complex examples an introduction that explains how such results can be derived is presented.
For the entire collection see [Zbl 1304.68009].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI