No free lunch theorems for search
Inhaltsverzeichnis
Reference
Wolpert, D.H., Macready, W.G. (1995). No free lunch theorems for search. SFI-TR-95-02-010 Santa Fe Institute 1995
DOI
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 information-theoretic aspects. This analysis allows us to derive mathematical benchmarks for assessing a particular search algo- rithm's 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 time-varying cost functions. We conclude with som
Extended Abstract
Bibtex
Used References
1] M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman (1979).
2] E.L. Lawler, D.E. Wood, Operations Research, 14(4), 699-719, (1966).
3] J. Pearl, Heuristics, intelligent search strategies for computer problem solv- ing, Addison-Wesley, (1984).
4] S. Kirkpatrick, C. D. Gelatt Jr., M. P. Vecchi, Science, 220, 671, (1983).
5] J. Holland, Adaptation in Natural and Arti cial Systems, University of Michigan Press, Ann Arbor, (1975).
6] L. Ingber, Adaptive Simulated Annealing, Software package documenta- tion, ftp.caltech.edu:/pub/ingber/asa.Z.
7] D. Yuret, M. de la Maza, Dynamic Hill-Climbing: Overcoming the limi- tations of optimization techniques in The Second Turkish Symposium on Arti cial Intelligence and Neural Networks, pp208-212, (1993).
8] C.E.M. Strauss, D.H. Wolpert, D.R. Wolf. Alpha, Evidence, and the Entropic Prior in Maximum Entropy and Bayesian Methods, ed. Ali Mohammed-Djafari, pp113-120, (1992).
9] T. Cover, J. Thomas, Elements of Information Theory, John Wiley & Sons, (1991).
10] D H. Wolpert, O -training set error and a priori distinctions between learning algorithms, Technical Report SFI-TR-95-01-003, Santa Fe Insti- tute, 1995.
11] D H. Wolpert, On Over tting Avoidance as Bias, Technical Report SFI- TR-92-03-5001, Santa Fe Institute, 1992.
12] Gerhard Reinelt, The Traveling Salesman, computational solutions for TSP applications, Springer Verlag Berlin Heidelberg (1994).
13] P.F. Stadler, Europhys. Lett. 20, pp479-482, (1992).
Links
Full Text
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.5447&rep=rep1&type=pdf
Sonstige Links
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.5447&rank=1
