 |
    |
Two Broad Classes of Functions for Which a No Free Lunch Result Does Not Hold
Matthew J. Streeter
Genetic Programming, Inc.
Mountain View, California
mjs@tmolp.com
Abstract. We identify classes of functions for which a No Free Lunch result does and does not hold, with particular emphasis on the relationship between No Free Lunch and problem description length. We show that a NFL result does not apply to a set of functions when the description length of the functions is sufficiently bounded. We consider sets of functions with non-uniform associated probability distributions, and show that a NFL result does not hold if the probabilities are assigned according either to description length or to a Solomonoff-Levin distribution. We close with a discussion of the conditions under which NFL can apply to sets containing an infinite number of functions.
LNCS 2724, p. 1418 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003