Ubiquity symposium: Evolutionary computation and the processes of life: what the no free lunch theorems really mean: how to improve search algorithms

UbiquityPublished 1 December 2013Open access

David H. Wolpert

Citations37

TL;DR

To round out the symposia, David Wolpert presents an overview of the no free lunch theorems and clarifies many of their incorrect interpretations, which appear to be more important for evolutionary computation theory than traditional schema theorem.

Abstract

forum Free Access Share on Ubiquity symposium: Evolutionary computation and the processes of life: what the no free lunch theorems really mean: how to improve search algorithms Author: David H. Wolpert Santa Fe Institute Santa Fe InstituteView Profile Authors Info & Claims UbiquityVolume 2013Issue DecemberDecember 2013Article No.: 2pp 1–15https://doi.org/10.1145/2555235.2555237Published:01 December 2013Publication History 24citation4,561DownloadsMetricsTotal Citations24Total Downloads4,561Last 12 Months315Last 6 weeks125 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Publisher SiteView all FormatsPDF

Keywords

Computer ScienceBiochemistry, Genetics and Molecular Biology

IEEE Transactions on Evolutionary ComputationNo free lunch theorems for optimization

13,936 Citations1997David H. Wolpert, William G. Macready

A framework is developed to explore the connection between effective optimization algorithms and the problems they are solving and a number of "no free lunch" (NFL) theorems are presented which establish that for any algorithm, any elevated performance over one class of problems is offset by performance over another class.

Neural ComputationThe Lack of A Priori Distinctions Between Learning Algorithms

1,646 Citations1996David H. Wolpert

It is shown that one cannot say: if empirical misclassification rate is low, the Vapnik-Chervonenkis dimension of your generalizer is small, and the training set is large, then with high probability your OTS error is small.

MIMIC: Finding Optima by Estimating Probability Densities

472 Citations1996Jeremy S. De Bonet, Charles L. Isbell +1 more

This work presents MIMIC, a framework in which it analyzes the global structure of the optimization landscape and uses knowledge of this structure to guide a randomized search through the solution space and, in turn, to refine the structure.

Elsevier eBooksA Conservation Law for Generalization Performance

341 Citations1994Cullen Schaffer

A proof of a basic mathematical result stating that positive performance in some learning situations must be offset by an equal degree of negative performance in others is presented.

IEEE Transactions on Evolutionary ComputationCoevolutionary Free Lunches

229 Citations2005David H. Wolpert, William G. Macready

This paper presents a general framework covering most optimization scenarios and shows that in self-play there are free lunches: in coevolution some algorithms have better performance than other algorithms, averaged across all possible problems.

Neural ComputationOn Bias Plus Variance

111 Citations1997David H. Wolpert

ComplexityWhat makes an optimization problem hand?

58 Citations1996William G. Macready, David H. Wolpert

It is shown that according to this quantitiy, there is no distinction between optimization problems, and in this sense no problems are intrinsically harder than others.

IIASA PURE (International Institute of Applied Systems Analysis)Monte Carlo Optimization and Path Dependent Nonstationary Laws of Large Numbers

15 Citations1998Y. Ermoliev, V. I. Norkin

View PDF

ArXiv.orgBias-Variance Techniques for Monte Carlo Optimization: Cross-validation for the CE Method

4 Citations2008Dev Rajnarayan, David H. Wolpert

The technique of cross-validation is used, a technique based on the bias-variance tradeoff, to significantly improve the performance of the Cross Entropy (CE) method, which is an MCO algorithm.

View PDF