zbMATH — the first resource for mathematics

No free lunch and free leftovers theorems for multiobjective optimisation problems. (English) Zbl 1036.90523
Fonseca, Carlos M. (ed.) et al., Evolutionary multi-criterion optimization. Second international conference, EMO 2003, Faro, Portugal, April 8–11, 2003. Proceedings. Berlin: Springer (ISBN 3-540-01869-7/pbk). Lect. Notes Comput. Sci. 2632, 327-341 (2003).
Summary: The classic NFL theorems are invariably cast in terms of single objective optimization problems. We confirm that the classic NFL theorem holds for general multiobjective fitness spaces, and show how this follows from a ‘single-objective’ NFL theorem. We also show that, given any particular Pareto front, an NFL theorem holds for the set of all multiobjective problems which have that Pareto front. It follows that, given any ‘shape’ or class of Pareto fronts, an NFL theorem holds for the set of all multiobjective problems in that class. These findings have salience in test function design. Such NFL results are cast in the typical context of absolute performance, assuming a performance metric which returns a value based on the result produced by a single algorithm. But, in multiobjective search we commonly use comparative metrics, which return performance measures based non-trivially on the results from two (or more) algorithms. Closely related to but extending the observations in the seminal NFL work concerning minimax distinctions between algorithms, we provide a ‘Free Leftovers’ theorem for comparative performance of algorithms over permutation functions; in words: over the space of permutation problems, every algorithm has some companion algorithm(s) which it outperforms, according to a certain well-behaved metric, when comparative performance is summed over all problems in the space.
For the entire collection see [Zbl 1018.00013].

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