Abstract:

The classic NFL theorems are invariably cast in terms of single
objective optimization problems. We confirm that the basic static 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 readily
follows that, given any particular `shape' or class of Pareto fronts,
an NFL theorem holds for the set of all multiobjective problems which
have that shape of Pareto front. These findings have salience in
issues relating to 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. However, in multiobjective search we commonly use
comparative metrics, which return performance measures based on the
results from two algorithms. Closely related to but extending the
observations in the seminal NFL work concerning minimax distinctions
between algorithms, we prove a `Free Leftovers' theorem for
comparative performance of algorithms over permutation functions
(holding for single and multiobjective problems); 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.