Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Mathematical Analysis of Nature-Inspired Algorithms Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

A Review of No Free Lunch Theorems, and Their Implications for Metaheuristic Optimisation

verfasst von : Thomas Joyce, J. Michael Herrmann

Erschienen in: Nature-Inspired Algorithms and Applied Optimization

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The No Free Lunch Theorem states that, averaged over all optimisation problems, all non-resampling optimisation algorithms perform equally well. In order to explain the relevance of these theorems for metaheuristic optimisation, we present a detailed discussion on the No Free Lunch Theorem, and various extensions including some which have not appeared in the literature so far. We then show that understanding the No Free Lunch theorems brings us to a position where we can ask about the specific dynamics of an optimisation algorithm, and how those dynamics relate to the properties of optimisation problems.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Mathematical Analysis of Nature-Inspired Algorithms
Nächstes Kapitel Global Convergence Analysis of Cuckoo Search Using Markov Theory
Literatur
1.
Wolpert, D.H., Macready, W.G.: No free lunch theorems for search. Technical report. SFI-TR-95-02-010, Santa Fe Institute (1995)
2.
Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. In: IEEE Trans. Evol. Comput. 1.1, 67–82 (1997)
3.
Whitley, D., Rowe, J.: Focused no free lunch theorems. In: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, pp. 811–818. ACM (2008)
4.
Whitley, D.: Functions as permutations: regarding no free lunch, walsh analysis and summary statistics. In: Parallel Problem Solving from Nature PPSN VI, pp. 169–178. Springer (2000)
5.
Culberson, J.C.: On the futility of blind search: an algorithmic view of ’no free lunch. Evol. Comput. 6(2), 109–127 (1998)CrossRef
6.
Lattimore, T., Hutter, M.: No free lunch versus Occam’s razor in supervised learning. In: Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence, pp. 223–235. Springer (2013)
7.
Serafino, L.: No Free Lunch Theorem and Bayesian probability theory: two sides of the same coin. Some implications for black-box optimization and metaheuristics. In: (2013). arXiv:​1311.​6041
8.
English, T.: No more lunch: analysis of sequential search. In: Proceedings of the 2004 Congress on Evolutionary Computation CEC2004, Vol. 1, pp. 227–234. IEEE (2004)
9.
English, T.: Optimization is easy and learning is hard in the typical function. In: Proceedings of the 2000 Congress on Evolutionary Computation, vol. 2, pp. 924–931. IEEE (2000)
10.
English, T.: On the structure of sequential search: beyond ’no free lunch’. In: Evolutionary Computation in Combinatorial Optimization, pp. 95–103. Springer (2004)
11.
Ho, Yu-Chi, Pepyne, D.L.: Simple explanation of the no-free-lunch theorem and its implications. J. Optim. Theory Appl. 115(3), 549–570 (2002)MathSciNetCrossRefMATH
12.
Duéñez-Guzmán, E.A., Vose, M.D.: No free lunch and benchmarks. Evol. Comput. 21(2), 293–312 (2013)CrossRef
13.
Radcliffe, N.J., Surry, P.D.: Fundamental limitations on search algorithms: evolutionary computing in perspective. In: Computer Science Today, pp. 275–291. Springer (1995)
14.
Schumacher, C., Vose, M.D., Whitley, L.D.: The no free lunch and problem description length. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pp. 565–570 (2001)
15.
Igel, C., Toussaint, M.: A no-free-lunch theorem for non-uniform distributions of target functions. J. Math. Model. Algorithm. 3(4), 313–322 (2005)MathSciNetCrossRefMATH
16.
Droste, S., Thomas, J., Ingo, W.: Optimization with randomized search heuristics—the (A) NFL theorem, realistic scenarios, and difficult functions. Theor. Comput. Sci. 287(1), 131–144 (2002)MathSciNetCrossRefMATH
17.
Griffiths, E.J., Orponen, P.: Optimization, block designs and no free lunch theorems. Inf. Process. Lett. 94(2), 55–61 (2005)MathSciNetCrossRefMATH
18.
Corne, D.W., Knowles, J.D.: No free lunch and free leftovers theorems for multiobjective optimisation problems. In: Evolutionary Multi- Criterion Optimization. Springer (2003)
19.
Service, T.C.: A no free Lunch theorem for multi-objective optimization. Inf. Process. Lett. 110(21), 917–923 (2010)MathSciNetCrossRef
20.
Corne, D., Knowles, J.: Some multiobjective optimizers are better than others. In: The 2003 Congress on Evolutionary Computation, Vol. 4, pp. 2506–2512. IEEE (2003)
21.
Everitt, T.: Universal indution and optimisation: no free lunch? In: Thesis (2013)
22.
Auger, A., Teytaud, O.: Continuous lunches are free plus the design of optimal optimization algorithms. Algorithmica 57(1), 121–146 (2010)MathSciNetCrossRefMATH
23.
Rowe, J., Vose, M., Wright, A.: Reinterpreting no free lunch. Evol. Comput. 17(1), 117–129 (2009)CrossRef
24.
25.
Yang, X.-S.: Free lunch or no free lunch: that is not just a question? Int. J. Artif. Intell. Tools 21(03), 1240010 (2012)CrossRef
26.
Yang, X.-S., Deb, S.: Cuckoo search via Lévy flights. In: World Congress on Nature & Biologically Inspired Computing, pp. 210–214. IEEE (2009)
27.
Kennedy, J.: Particle swarm optimization. In: Encyclopedia of Machine Learning, pp. 760–766. Springer (2011)
28.
Poli, R.: Mean and variance of the sampling distribution of particle swarm optimizers during stagnation. IEEE Trans. Evol. Comput. 13(4), 712–721 (2009)CrossRef
29.
Erskine, A., Joyce, T., Herrmann, J.M.: Parameter selection in particle Swarm optimisation from stochastic stability analysis. In: International Conference on Swarm Intelligence, pp. 161–172. Springer (2016)
30.
Serafino, L.: Optimizing without derivatives: what does the no free lunch theorem actually say? In: Notices of the AMS 61.7 (2014)
31.
Ben-David, S., Srebro, N., Urner, R.: Universal learning versus no free lunch results. In: Philosophy and Machine Learning Workshop NIPS (2011)
32.
David, J.C.M.: Information theory, inference and learning algorithms. Cambridge University Press (2003)
33.
Streeter, M.J.: Two broad classes of functions for which a no free lunch result does not hold. In: Genetic and Evolutionary Computation-GECCO, pp. 1418–1430 Springer (2003)
Metadaten
Titel
A Review of No Free Lunch Theorems, and Their Implications for Metaheuristic Optimisation
verfasst von
Thomas Joyce
J. Michael Herrmann
Copyright-Jahr
2018
Buch
Nature-Inspired Algorithms and Applied Optimization

Print ISBN: 978-3-319-67668-5

Electronic ISBN: 978-3-319-67669-2

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-67669-2_2