nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

On the Automatic Design of a Representation for Grammar-Based Genetic Programming

verfasst von : Eric Medvet, Alberto Bartoli

Erschienen in: Genetic Programming

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

A long-standing problem in Evolutionary Computation consists in how to choose an appropriate representation for the solutions. In this work we investigate the feasibility of synthesizing a representation automatically, for the large class of problems whose solution spaces can be defined by a context-free grammar. We propose a framework based on a form of meta-evolution in which individuals are candidate representations expressed with an ad hoc language that we have developed to this purpose. Individuals compete and evolve according to an evolutionary search aimed at optimizing such representation properties as redundancy, locality, uniformity of redundancy.

We assessed experimentally three variants of our framework on established benchmark problems and compared the resulting representations to human-designed representations commonly used (e.g., classical Grammatical Evolution). The results are promising in the sense that the evolved representations indeed exhibit better properties than the human-designed ones. Furthermore, while those improved properties do not result in a systematic improvement of search effectiveness, some of the evolved representations do improve search effectiveness over the human-designed baseline.

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 Generating Redundant Features with Unsupervised Multi-tree Genetic Programming

Nächstes Kapitel Multi-level Grammar Genetic Programming for Scheduling in Heterogeneous Networks

https://github.com/ericmedvet/evolved-ge.

Altenberg, L.: Probing the axioms of evolutionary algorithm design: commentary on “On the mapping of genotype to phenotype in evolutionary algorithms” by Peter A. Whigham, Grant Dick, and James Maclaurin. Genet. Program. Evolvable Mach. 18(3), 363–367 (2017)CrossRef

Castelli, M., Manzoni, L., Vanneschi, L., Silva, S., Popovič, A.: Self-tuning geometric semantic genetic programming. Genet. Program. Evolvable Mach. 17(1), 55–74 (2016)CrossRef

Correia, M.B.: A study of redundancy and neutrality in evolutionary optimization. Evol. Comput. 21(3), 413–443 (2013)CrossRef

Cruz-Salinas, A.F., Perdomo, J.G.: Self-adaptation of genetic operators through genetic programming techniques. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 913–920. ACM, New York (2017)

De Jong, K.: Parameter setting in EAs: a 30 year perspective. In: Lobo, F.G., Lima, C.F., Michalewicz, Z. (eds.) Parameter Setting in Evolutionary Algorithms, pp. 1–18. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-69432-8_1

Fogel, D.B., Fogel, L.J., Atmar, J.W.: Meta-evolutionary programming. In: 1991 Conference Record of the Twenty-Fifth Asilomar Conference on Signals, Systems and Computers, pp. 540–545. IEEE (1991)

Foster, J.A.: Taking “biology” just seriously enough: commentary on “On the mapping of genotype to phenotype in evolutionary algorithms” by Peter A. Whigham, Grant Dick, and James Maclaurin. Genet. Program. Evolvable Mach. 18(3), 395–398 (2017)CrossRef

Hong, L., Drake, J.H., Woodward, J.R., Özcan, E.: A hyper-heuristic approach to automated generation of mutation operators for evolutionary programming. Appl. Soft Comput. 62, 162–175 (2018)CrossRef

Lourenço, N., Pereira, F.B., Costa, E.: SGE: a structured representation for grammatical evolution. In: Bonnevay, S., Legrand, P., Monmarché, N., Lutton, E., Schoenauer, M. (eds.) EA 2015. LNCS, vol. 9554, pp. 136–148. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-31471-6_11

10.

Mckay, R.I., Hoai, N.X., Whigham, P.A., Shan, Y., O’Neill, M.: Grammar-based genetic programming: a survey. Genet. Program. Evolvable Mach. 11(3–4), 365–396 (2010)CrossRef

11.

Medvet, E.: A comparative analysis of dynamic locality and redundancy in grammatical evolution. In: McDermott, J., Castelli, M., Sekanina, L., Haasdijk, E., García-Sánchez, P. (eds.) EuroGP 2017. LNCS, vol. 10196, pp. 326–342. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55696-3_21 CrossRef

12.

Medvet, E.: Hierarchical grammatical evolution. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO (2017)

13.

Medvet, E., Bartoli, A., Squillero, G.: An effective diversity promotion mechanism in grammatical evolution. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2017, pp. 247–248. ACM, New York (2017)

14.

Medvet, E., Daolio, F., Tagliapietra, D.: Evolvability in grammatical evolution. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 977–984. ACM, New York (2017)

15.

Miller, J.F., Smith, S.L.: Redundancy and computational efficiency in Cartesian genetic programming. IEEE Trans. Evol. Comput. 10(2), 167–174 (2006)CrossRef

16.

O’Neill, M., Brabazon, A., Nicolau, M., Garraghy, S.M., Keenan, P.: \(\pi \)Grammatical evolution. In: Deb, K. (ed.) GECCO 2004. LNCS, vol. 3103, pp. 617–629. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24855-2_70 CrossRef

17.

O’Neill, M., Ryan, C.: Genetic code degeneracy: implications for grammatical evolution and beyond. In: Floreano, D., Nicoud, J.-D., Mondada, F. (eds.) ECAL 1999. LNCS (LNAI), vol. 1674, pp. 149–153. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48304-7_21 CrossRef

18.

O’Neill, M., Ryan, C.: Grammatical evolution by grammatical evolution: the evolution of grammar and genetic code. In: Keijzer, M., O’Reilly, U.-M., Lucas, S., Costa, E., Soule, T. (eds.) EuroGP 2004. LNCS, vol. 3003, pp. 138–149. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24650-3_13 CrossRef

19.

Pagie, L., Hogeweg, P.: Evolutionary consequences of coevolving targets. Evol. Comput. 5(4), 401–418 (1997)CrossRef

20.

Pappa, G.L., Ochoa, G., Hyde, M.R., Freitas, A.A., Woodward, J., Swan, J.: Contrasting meta-learning and hyper-heuristic research: the role of evolutionary algorithms. Genet. Program. Evolvable Mach. 15(1), 3–35 (2014)CrossRef

21.

Qin, A.K., Huang, V.L., Suganthan, P.N.: Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans. Evol. Comput. 13(2), 398–417 (2009)CrossRef

22.

Rothlauf, F.: Representations for genetic and evolutionary algorithms. In: Rothlauf, F. (ed.) Representations for Genetic and Evolutionary Algorithms, pp. 9–32. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-32444-5_2 CrossRef

23.

Rothlauf, F., Goldberg, D.E.: Redundant representations in evolutionary computation. Evol. Comput. 11(4), 381–415 (2003)CrossRef

24.

Ryan, C.: A rebuttal to Whigham, Dick, and Maclaurin by one of the inventors of grammatical evolution: commentary on “On the mapping of genotype to phenotype in evolutionary algorithms” by Peter A. Whigham, Grant Dick, and James Maclaurin. Genet. Program. Evolvable Mach. 18, 385–389 (2017)CrossRef

25.

Ryan, C., Collins, J.J., Neill, M.O.: Grammatical evolution: evolving programs for an arbitrary language. In: Banzhaf, W., Poli, R., Schoenauer, M., Fogarty, T.C. (eds.) EuroGP 1998. LNCS, vol. 1391, pp. 83–96. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055930 CrossRef

26.

Saravanan, N., Fogel, D.B., Nelson, K.M.: A comparison of methods for self-adaptation in evolutionary algorithms. BioSystems 36(2), 157–166 (1995)CrossRef

27.

Scott, E.O., Bassett, J.K.: Learning genetic representations for classes of real-valued optimization problems. In: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 1075–1082. ACM (2015)

28.

Simões, L.F., Izzo, D., Haasdijk, E., Eiben, A.E.: Self-adaptive genotype-phenotype maps: neural networks as a meta-representation. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 110–119. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10762-2_11

29.

Spector, L.: Introduction to the peer commentary special section on “On the mapping of genotype to phenotype in evolutionary algorithms” by Peter A. Whigham, Grant Dick, and James Maclaurin. Genet. Program. Evolvable Mach. 18(3), 351–352 (2017)CrossRef

30.

Squillero, G., Tonda, A.: (over-)realism in evolutionary computation: commentary on “On the mapping of genotype to phenotype in evolutionary algorithms” by Peter A. Whigham, Grant Dick, and James Maclaurin. Genet. Program. Evolvable Mach. 18, 391–393 (2017)CrossRef

31.

Thorhauer, A.: On the non-uniform redundancy in grammatical evolution. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 292–302. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_27 CrossRef

32.

Thorhauer, A., Rothlauf, F.: On the locality of standard search operators in grammatical evolution. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 465–475. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10762-2_46

33.

Vanneschi, L., Castelli, M., Manzoni, L.: The K landscapes: a tunably difficult benchmark for genetic programming. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, pp. 1467–1474. ACM (2011)

34.

Whigham, P.A., Dick, G., Maclaurin, J.: On the mapping of genotype to phenotype in evolutionary algorithms. Genet. Program. Evolvable Mach. 18, 353–361 (2017)CrossRef

35.

Whigham, P.A., Dick, G., Maclaurin, J., Owen, C.A.: Examining the best of both worlds of grammatical evolution. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 1111–1118. ACM (2015)

36.

Whigham, P.A., et al.: Grammatically-based genetic programming. In: Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, vol. 16, pp. 33–41 (1995)

37.

White, D.R., Mcdermott, J., Castelli, M., Manzoni, L., Goldman, B.W., Kronberger, G., Jaśkowski, W., O’Reilly, U.M., Luke, S.: Better GP benchmarks: community survey results and proposals. Genet. Program. Evolvable Mach. 14(1), 3–29 (2013)CrossRef

38.

Wong, P.-K., Wong, M.-L., Leung, K.-S.: Hierarchical knowledge in self-improving grammar-based genetic programming. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 270–280. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_25 CrossRef

Titel: On the Automatic Design of a Representation for Grammar-Based Genetic Programming
verfasst von: Eric Medvet
Alberto Bartoli
Verlag: Springer International Publishing
Buch: Genetic Programming
Print ISBN: 978-3-319-77552-4

Electronic ISBN: 978-3-319-77553-1

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-77553-1_7

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"