nach oben

Erschienen in:

2014 | OriginalPaper | Buchkapitel

1. No Free Lunch Theorems: Limitations and Perspectives of Metaheuristics

verfasst von : Christian Igel

Erschienen in: Theory and Principled Methods for the Design of Metaheuristics

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The No Free Lunch (NFL) theorems for search and optimization are reviewed and their implications for the design of metaheuristics are discussed. The theorems state that any two search or optimization algorithms are equivalent when their performance is averaged across all possible problems and even over subsets of problems fulfilling certain constraints. The NFL results show that if there is no assumption regarding the relation between visited and unseen search points, efficient search and optimization is impossible. There is no well-performing universal metaheuristic, but the heuristics must be tailored to the problem class at hand using prior knowledge. In practice, it is not likely that the preconditions of the NFL theorems are fulfilled for a problem class and thus differences between algorithms exist. Therefore, tailored algorithms can exploit structure underlying the optimization problem. Given full knowledge about the problem class, it is, in theory, possible to construct an optimal algorithm.

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

Nächstes Kapitel Convergence Rates of Evolutionary Algorithms and Parallel Evolutionary Algorithms

In general, this cannot be done in the theorems because \(\sum _{f\in F}\delta (k,\sum _{a\prime\in A}p_{a}(a\prime)c(Y (f,m,a\prime)))\neq \sum _{f\in F}\sum _{a\prime\in A}p_{a}(a\prime)\delta (k,c(Y (f,m,a\prime)))\).

It is also possible to map the optimization to an infinite horizon problem with appropriate absorbing states.

In a S-MDP no state is ever revisited. Hence, for any policy, the transition probability graph is acyclic and thus value iteration finds the optimal policy after at most m steps, where each step needs \(O{(\vert \mathcal{A}\vert \vert \mathcal{S}\vert )}^{2}\) computations (see [3, Sect. 2.2.2] or [2]).

A. Auger, O. Teytaud, Continuous lunches are free plus the design of optimal optimization algorithms. Algorithmica 57(1), 121–146 (2010)CrossRefMATHMathSciNet

D.P. Bertsekas, Dynamic programming and optimal control. Athena Sci. 2 (2007)

D.P. Bertsekas, J.N. Tsitsiklis, Neuro-dynamic programming. Athena Sci. (1996)

O. Bousquet, S. Boucheron, G. Lugosi, Introduction to statistical learning theory, in Advanced Lectures in Machine Learning, ed. by O. Bousquet, U. von Luxburg, G. Rätsch. LNAI, vol. 3176 (Springer, Berlin Heidelberg, 2004), pp. 169–207

D.W. Corne, J.D. Knowles, No free lunch and free leftovers theorems for multiobjective optimisation problems, in Evolutionary Multi-Criterion Optimization (EMO 2003), ed. by C.M. Fonseca, P.J. Fleming, E. Zitzler, L. Thiele, K. Deb. LNCS, vol. 2632 (Springer, Berlin Heidelberg, 2003), pp. 327–341

S. Droste, T. Jansen, I. Wegener, Optimization with randomized search heuristics – the (A)NFL theorem, realistic scenarios, and difficult functions. Theor. Comput. Sci. 287(1), 131–144 (2002)CrossRefMATHMathSciNet

T.M. English, Evaluation of evolutionary and genetic optimizers: no free lunch, in Proceedings of the Fifth Annual Conference on Evolutionary Programming (EP V), San Diego, ed. by L.J. Fogel, P.J. Angeline, T. Bäck (MIT, 1996), pp. 163–169

T.M. English, Optimization is easy and learning is hard in the typical function, in Proceedings of the 2000 Congress on Evolutionary Computation (CEC 2000), San Diego, ed. by A. Zalzala, C. Fonseca, J.H. Kim, A. Smith (IEEE, 2000), pp. 924–931

T. English, On the structure of sequential search: beyond “No free lunch”, in Evolutionary Computation in Combinatorial Optimization (EvoCOP 2004), ed. by J. Gottlieb, G.R. Raidl. LNCS, vol. 3004 (Springer, Berlin Heidelberg, 2004), pp. 95–103

10.

C. Giraud-Carrier, F. Provost, Toward a justification of meta-learning: is the no free lunch theorem a show-stopper? in Proceedings of the ICML-2005 Workshop on Meta-learning, Bonn, 2005

11.

N. Hansen: Invariance, self-adaptation and correlated mutations and evolution strategies, in Parallel Problem Solving from Nature (PPSN VI), ed. by M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J.J.M. Guervós, H.P. Schwefel. LNCS, vol. 1917 (Springer, Berlin Heidelberg, 2000), pp. 355–364

12.

N. Hansen, Adaptive encoding: how to render search coordinate system invariant, in Parallel Problem Solving from Nature (PPSN X), ed. by G. Rudolph, T. Jansen, S.M. Lucas, C. Poloni, N. Beume. LNCS, vol. 5199 (Springer, Berlin Heidelberg, 2008), pp. 205–214

13.

N. Hansen, A. Ostermeier, Completely derandomized self-adaptation in evolution strategies. Evol. Comput. 9(2), 159–195 (2001)CrossRef

14.

D. Hume, A Treatise of Human Nature, Chap. Sect. vi. Of the Inference from the impression to the idea. Web edition published by eBooks@Adelaide, 2006 (1739)

15.

C. Igel, Recent results on no-free-lunch for optimization, in Theory of Evolutionary Algorithms, no. 04081, ed. by H. Beyer, T. Jansen, C. Reeves, M.D. Vose, in Dagstuhl Seminar Proceedings, Abstract Collection, Schloss Dagstuhl (Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), 2004)

16.

C. Igel, P. Stagge, Graph isomorphisms effect structure optimization of neural networks, in International Joint Conference on Neural Networks (IJCNN 2002), Honolulu (IEEE, 2002), pp. 142–147

17.

C. Igel, M. Toussaint, Neutrality and self-adaptation. Nat. Comput. 2(2), 117–132 (2003)CrossRefMATHMathSciNet

18.

C. Igel, M. Toussaint, On classes of functions for which no free lunch results hold. Inf. Process. Lett. 86(6), 317–321 (2003)CrossRefMATHMathSciNet

19.

C. Igel, M. Toussaint, Recent results on no-free-lunch theorems for optimization. arXiv preprint cs.NE/0303032 (2003), http://arxiv.org/abs/cs.NE/0303032

20.

C. Igel, M. Toussaint, A no-free-lunch theorem for non-uniform distributions of target functions. J. Math. Model. Algorithms 3(4), 313–322 (2004)CrossRefMATHMathSciNet

21.

M. Köppen, D.H. Wolpert, W.G. Macready, Remarks on a recent paper on the “no free lunch” theorems. IEEE Trans. Evol. Comput. 5(3), 295–296 (1995)CrossRef

22.

R. Motwani, P. Raghavan, Randomized Algorithms (Cambridge University Press, Cambridge, 1995)CrossRefMATH

23.

J. Niehaus, C. Igel, W. Banzhaf, Reducing the number of fitness evaluations in graph genetic programming using a canonical graph indexed database. Evol. Comput. 15(2), 199–221 (2007)CrossRef

24.

N.J. Radcliffe, P.D. Surry, Fundamental limitations on search algorithms: evolutionary computing in perspective, in Computer Science Today: Recent Trends and Development, ed. by J. van Leeuwen. LNCS, vol. 1000 (Springer, Berlin Heidelberg, 1995), pp. 275–291

25.

G.J.E. Rawlins, Introduction, in Foundations of Genetic Algorithms (FOGA), ed. by G.J.E. Rawlins (Morgan Kaufmann, San Mateo, 1991), pp. 1–10

26.

J.E. Rowe, M.D. Vose, A.H. Wright, Reinterpreting no free lunch. Evol. Comput. 17(1), 117–129 (2009)CrossRef

27.

C. Schumacher, Fundamental limitations of search. Ph.D. Thesis, University of Tennessee, 2000

28.

C. Schumacher, M.D. Vose, L.D. Whitley, The no free lunch and description length, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), San Francisco, ed. by L. Spector, E. Goodman, A. Wu, W. Langdon, H.M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon, E. Burke (Morgan Kaufmann, 2001), pp. 565–570

29.

M.J. Streeter, Two broad classes of functions for which a no free lunch result does not hold, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003), Chicago, ed. by E. Cantú-Paz, J.A. Foster, K. Deb, D. Davis, R. Roy, U.M. O’Reilly, H.G. Beyer, R. Standish, G. Kendall, S. Wilson, M. Harman, J. Wegener, D. Dasgupta, M.A. Potter, A.C. Schultz, K. Dowsland, N. Jonoska, J. Miller. LNCS, vol. 2724 (Springer, Berlin Heidelberg, 2003), pp. 1418–1430

30.

T. Suttorp, N. Hansen, C. Igel, Efficient covariance matrix update for variable metric evolution strategies. Mach. Learn. 75(2), 167–197 (2009). doi:10.1007/s10994-009-5102-1CrossRef

31.

D. Whitley, A free lunch proof for Gray versus binary encodings, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999), Orlando, ed. by W. Banzhaf, J. Daida, A.E. Eiben, M.H. Garzon, V. Honavar, M. Jakiela, R.E. Smith, vol. 1 (Morgan Kaufmann, 1999), pp. 726–733

32.

D. Whitley, J. Rowe, Focused no free lunch theorems, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008), Atlanta, ed. by M. Keijzer, et al. (ACM, 2008), pp. 811–818

33.

D. Whitley, J.P. Watson, Complexity theory and the no free lunch theorem, in Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, ed. by E.K. Burke, G. Kendall, Chap. 11 (Springer, New York, 2005), pp. 317–339

34.

D.H. Wolpert, The lack of a priori distinctions between learning algorithms. Neural Comput. 8(7), 1341–1390 (1996)CrossRef

35.

D.H. Wolpert, W.G. Macready, No free lunch theorems for search. Technical Report SFI-TR-05-010, Santa Fe Institute, Santa Fe (1995)

36.

D.H. Wolpert, W.G. Macready, No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1(1), 67–82 (1997)CrossRef

37.

D.H. Wolpert, W.G. Macready, Coevolutionary free lunches. IEEE Trans. Evol. Comput. 9(6), 721–735 (2005)CrossRef

Titel: No Free Lunch Theorems: Limitations and Perspectives of Metaheuristics
verfasst von: Christian Igel
Verlag: Springer Berlin Heidelberg
Buch: Theory and Principled Methods for the Design of Metaheuristics
Print ISBN: 978-3-642-33205-0

Electronic ISBN: 978-3-642-33206-7

Copyright-Jahr: 2014
DOI: https://doi.org/10.1007/978-3-642-33206-7_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"