Formal Synopsis of NFL
is the set of all objective functions f:X→Y, where is a finite solution space and is a finite poset. The set of all permutations of X is J. A random variable F is distributed on . For all j in J, F o j is a random variable distributed on, with P(F o j = f) = P(F = f o j–1) for all f in .
Let a(f) denote the output of search algorithm a on input f. If a(F) and b(F) are identically distributed for all search algorithms a and b, then F has an NFL distribution. This condition holds if and only if F and F o j are identically distributed for all j in J. In other words, there is no free lunch for search algorithms if and only if the distribution of objective functions is invariant under permutation of the solution space.
The "only if" part was first published by C. Schumacher in his PhD dissertation "Black Box Search – Framework and Methods" (The University of Tennessee, Knoxville (2000)). Set-theoretic NFL theorems have recently been generalized to arbitrary cardinality and .
Read more about this topic: No Free Lunch In Search And Optimization
Famous quotes containing the word formal:
“That anger can be expressed through words and non-destructive activities; that promises are intended to be kept; that cleanliness and good eating habits are aspects of self-esteem; that compassion is an attribute to be prized—all these lessons are ones children can learn far more readily through the living example of their parents than they ever can through formal instruction.”
—Fred Rogers (20th century)