On classes of functions for which no free lunch results hold

DOI10.1016/S0020-0190(03)00222-9MaRDI QIDQ1007637zbMATH OpenWikidataFDO

Authors Christian Igel, Marc Toussaint

Publication date 23 March 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0108011

zbMATH Keywords

optimizationrandomized algorithmscombinatorial problemsno free lunch

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Abstract: In a recent paper it was shown that No Free Lunch results hold for any subset F of the set of all possible functions from a finite set X to a finite set Y iff F is closed under permutation of X. In this article, we prove that the number of those subsets can be neglected compared to the overall number of possible subsets. Further, we present some arguments why problem classes relevant in practice are not likely to be closed under permutation.

Cites work

• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions.

Cited in

(9)

• On a feasible-infeasible two-population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch
• No free lunch theorems: limitations and perspectives of metaheuristics
• Practical performance models of algorithms in evolutionary program induction and other domains
• A no free lunch theorem for multi-objective optimization
• Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem
• A framework for co-optimization algorithm performance and its application to worst-case optimization
• Optimization, block designs and no free lunch theorems
• Efficient covariance matrix update for variable metric evolution strategies
• A no-free-lunch theorem for non-uniform distributions of target functions

This page was built for publication: On classes of functions for which no free lunch results hold

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1007637)