Recent Results on No-Free-Lunch Theorems for Optimization
<|reference_start|>Recent Results on No-Free-Lunch Theorems for Optimization: The sharpened No-Free-Lunch-theorem (NFL-theorem) states that the performance of all optimization algorithms averaged over any finite set F of functions is equal if and only if F is closed under permutation (c.u.p.) and each target function in F is equally likely. In this paper, we first summarize some consequences of this theorem, which have been proven recently: The average number of evaluations needed to find a desirable (e.g., optimal) solution can be calculated; the number of subsets c.u.p. can be neglected compared to the overall number of possible subsets; and problem classes relevant in practice are not likely to be c.u.p. Second, as the main result, the NFL-theorem is extended. Necessary and sufficient conditions for NFL-results to hold are given for arbitrary, non-uniform distributions of target functions. This yields the most general NFL-theorem for optimization presented so far.<|reference_end|>
@article{igel2003recent,
    title={Recent Results on No-Free-Lunch Theorems for Optimization},
    author={Christian Igel and Marc Toussaint},
    journal={arXiv preprint arXiv:cs/0303032},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0303032},
    primaryClass={cs.NE math.OC nlin.AO}
}