zbMATH — the first resource for mathematics

Two broad classes of functions for which a no free lunch result does not hold. (English) Zbl 1038.68880
Cantú-Paz, Erick (ed.) et al., Genetic and evolutionary computation – GECCO 2003. Genetic and evolutionary computation conference, Chicago, IL, USA, July 12–16, 2003. Proceedings, Part II. Berlin: Springer (ISBN 3-540-40603-4/pbk). Lect. Notes Comput. Sci. 2724, 1418-1430 (2003).
Summary: 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.
For the entire collection see [Zbl 1025.68695].

68U99 Computing methodologies and applications
68T05 Learning and adaptive systems in artificial intelligence
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: Link