No Free Lunch Theorems: Limitations and Perspectives of Metaheuristics

[...] Thus not only our reason fails us in the discovery of the ultimate connexion of causes and effects, but even after experience has informed us of their constant conjunction, it is impossible for us to satisfy ourselves by our reason, why we should extend that experience beyond those particular instances, which have fallen under our observation. We suppose, but are never able to prove, that there must be a resemblance betwixt those objects, of which we have had experience, and those which lie beyond the reach of our discovery. (David Hume, 1739 [14, 10]) Abstract The No Free Lunch (NFL) theorems for search and optimization are re-viewed and their implications for the design of metaheuristics are discussed. The theorems state that any two search or optimization algorithms are equivalent when their performance is averaged across all possible problems and even over subsets of problems fulfilling certain constraints. The NFL results show that if there is no assumption regarding the relation between visited and unseen search points, effi-cient search and optimization is impossible. There is no well performing universal metaheuristic, but the heuristics must be tailored to the problem class at hand us-ing prior knowledge. In practice, it is not likely that the preconditions of the NFL theorems are fulfilled for a problem class and thus differences between algorithms exist. Therefore, tailored algorithms can exploit structure underlying the optimiza-tion problem. Given full knowledge about the problem class, it is in theory possible to construct an optimal algorithm.