On classes of functions for which no free lunch results hold

DOI10.1016/S0020-0190(03)00222-9zbMATH Open1162.68816arXivcs/0108011WikidataQ56431138 ScholiaQ56431138MaRDI QIDQ1007637FDOQ1007637

Authors: Christian Igel, Marc Toussaint 

Publication date: 23 March 2009

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions.

Cited In (9)

• 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
• On a feasible-infeasible two-population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch

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)