TY - GEN
T1 - Continuous lunches are free!
AU - Auger, Anne
AU - Teytaud, Olivier
PY - 2007/8/27
Y1 - 2007/8/27
N2 - This paper investigates extensions of No Free Lunch (NFL) theorems to countably infinite and uncountable infinite domains. The original NFLdue 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 measurability 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 distributions of fitness leading to equal performance forall search heuristics. Our main result is that for continuous domains, NFL does not hold.
AB - This paper investigates extensions of No Free Lunch (NFL) theorems to countably infinite and uncountable infinite domains. The original NFLdue 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 measurability 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 distributions of fitness leading to equal performance forall search heuristics. Our main result is that for continuous domains, NFL does not hold.
KW - Free-lunch
KW - Kolmogorov's extension theorem
KW - No-free-lunch
UR - https://www.scopus.com/pages/publications/34548087350
U2 - 10.1145/1276958.1277145
DO - 10.1145/1276958.1277145
M3 - Conference contribution
AN - SCOPUS:34548087350
SN - 1595936971
SN - 9781595936974
T3 - Proceedings of GECCO 2007: Genetic and Evolutionary Computation Conference
SP - 916
EP - 922
BT - Proceedings of GECCO 2007
T2 - 9th Annual Genetic and Evolutionary Computation Conference, GECCO 2007
Y2 - 7 July 2007 through 11 July 2007
ER -