A New Framework for the Valuation of Algorithms for Black-Box-Optimization
Stefan Droste, Thomas Jansen, Ingo Wegener · Technische Universität Dortmund Eldorado (Technische Universität Dortmund) · 2001
Black-box optimization algorithms cannot use the specific parameters of the problem instance, i.e., of the fitness function f .Their run time is measured as the number of f -evaluations.This implies that the usual algorithmic complexity of a problem cannot be used in the black-box scenario.Therefore, a new framework for the valuation of algorithms for black-box optimization is presented allowing the notion of the black-box complexity of a problem.For several problems upper and lower bounds on their black-box complexity are presented.Moreover, it can can be concluded that randomized search heuristics whose (worst-case) expected optimization time for some problem is close to the black-box complexity of the problem are provably efficient (in the black-box scenario).The new approach is applied to several problems based on typical example functions and further interesting problems.Run times of general EAs for these problems are compared with the black-box complexity of the problem.