Abstract
A framework is developed to explore the connection between effective optimization algorithms and the problems they are solving. 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. These theorems result in a geometric interpretation of what it means for an algorithm to be well suited to an optimization problem. Applications of the NFL theorems to information-theoretic aspects of optimization and benchmark measures of performance are also presented. Other issues addressed include time-varying optimization problems and a priori “head-to-head” minimax distinctions between optimization algorithms, distinctions that result despite the NFL theorems’ enforcing of a type of uniformity over all algorithms.
Keywords
MinimaxOptimization problemMathematical optimizationClass (philosophy)A priori and a posterioriMathematicsInterpretation (philosophy)Computer scienceL-reductionAlgorithmContinuous optimizationArtificial intelligenceMulti-swarm optimization
Affiliated Institutions
Related Publications
No Free Lunch Theorems for Search
We show that all algorithms that search for an extremum of a cost function perform exactly the same, according to any performance measure, when averaged over all possible cost f...
Direct Search Methods on Parallel Machines
This paper describes an approach to constructing derivative-free algorithms for unconstrained optimization that are easy to implement on parallel machines. A special feature of ...
Some experiments in machine learning using vector evaluated genetic algorithms (artificial intelligence, optimization, adaptation, pattern recognition)
This dissertation describes experiments conducted to explore the efficacy of using vector-valued feedback with a class of adaptive procedures called genetic algorithms. The soft...
Multidirectional search: a direct search algorithm for parallel machines
In recent years there has been a great deal of interest in the development of optimization algorithms which exploit the computational power of parallel computer architectures. W...
A fast and elitist multiobjective genetic algorithm: NSGA-II
Multi-objective evolutionary algorithms (MOEAs) that use non-dominated sorting and sharing have been criticized mainly for: (1) their O(MN/sup 3/) computational complexity (wher...
Publication Info
- Year
- 1997
- Type
- article
- Volume
- 1
- Issue
- 1
- Pages
- 67-82
- Citations
- 13304
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
13304
OpenAlex
Cite This
David H. Wolpert,
William G. Macready
(1997).
No free lunch theorems for optimization.
IEEE Transactions on Evolutionary Computation
, 1
(1)
, 67-82.
https://doi.org/10.1109/4235.585893
Identifiers
- DOI
- 10.1109/4235.585893