No free lunch theorems for search: Unterschied zwischen den Versionen
(Die Seite wurde neu angelegt: „ == Reference == Wolpert, D.H., Macready, W.G. (1997). No free lunch theorems for search. IEEE Transactions on Evolutionary Computation, 1(1): 67–82. == D…“) |
|||
Zeile 2: | Zeile 2: | ||
== Reference == | == Reference == | ||
− | Wolpert, D.H., Macready, W.G. ( | + | Wolpert, D.H., Macready, W.G. (1995). No free lunch theorems for search. SFI-TR-95-02-010 Santa Fe Institute 1995 |
== DOI == | == DOI == | ||
− | + | ||
== Abstract == | == 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 == | == Extended Abstract == | ||
Zeile 15: | Zeile 26: | ||
== Used References == | == 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). | ||
− | E. | + | 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). | ||
− | D | + | 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. | ||
− | D | + | 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 == | == Links == | ||
=== Full Text === | === Full Text === | ||
− | + | http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.5447&rep=rep1&type=pdf | |
[[intern file]] | [[intern file]] | ||
=== Sonstige Links === | === Sonstige Links === | ||
− | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1. | + | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.5447&rank=1 |
− | |||
− |
Aktuelle Version vom 14. November 2014, 18:33 Uhr
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