Title: | No Free Lunch Theorems for Search |

Author: | David H. Wolpert and William G. Macready |

Institution: | Santa Fe Institute |

Year: | 1995 |

Abstract: | We show that all algorithms that search for an extremum of a cost function perform exactly the same, when averaged over all possible cost functions In particular, if algorithm A outperforms algorithm B on some cost functions then loosely speaking there must exist exactly as many other functions where B outperforms A Starting from this we analyze a number of the other a priori characteristics of the search problem, like its geometry and its informationtheoretic aspects This analysis allows us to derive mathematical benchmarks for assessing a particular search algorithms performance We also investigate minimax aspects of the search problem, the validity of using characteristics of a partial search over a cost function to predict future behavior of the search algorithm on that cost function, and timevarying cost functions We conclude with some discussion of the justiability of biologicallyinspired search methods |

Cited by 353

@TechReport{wolpert95a, author = {David H. Wolpert and William G. Macready}, title = {No Free Lunch Theorems for Search}, institution = {Santa Fe Institute}, year = 1995, abstract = {We show that all algorithms that search for an extremum of a cost function perform exactly the same, when averaged over all possible cost functions In particular, if algorithm A outperforms algorithm B on some cost functions then loosely speaking there must exist exactly as many other functions where B outperforms A Starting from this we analyze a number of the other a priori characteristics of the search problem, like its geometry and its informationtheoretic aspects This analysis allows us to derive mathematical benchmarks for assessing a particular search algorithms performance We also investigate minimax aspects of the search problem, the validity of using characteristics of a partial search over a cost function to predict future behavior of the search algorithm on that cost function, and timevarying cost functions We conclude with some discussion of the justiability of biologicallyinspired search methods}, cluster = {15851006413928005146}, url = {http://jmvidal.cse.sc.edu/library/wolpert95a.pdf} }Last modified: Wed Mar 9 10:14:04 EST 2011