Session:

TUT - Tutorials

Title:

New Insights about No Free Lunch

Authors:

Darrell Whitley

Abstract:

The "No Free Lunch" theorem, now almost 10 years old, asserts that all search algorithms have the same expected behavior over all possible discrete search problems. However, No Free Lunch (NFL) also holds over finite sets of functions, some of which are compressible and some of which are not. A focused form of NFL also holds for very small finite sets of parameter optimization problems encoded using Binary and Gray Code representations. Some observations that hold when NFL is applied over all possible discrete functions are not true when NFL holds over a finite set. Variants of local search are also capable of beating random enumeration (and NFL) over large classes of problems that can be described using polynomials of bounded complexity. These results have a very real impact on how we construct, compare and evaluate search algorithms.