Continuous lunches are free!

Anne Auger 1 Olivier Teytaud 1
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : This paper investigates extensions of No Free Lunch (NFL) theorems to countably infinite and uncountable infinite do- mains. The original NFL due to Wolpert and Macready states that all search heuristics have the same performance when averaged over the uniform distribution over all possible functions. For infinite domains the extension of the concept of distribution over all possible functions involves measur- ability issues and stochastic process theory. For countably infinite domains, we prove that the natural extension of NFL theorems does not hold, but that a weaker form of NFL does hold, by stating the existence of non-trivial distribution of fitness leading to equal performance for all search heuristics. Our main result is that for continuous domains, NFL does not hold.
Type de document :
Communication dans un congrès
GECCO, 2007, London, United Kingdom. 2007
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00173209
Contributeur : Olivier Teytaud <>
Soumis le : mercredi 19 septembre 2007 - 15:40:11
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : jeudi 8 avril 2010 - 22:00:05

Fichier

cfl.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00173209, version 1

Collections

Citation

Anne Auger, Olivier Teytaud. Continuous lunches are free!. GECCO, 2007, London, United Kingdom. 2007. 〈inria-00173209〉

Partager

Métriques

Consultations de la notice

261

Téléchargements de fichiers

225