在理论计算机科学和计算复杂性理论中，没有免费的午餐定理(No Free Lunch Theorem, NFL定理)指出，对于基于迭代的最优化算法，不存在某种算法对有限的搜索空间内所有的问题都有效[1]。这意味着，如果某个算法对某些问题的解决好于纯随机的算法，那么必然存在一个问题，使得这个算法的表现不如纯随机的算法。
NFL定理意味着，不能脱离具体问题来谈论算法的优劣。
描述
NFL定理的研究对象是一类通过在可能解集合中搜索并找出最优解的一类算法。例如，对于拟合问题，可能解是因变量的理论取值范围，而评价解的优劣性的方式是考察算法给出值与真实值的差异。不同的算法会给出不同优劣性的解，但是按照提出者 Wolpert 原始论文中的解释，这些算法在所有问题上平均来看都是等价的[2][3]。
理解
对此定理的一种解释是，不可能创造一个广泛适用的优化策略。一个有效的优化策略必须是针对某个具体的、细分的问题的[4]。然而，许多哲学家和数学家质疑这种理解。例如，T.M.English 认为，理论意义上存在一个“几乎”适用于全部问题的优化算法，而对大多数用户来说，不同搜索算法之间的差异是可以忽略的[5]。
参考资料
- ↑ 邱锡鹏. 神经网络与深度学习. 机械工业出版社. : 50. ISBN 978-7-111-64968-7.
- ↑ Wolpert, D. H.; Macready, W. G. No Free Lunch Theorems for Search. Technical Report SFI-TR-95-02-010 (Santa Fe Institute). 1995. S2CID 12890367.
- ↑ Wolpert, D. H.; Macready, W. G. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation. 1997, 1: 67–82. CiteSeerX 10.1.1.138.6606
. S2CID 5553697. doi:10.1109/4235.585893.
- ↑ Ho, Y. C.; Pepyne, D. L. Simple Explanation of the No-Free-Lunch Theorem and Its Implications. Journal of Optimization Theory and Applications. 2002, 115 (3): 549–570. S2CID 123041865. doi:10.1023/A:1021251113462.
- ↑ English, T. M. Optimization is easy and learning is hard in the typical function. Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512) 2. 2000: 924–931. ISBN 0-7803-6375-2. S2CID 11295575. doi:10.1109/CEC.2000.870741.