×

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].

MSC:
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.)
PDF BibTeX XML Cite
Full Text: Link