patternModerate
What is the no free lunch theorem?
Viewed 0 times
thewhatfreetheoremlunch
Problem
I've been reading about the No Free Lunch Theorem, but I can't quite understand what it is about. I've heard this theorem described elsewhere as the claim that "no general purpose universal optimiser exists". On the other hand, the Wikipedia article talks about 'candidate solutions" that are "evaluated one by one" - if we only consider algorithms of a particular form, then that is a much more limited claim.
Can anyone explain what this theorem actually claims?
Can anyone explain what this theorem actually claims?
Solution
The No Free Lunch theorem (NFL) was established to debunk claims of the form:
My optimisation strategy X is always best.
In particular, such claims arose in the area of genetic/evolutionary algorithms.
The statement is, roughly: every optimisation strategy performs badly on many problems. Therefore, there can be no always-best strategy and your claim about X is wrong.
My optimisation strategy X is always best.
In particular, such claims arose in the area of genetic/evolutionary algorithms.
The statement is, roughly: every optimisation strategy performs badly on many problems. Therefore, there can be no always-best strategy and your claim about X is wrong.
Context
StackExchange Computer Science Q#21758, answer score: 10
Revisions (0)
No revisions yet.