Generalization of the No-Free-Lunch Theorem

Abstract — The No-Free-Lunch (NFL) Theorem provides a fundamental limit governing all optimization/search algorithms and has successfully drawn attention to theoretical foundation of optimization and search. However, we find several limitations in the original NFL paper. In this work, using results from the nature of search algorithms, we enhance several aspects of the original NFL Theorem. We have identified the properties of deterministic and probabilistic algorithms. We also provide an enumeration proof of the theorem. In addition, we show that the NFL Theorem is still valid for more general performance measures. This work serves as an application of the nature of search algorithms