Quelltext der Seite No free lunch theorems for search



== 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

[[intern file]]

=== Sonstige Links ===
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.5447&rank=1