No free lunch in search and optimization

The no- free - lunch theorems (English, about Nothing is free ) are essentially two sets of computer science, which show the limitations of optimization algorithms and machine learning methods. They therefore constitute impossibility sets, as well as Gödel's incompleteness theorem in mathematics or the Arrow 's theorem in social choice theory. The name comes from the English phrase There is not no such thing as a free lunch. David Wolpert and William G. Macready they discovered in 1995.

Simplified say of them that no universally good method for solving an optimization problem or for abstracting records exist if the set of all problems or data sets is considered. If a particular strategy in a subregion better than another, it must be worse in another part of the field to be ( nothing is free). In particular, it follows that no strategy is better than guessing. In everyday life, they can not be applied generally, as the set of all possible problems in most cases is already severely limited by the laws of nature. It is thus possible, for certain problem amounts to develop strategies that are better than others.

In a stricter formulation of 2001, the no- free -lunch theorem, the optimization problem only applies to straits which are closed under permutation.

Original formulation

Wolpert and Macready published the no- free -lunch theorem for optimization problems that do not change during the search problem, like this:

If all functions are equally likely to occur, the probability of finding an arbitrary sequence of values ​​during the optimization, not the optimization algorithm -dependent.

Attempted application to evolutionary processes

William A. Dembski has no- free - lunch theorems for his controversial hypotheses of specified complexity applied to formulate his opinion, mathematical bounds on evolutionary processes. Dembski uses these barriers as an argument against the theory of evolution and for intelligent design.

This argument is, however, generally regarded as not scientifically sound. Among other objections is mainly argued that evolutionary processes can not be considered as a search for a specific predetermined from the outset optimal element within a search lot like it presuppose the no- free - lunch theorems. The Darwinian evolution is generally regarded as more of a "prevention strategy " rather than a " search strategy ", since mainly include survival and reproduction, and only those evolutionary steps can not occur, which lead to species which are not to in principle capable. The no- free - lunch theorems are therefore not applicable.

Another objection states that the theorems make a statement about the average of all possible problems. In evolutionary theory, this means averaged over all possible fitness landscapes. About the effectiveness of the process of mutation and selection for the actually occurring Fitness landscapes which theorems can not say anything. In particular, the majority of all theoretically possible fitness landscapes are completely random, while the laws of nature already imply a certain structure.

Wolpert himself rejects Dembski's remarks as non-mathematical ( written in jello ) and adds also that the fitness function of evolutionary systems as neither constant in time nor can be considered identical for all individuals. But this is an important condition for the no- free - lunch theorems and therefore also makes an application on evolutionary processes impossible. Indeed, Wolpert and Macready could prove the existence of optimal algorithms for a particular class of such co-evolutionary systems.