From ResearchID.org

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.

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.

The no free lunch theorems have been used (many in the scientific community say misused) in some of the critiques of atelic 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.^[1] David Wolpert has said that Dembski misapplies the NFLT, characterizing Dembski's treatment of it as "written in jello."[1]

References and notes

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.

External links

• Introduction to No Free Lunch by William Dembski
• Searching Large Spaces: Displacement and the No Free Lunch Regress by William Dembski
• Fitness among Competitive Agents: A Brief Note by William Dembski
• "Yin-Yang: No-Free-Lunch Theorems for Search"

Copyright

The content of this page is based on an article at Wikipedia, The Free Encyclopedia, and the original text is licensed under the GNU Free Documentation License. The text from Wikipedia is here in compliance with their terms of reuse, and the citation for the original article is as follows: Wikipedia contributors, "No-free-lunch theorem," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=No-free-lunch_theorem&oldid=98029040 (accessed January 4, 2007).