This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Koehler, G. J. Search for Related Content

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

Department of Decision and Information Sciences, 351 Stuzin Hall, The Warrington College of Business Administration, University of Florida, Gainesville, Florida 32611, USA
koehler{at}ufl.edu

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.

Key words: blackbox search; no free lunch
revised February 2005; accepted November 2005.