Cheque Please

At the end of the day No Free Lunch Theorems appear to be telling us something rather counterintuitive about search algorithms. I first encountered these ideas in an article in the New Yorker by H. Allen Orr about Intelligent Design (more on that another time).

"Consider a search for high ground on some unfamiliar, hilly terrain. You’re on foot and it’s a moonless night; you’ve got two hours to reach the highest place you can. How to proceed? One sensible search algorithm might say, “Walk uphill in the steepest possible direction; if no direction uphill is available, take a couple of steps to the left and try again.” This algorithm insures that you’re generally moving upward. Another search algorithm—a so-called blind search algorithm—might say, “Walk in a random direction.” This would sometimes take you uphill but sometimes down. Roughly, the N.F.L. theorems prove the surprising fact that, averaged over all possible terrains, no search algorithm is better than any other. "

(The proponents of intelligent design proceed as follows: natural selection is an algorithm so therefore it's no better than any other way of generating bio-chemical complexity. The reasons why this approach is misguided are explained here.)

However, when I read the analogy above I immediately suspected that Orr might have exaggerated the case against search methodologies.

At the end of the day, Google works doesn't it? I still can't say I fully understand the maths, but from these descriptions I think it can be said that the prescription applies specifically to generalised search algorithms and the ways that their performance compares to highly specialised algorithms.