nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

3. Evolutionary Algorithms and Hyper-Heuristics

verfasst von : Rodrigo C. Barros, André C. P. L. F. de Carvalho, Alex A. Freitas

Erschienen in: Automatic Design of Decision-Tree Induction Algorithms

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This chapter presents the basic concepts of evolutionary algorithms (EAs) and hyper-heuristics (HHs), which are computational techniques directly explored in this book. EAs are well-known population-based metaheuristics. They have been employed in artificial intelligence over several years with the goal of providing the near-optimal solution for a problem that comprises a very large search space. A general overview of EAs is presented in Sect. 3.1. HHs, in turn, are a recently new field in the optimisation research area, in which a metaheuristic—often an EA, and this is why these related concepts are reviewed together in this chapter—is used for searching in the space of heuristics (algorithms), and not in the space of solutions, like conventional metaheuristics. The near-optimal heuristic (algorithm) provided by a HHs approach can be further employed in several distinct problems, instead of relying on a new search process for each new problem to be solved. An overview of HHs is given in Sect. 3.2.

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 Decision-Tree Induction

Nächstes Kapitel HEAD-DT: Automatic Design of Decision-Tree Algorithms

For instance, Angeline [1] argues that the lack of performance of standard GP crossover (in comparison to some types of macromutations) indicates that it is, in effect, more accurately described as a population-limited macromutation operation rather than an operation consistent with the building block hypothesis.

P.J. Angeline, Subtree crossover: building block engine or macromutation, in Second Annual Conference on Genetic Programming, pp. 9–17 (1997)

T. Back, Selective pressure in evolutionary algorithms: a characterization of selection mechanisms, in IEEE Conference on Evolutionary Computation (CEC 1994), pp. 57–62 (1994)

W. Banzhaf et al., Genetic Programming: An Introduction–On The Automatic Evolution of Computer Programs and its Applications (Morgan Kaufmann Publishers Inc., San Francisco, 1998). ISBN: 1-55860-510-XCrossRefMATH

M.P. Basgalupp et al., Lexicographic multi-objective evolutionary induction of decision trees. Int. J. Bio-Inspir. Comput. 1(1/2), 105–117 (2009)CrossRef

T. Blickle, L. Thiele, A Comparison of Selection Schemes Used in Evolutionary Algorithms (Tech. Rep Swiss Federal Institute of Technology, Lausanne, 1995)

W. Bohm, A. Geyer-Schulz, Foundations of Genetic Algorithms IV, Exact uniform initialization for genetic programming (Morgan Kaufmann, San Francisco, 1996)

E. Burke, S. Gustafson, G. Kendall, Ramped half-n-half initialisation bias in GP, in Genetic and Evolutionary Computation Conference (GECCO 2003), pp. 1800–1801 (2003)

E.K. Burke, G. Kendall, E. Soubeiga, A tabu-search hyperheuristic for timetabling and rostering. J. Heuristics 9(6), 451–470 (2003)CrossRef

E.K. Burke, S. Petrovic, R. Qu, Case-based heuristic selection for timetabling problems. J. Sched. 9(2), 115–132 (2006). ISSN: 1094–6136CrossRefMATH

10.

E.K. Burke et al., A graph-based hyper-heuristic for educational timetabling problems. Eur. J. Oper. Res. 176(1), 177–192 (2007)CrossRefMATHMathSciNet

11.

E.K. Burke et al., A survey of hyper-heuristics. Technical report Computer Science Technical Report No. NOTTCS-TR-SUB-0906241418-2747. School of Computer Science and Information Technology, University of Nottingham (2009)

12.

K. Chellapilla, Evolving computer programs without subtree crossover. IEEE Trans. Evol. Comput. 1(3), 209–216 (1997)CrossRef

13.

C. Coello, A comprehensive survey of evolutionary-based multiobjective optimization techniques. Knowl. Inf. Syst. 1(3), 129–156 (1999)

14.

C.A.C. Coello, G.B. Lamont, D.A.V. Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems, Genetic and Evolutionary Computation (Springer, New York, 2006)

15.

P.I. Cowling, G. Kendall, E. Soubeiga, A hyperheuristic approach to scheduling a sales summit, in Third International Conference on Practice and Theory of Automated Timetabling. Springer, Berlin, pp. 176–190 (2001)

16.

A.E. Eiben, J.E. Smith, Introduction to Evolutionary Computing (Springer, Berlin, 2003)CrossRefMATH

17.

H. Fisher, G.L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules, in Industrial Scheduling, ed. by J.F. Muth, G.L. Thompson (Prentice Hall, Upper Saddle River, 1963), pp. 225–251

18.

A. Frank, A. Asuncion, UCI Machine Learning Repository (2010)

19.

A.A. Freitas, Data Mining and Knowledge Discovery with Evolutionary Algorithms (Springer, New York, 2002). ISBN: 3540433317

20.

A.A. Freitas, A review of evolutionary algorithms for data mining, in Soft Computing for Knowledge Discovery and Data Mining, ed. by O. Maimon, L. Rokach (Springer, Berlin, 2008), pp. 79–111. ISBN: 978-0-387-69935-6

21.

P. Garrido, C. Castro, Stable solving of CVRPs using hyperheuristics, in Proceedings of the 11th Annual conference on Genetic and evolutionary computation. GECCO’09. Montreal, Québec, (Canada: ACM, 2009), pp. 255–262. ISBN: 978-1-60558-325-9

22.

P. Garrido, M.-C. Riff, An evolutionary hyperheuristic to solve strip-packing problems, in Proceedings of the 8th international conference on Intelligent data engineering and automated learning. IDEAL’07. Springer, Birmingham, pp. 406–415 (2007)

23.

P. Garrido, M.C. Riff, DVRP: a hard dynamic combinatorial optimisation problem tackled by an evolutionary hyper-heuristic. J. Heuristics 16(6), 795–834 (2010). ISSN: 1381–1231

24.

D.E. Goldberg, K. Deb, A comparative analysis of selection schemes used in genetic algorithms, in Foundations of Genetic Algorithms, ed. by G.J.E. Rawlins (Morgan Kaufmann, San Mateo, 1991), pp. 69–93

25.

J.H. Holland, Adaptation in Natural and Artificial Systems (MIT Press, Cambridge, 1975)

26.

J.R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection (MIT Press, Cambridge, 1992). ISBN: 0-262-11170-5

27.

S. Luke, Two fast tree-creation algorithms for genetic programming. IEEE Trans. Evol. Comput. 4(3), 274–283 (2000)CrossRef

28.

H. Majeed, C. Ryan, Using context-aware crossover to improve the performance of GP, in 8th Annual Conference on Genetic and Evolutionary Computation (GECCO’06). ACM, pp. 847–854 (2006)

29.

H. Majeed, C. Ryan, A less destructive, context-aware crossover operator for GP, in Lecture Notes in Computer Science, ed. by P. Collet, et al. (Springer, Berlin, 2006), pp. 36–48

30.

J.G. Marín-Blázquez, S. Schulenburg, A hyper-heuristic framework with XCS: learning to create novel problem-solving algorithms constructed from simpler algorithmic ingredients, in Proceedings of the 2003–2005 International Conference on Learning Classifier Systems. IWLCS’03-05. (Berlin: Springer, 2007), pp. 193–218. ISBN: 978-3-540-71230-5

31.

M. Mitchell, An Introduction to Genetic Algorithms (MIT Press, Cambridge, 1998). ISBN: 0262631857

32.

G. Ochoa et al., Dispatching rules for production scheduling: A hyper-heuristic landscape analysis, in IEEE Congr. Evol. Comput. pp. 1873–1880 (2009)

33.

G. Ochoa, R. Qu, E.K. Burke. Analyzing the landscape of a graph based hyper-heuristic for timetabling problems, in Proceedings of the 11th Annual conference on Genetic and Evolutionary Computation. GECCO’09. Montreal, Québec, (Canada: ACM, 2009), pp. 341–348. ISBN: 978-1-60558-325-9

34.

M. Oltean, Evolving evolutionary algorithms using linear genetic programming. Evol. Comput. 13(3), 387–410 (2005)CrossRef

35.

E. Özcan, B. Bilgin, E.E. Korkmaz, A comprehensive analysis of hyper-heuristics. Intell. Data Anal. 12(1), 3–23 (2008)

36.

G.L. Pappa, A.A. Freitas, Automating the Design of Data Mining Algorithms: An Evolutionary Computation Approach (Springer Publishing Company Incorporated, New York, 2009)

37.

N. Pillay, An analysis of representations for hyper-heuristics for the uncapacitated examination timetabling problem in a genetic programming system, in Proceedings of the 2008 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists on IT Research in Developing Countries: Riding the Wave of Technology. SAICSIT’08. Wilderness, (South Africa: ACM, 2008), pp. 188–192. ISBN: 978-1-60558-286-3

38.

K.O. Stanley, R. Miikkulainen, Evolving neural networks through augmenting topologies. Evol. Comput. 10(2), 99–127 (2002). ISSN: 1063–6560CrossRef

39.

R.H. Storer, S.D. Wu, R. Vaccari, New search spaces for sequencing problems with application to job shop scheduling. Manag. Sci. 38(10), 1495–1509 (1992)CrossRefMATH

40.

H. Terashima-Marín et al., Generalized hyper-heuristics for solving 2D regular and irregular packing problems. Ann. Oper. Res. 179(1), 369–392 (2010)CrossRefMATHMathSciNet

41.

N. Uy et al., in Lecture Notes in Computer Science, Semantic similarity based crossover in GP: The case for real-valued function regression, ed. by P. Collet, et al. (Springer, Berlin, 2010), pp. 170–181

42.

J.A. Vázquez-Rodríguez, S. Petrovic, A new dispatching rule based genetic algorithm for the multi-objective job shop problem. J. Heuristics 16(6), 771–793 (2010)CrossRefMATH

43.

A. Vella, D. Corne, C. Murphy, Hyper-heuristic decision tree induction, in World Congress on Nature and Biologically Inspired Computing, pp. 409–414 (2010)

44.

T. Weise, Global Optimization Algorithms—Theory and Application. en. Second. Online available at http://www.it-weise.de/. Accessed in Sept 2009. Self-Published, (2009)

45.

J.R. Woodward, GA or GP? That is not the question, in IEEE Congress on Evol. Comput. (CEC 2003). pp. 1056–1063 (2003)

Titel: Evolutionary Algorithms and Hyper-Heuristics
verfasst von: Rodrigo C. Barros
André C. P. L. F. de Carvalho
Alex A. Freitas
Verlag: Springer International Publishing
Buch: Automatic Design of Decision-Tree Induction Algorithms
Print ISBN: 978-3-319-14230-2

Electronic ISBN: 978-3-319-14231-9

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-14231-9_3

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"