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).

The theorem is used as an argument against using generic searching algorithms such as genetic algorithms and simulated annealing without using as much domain knowledge as possible. It's 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 are sometimes used, the scientific community says misused, in the polemics offered against evolution by intelligent design proponents, such as William A. Dembski in his book No Free Lunch. Why Specified Complexity Cannot be Purchased Without Intelligence.

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

---

• "Yin-Yang: No-Free-Lunch Theorems for Search"

Optimization | Mathematical theorems

No-Free-Lunch-Theoreme | Teorema de non-existe-o-xantar-de-balde | ノーフリーランチ定理