Beyond NFL: A few tentative steps

The No Free Lunch theorem (NFL) asks some serious questions to researchers interested in search processes. In an attempt to start answering these questions this paper examines the close link between local landscape structure and the performance of the genetic operators hill-climbing, mutation and uniform cross-over. Three abstract landscapes are described, each of which is based on the simple Mt. Fuji landscape. Each landscape has been constructed to have a local structure that is easy for only one of the three operators to traverse. The performance of various hybrid algorithms are also compared. It is shown that the tight coupling between operators and local structure holds even when the operators are combined. The conclusions drawn here are argued to have their equivalent in `real-world' problems. 1 No Free Lunch (NFL) The No Free Lunch theorem (Wolpert & Macready, 1995) (NFL from now on) states that all search algorithms perform equally well when performance i..