No Free Lunch Results Hold

Title: No Free Lunch Results Hold

Abstract: This research article explores the implications of No Free Lunch (NFL) results, which state that all search algorithms have the same average performance on all possible objective functions. The authors focus on subsets of functions that are closed under permutation, a property that allows for the application of NFL results. They prove that the number of these subsets is negligible compared to the overall number of possible subsets, and they argue that real-world problem classes are unlikely to be closed under permutation. This work provides encouraging results for the applicability of NFL theorems in practical scenarios.

Main Research Question: How many subsets of functions are closed under permutation, and what are the implications of this for the applicability of No Free Lunch results?

Methodology: The authors begin by defining basic terms and restating the sharpened NFL theorem from a previous study. They then derive the number of subsets closed under permutation and provide a proof for their calculation. Finally, they discuss the implications of their findings for structured search spaces and closure under permutation.

Results: The authors prove that the fraction of non-empty subsets that are closed under permutation is so small that it can be neglected. They also argue that real-world problem classes are unlikely to be closed under permutation.

Implications: The results of this study have important implications for the applicability of No Free Lunch results in practical scenarios. The fact that the number of subsets closed under permutation is negligible means that NFL results can be applied to a wide range of problem classes. Furthermore, the argument that real-world problem classes are unlikely to be closed under permutation suggests that NFL results are even more broadly applicable.

Link to Article: https://arxiv.org/abs/0108011v1 Authors: arXiv ID: 0108011v1