We use simple adversary arguments to redevelop and explore some of the no free lunch (NFL) theorems and perhaps extend them a little. A second goal is to clarify the relationship of NFL theorems to algorithm theory. In particular we claim that NFL puts much weaker restrictions on the claims that an evolutionary algorithm can make than does acceptance of the conjectures of traditional complexity theory. And third we take a brief look at whether the notion of natural evolution relates to optimization, and what if any the implications of evolution are for computing. In this part, we mostly try to raise questions concerning the validity of applying the genetic model to the problem of optimization.
This is an informal paper --- most of the information presented is not formally proven, and is either ``common knowledge'' or formally proven elsewhere. Some of the claims are intuitions based on experience with algorithms, and in a more formal setting should be classified as conjectures. The goal is not so much to develop theory, as it is to perhaps persuade the reader to adopt a particular viewpoint.
Paper available here in postscript.
It can also be retrieved via anonymous ftp ftp://ftp.cs.ualberta.ca/pub/TechReports/1996/TR96-18/
Up to Landscapes and GAs