Q&A roundup: No Free Lunch
I've been receiving a bunch of email over the last couple of weeks with similar questions about my critique of Dembski's "no free lunch". Rather than answering the emails individually, I've been gathering them up, and I'll try to answer the questions here.
- What does "averaged over all landscapes" mean?
In a NFL setting, we're talking about doing something like a search over a landscape, where we have "fitness functions" which provide the search algorithm with its directions: the search moves in the direction that the fitness function tells it to.
One of the properties of the fitness functions is that they don't get to see the real landscape: their job is to try to approximate the landscape in a good way, so the search will wind up at a good destination.
When we average over all landscapes - what that means is that instead of considering how a particular fitness function matches a particular landscape, we're saying "Let's look at every possible landscape, and run the fitness function, and see what kind of results it gets".
NFL says that if we do that, that no matter how carefully we design the fitness function, it can't possibly do better than random for all landscapes. What this means is that if we don't know which landscape we're going to be confronted with, we can't pick a fitness function that's guaranteed to do well. This is interesting, for example, when applied to things like financial derivatives markets: if we don't have information about what the markets are going to do, then on average, we can't beat the market.
- NFL works for operations research tasks; why doesn't it work for evolution?
Receiving multiple emails with this question surprised the heck out of me. It's an odd question, one which is both deep and shallow at the same time. I suspect that someone somewhere put folks up to asking this one as a response to my argument, but I have no proof of that. Anyway - on to the answer:
One of the key properties of NFL is that it uses blind fitness functions. That is, the fitness function doesn't get to change itself depending on what landscape you're running it on. The fitness function in NFL is also deterministic: for any point in the landscape, looking at where it can go next, it can only choose one path as the best.
Evolution is an adaptational process: modelled as a function, it's more like the learning functions in Case's computational learning theory than like the fitness functions in NFL; an evolutionary process doesn't have a fixed path built in to it; it doesn't even have a real fitness function built in to it. In effect, an evolutionary process is modifying its fitness function as it goes. The landscape that it traverses gets built into the function, so that the longer it runs, the more adapted to the landscape it gets.
Evolution is also not deterministic: it tries multiple paths. Remember that evolution is working on a species, not on individuals. Within a species, multiple adaptations can occur in different sub-populations. That is effectively trying multiple paths. In fact, that's exactly how speciation occurs: different subpopulations adapt to the environment in different ways.
- NFL is a probability argument; why do you keep babbling about landscapes?
There are a lot of different ways that you can describe NFL-type problems; landscapes is the one I think is intuitively easiest. The idea of things like NFL is to look at a state-space with transitions, and see how algorithms can perform in different state spaces. You can describe that as a probability space, a landscape, a weighted graph, a state table, or any number of other things. The "probability" piece comes from comparing the fitness function (or fitness landscape, or whatever abstraction you choose) with the landscape it's supposed to by trying to fit. By doing that comparison, you can find the probability of a given type of fitness function performing well on a given type of landscape.
- NFL doesn't say evolution can't do better than randomness; it says that evolution must have some knowledge of the landscape to do better than randomness. Where does evolution get that knowledge?
As I said above, NFL relies on deterministic, fixed fitness functions for searching landscapes. Evolution is effectively non-deterministic, because it tries multiple paths; the successful paths persist and keep going; the unsuccessful ones die out.
Non-determinism is a big deal. The ability to try multiple paths and keep the ones that work is an incredibly powerful notion - and that's exactly where evolution gets its ability to adapt and perform well in any fitness landscape. Mathematically, you can't model evolution as a fixed deterministic function; it's an adaptive non-deterministic one. And an adaptive non-deterministic algorithm will not fall into the NFL trap. (See the Case citation above for some great work about what non-deterministic adaptive functions can do.)