No-free-lunch theorem
- This article or section should be merged with No-Free-Lunch theorems.
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) in the field of combinatorial optimization states that (Wolpert and Macready, 1995):
- "[...] all algorithms that search for an extremum of a cost function perform exactly the same, when averaged over all possible cost functions."
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).
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.
Categories: Articles to be merged | Mathematics stubs | Optimization | Theorems