IDEAS home Printed from https://ideas.repec.org/p/wop/safiwp/95-02-010.html
   My bibliography  Save this paper

No Free Lunch Theorems for Search

Author

Listed:
  • David H. Wolpert
  • William G. Macready

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 algorithm'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 some discussion of the justifiablility of biologically-inspired search methods.

Suggested Citation

  • David H. Wolpert & William G. Macready, 1995. "No Free Lunch Theorems for Search," Working Papers 95-02-010, Santa Fe Institute.
    • Handle: RePEc:wop:safiwp:95-02-010
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    References listed on IDEAS

    as
    1. L. Ingber, 1993. "Adaptive Simulated Annealing (ASA)," Lester Ingber Software asa, Lester Ingber.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Preminger, Arie & Franck, Raphael, 2007. "Forecasting exchange rates: A robust regression approach," International Journal of Forecasting, Elsevier, vol. 23(1), pages 71-84.
    2. L. Ingber & P.L. Nunez, 1995. "Statistical mechanics of neocortical interactions: High resolution path-integral calculation of short-term memory," Lester Ingber Papers 95ni, Lester Ingber.
    3. L. Ingber & J.K. Wilson, 1999. "Volatility of volatility of financial markets," Lester Ingber Papers 99vv, Lester Ingber.
    4. L. Ingber, 1994. "Statistical mechanics of neocortical interactions: Path-integral evolution of short-term memory," Lester Ingber Papers 94ni, Lester Ingber.
    5. Ingber, Lester, 2000. "High-resolution path-integral development of financial options," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 283(3), pages 529-558.
    6. L. Ingber, 2007. "Real Options for Project Schedules (ROPS)," Lester Ingber Papers 07ro, Lester Ingber.
    7. M. Bowman & L. Ingber, 1997. "Canonical momenta of nonlinear combat," Lester Ingber Papers 97cm, Lester Ingber.
    8. Lester Ingber & Radu Paul Mondescu, 2000. "Optimization of Trading Physics Models of Markets," Papers physics/0007075, arXiv.org.
    9. L. Ingber & J.K. Wilson, 2000. "Statistical mechanics of financial markets: Exponential modifications to Black-Scholes," Lester Ingber Papers 00fm, Lester Ingber.
    10. L. Ingber, 2002. "Statistical mechanics of portfolios of options," Lester Ingber Papers 02po, Lester Ingber.
    11. Patrick Minford & Zhirong Ou & Michael Wickens, 2015. "Revisiting the Great Moderation: Policy or Luck?," Open Economies Review, Springer, vol. 26(2), pages 197-223, April.
    12. L. Ingber, 1998. "Some Applications of Statistical Mechanics of Financial Markets," Lester Ingber Papers 98sa, Lester Ingber.
    13. L. Ingber & R.P. Mondescu, 2003. "Automated internet trading based on optimized physics models of markets," Lester Ingber Papers 03ai, Lester Ingber.
    14. L. Ingber, 1993. "ASA-README included with ASA code," Lester Ingber Papers 93as, Lester Ingber.
    15. L. Ingber, 1996. "Canonical momenta indicators of financial markets and neocortical EEG," Lester Ingber Papers 96cm, Lester Ingber.
    16. L. Ingber, 1995. "Statistical mechanics of neocortical interactions: Constraints on 40 Hz models of short-term memory," Lester Ingber Papers 95st, Lester Ingber.
    17. L. Ingber, 1996. "Adaptive simulated annealing (ASA): Lessons learned," Lester Ingber Papers 96as, Lester Ingber.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wop:safiwp:95-02-010. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Thomas Krichel (email available below). General contact details of provider: https://edirc.repec.org/data/epstfus.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.