Evaluation of Evolutionary and Genetic Optimizers: No Free Lunch.
Thomas M. English · Evolutionary Programming · 1996
The recent “no free lunch” theorems of Wolpert and Macready indicate the need to reassess empirical methods for evaluation of evolutionary and genetic optimizers. Their main theorem states, loosely, that the average performance of all optimizers is identical if the distribution of functions is average. The present work generalizes the result to an uncountable set of distributions. The focus is upon the conservation of information as an optimizer evaluates points. It is shown that the information an optimizer gains about unobserved values is ultimately due to its prior information of value distributions. Inasmuch as information about one distribution is misinformation about another, there is no generally superior function optimizer. Empirical studies are best regarded as attempts to infer the prior information optimizers have about distributions–i.e., to determine which tools are good for which tasks.