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:
“There must be a profound recognition that parents are the first teachers and that education begins before formal schooling and is deeply rooted in the values, traditions, and norms of family and culture.”
—Sara Lawrence Lightfoot (20th century)