No-free-lunch theorem

From Wikipedia, the free encyclopedia

This article is about a computer science theorem. For other uses, see TANSTAAFL.

An illustration of the no-free-lunch theorem, showing the performance of a highly specialized algorithm (red) and a general-purpose one (blue). Note that both algorithms perform — on average — equally well as they are applied to different problems.

The no-free-lunch theorem (NFLT) is a theorem in the field of combinatorial optimization developed by physicists David H. Wolpert and William G. Macready. It states that:

"[...] all algorithms that search for an extremum of a cost function perform exactly the same, when averaged over all possible cost functions." (Wolpert and Macready, 1995)

Taking its name from the phrase "there ain't no such thing as a free lunch", this theorem explains why, over the set of all mathematically possible problems, each search algorithm will do on average as well as any other. This is due to the bias in each search algorithm, because sometimes the assumptions that the algorithm makes are not the correct ones.

One way to visualize the NFLT is shown in the picture to the right.

Alternatively, the theorem establishes that "a general-purpose universal optimization strategy is theoretically impossible, and the only way one strategy can outperform another is if it is specialized to the specific problem under consideration" (Ho and Pepyne, 2002). That paper also contains a much simplified proof of the NFLT accessible to most engineers. See also Y.C. Ho, Q.C. Zhao, and D. Pepyne, "The No Free Lunch Theorem, Complexity and Computer Security" IEEE TRansaction on Automatic Control, v.48, #5, 783-793 May 2003, and Y.C. Ho and D. Pepyne, "Conceptual Framework for Optimization and Distributed Intelligence" Proceeding of IEEE Conference on Decision and Control Dec. 2004.

The theorem is used as an argument against generic searching algorithms such as genetic algorithms and simulated annealing when employed using as little domain knowledge as possible. It has also been applied to other generic algorithms, though in general arbitrarily large subsets of "real-world" problems can be constructed which are not covered under NFLT. Although mathematically sound, the fact that NFLT cannot be applied to arbitrary subsets of cost functions limits its applicability in practice.

For practising engineers and other optimization professionals, the theorem justifies the view that as much prior domain knowledge should be utilized as possible, and custom optimization routines constructed for particular domains. It may be thought of as a full employment theorem for optimization professionals.

The no free lunch theorems have been used (most in the scientific community say misused) in some of the critiques of evolution offered by intelligent design proponents, such as William A. Dembski in his book No Free Lunch: Why Specified Complexity Cannot be Purchased Without Intelligence. David Wolpert has said that Dembski misapplies the NFLT, characterizing Dembski's treatment of the NFLT as "written in jello" ([1]).

[edit] Bibliography

Most of these references can be obtained from http://www.no-free-lunch.org.

Wolpert, D.H., Macready, W.G. (1995), No Free Lunch Theorems for Search, Technical Report SFI-TR-95-02-010 (Santa Fe Institute).
Wolpert, D.H., Macready, W.G. (1997), No Free Lunch Theorems for Optimization, IEEE Transactions on Evolutionary Computation 1, 67.
Ho, Y.C., Pepyne, D.L. (2002), Simple Explanation of the No-Free-Lunch Theorem and Its Implications, Journal of Optimization Theory and Applications 115, 549.