Conditions that Obviate the No-Free-Lunch Theorems for Optimization

Abstract

Roughly speaking, the no-free-lunch (NFL) theorems state that any blackbox algorithm has the same average performance as random search. These results have largely been ignored by algorithm researchers. This paper looks more closely at the NFL results and focuses on their implications for combinatorial problems typically faced by many researchers and practitioners. We derive necessary conditions for the NFL results to hold based on common problem structures. Often it is simple to verify that these conditions are not present in the class of problems under investigation, thus providing a theoretical basis for ignoring the doleful implications of NFL giving justification for believing there might be a dominant algorithm for the problem class under study. We apply our results to three common classes of problems. We find that only trivial subclasses of these problems fall under the NFL implications.