Evolutionary Programming · 1996 · 65 citations · 2 references
Natural SciencesMathematicsEvolutionary TheoryMicroevolutionOptimizationEvolutionary ComputationEvolutionary OptimizationGenetic AlgorithmsEvolutionary SearchGenetic Algorithm OptimizationPopulation-based OptimizationPrior Value Of InformationUncountable Set
The recent no‑free‑lunch theorems of Wolpert and Macready show that all optimizers perform equally on average over a uniform function distribution, implying empirical studies should infer optimizers’ prior information about distributions to identify suitable tools. This study extends the no‑free‑lunch theorem to an uncountable set of function distributions. The authors analyze how optimizers conserve information while evaluating points. They demonstrate that an optimizer’s gained information about unseen values stems from its prior distribution knowledge, and because information about one distribution misleads about another, no optimizer is universally superior.
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.
2
No Free Lunch Theorems for Search
David H. Wolpert, William G. Macready · RePEc: Research Papers in Economics · 1995 · 930 citations