nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

A Grammar Design Pattern for Arbitrary Program Synthesis Problems in Genetic Programming

verfasst von : Stefan Forstenlechner, David Fagan, Miguel Nicolau, Michael O’Neill

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

Grammar Guided Genetic Programming has been applied to many problem domains. It is well suited to tackle program synthesis, as it has the capability to evolve code in arbitrary languages. Nevertheless, grammars designed to evolve code have always been tailored to specific problems resulting in bespoke grammars, which makes them difficult to reuse. In this study a more general approach to grammar design in the program synthesis domain is presented. The approach undertaken is to create a grammar for each data type of a language and combine these grammars for the problem at hand, without having to tailor a grammar for every single problem. The approach can be applied to arbitrary problem instances of program synthesis and can be used with any programming language. The approach is also extensible to use libraries available in a given language. The grammars presented can be applied to any grammar-based Genetic Programming approach and make it easy for researches to rerun experiments or test new problems. The approach is tested on a suite of benchmark problems and compared to PushGP, as it is the only GP system that has presented results on a wide range of benchmark problems. The object of this study is to match or outperform PushGP on these problems without tuning grammars to solve each specific problem.

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 RECIPE: A Grammar-Based Framework for Automatically Evolving Classification Pipelines

Nächstes Kapitel Improving the Tartarus Problem as a Benchmark in Genetic Programming

https://github.com/t-h-e/HeuristicLab.CFGGP.

https://github.com/lspector/Clojush.

Byrne, J., Cardiff, P., Brabazon, A., O’Neill, M.: Evolving parametric aircraft models for design exploration and optimisation. Neurocomputing 142(0), 39–47 (2014). SI Computational Intelligence Techniques for New Product DevelopmentCrossRef

Byrne, J., Fenton, M., Hemberg, E., McDermott, J., O’Neill, M.: Optimising complex pylon structures with grammatical evolution. Inf. Sci. (0), (2014). http://www.sciencedirect.com/science/article/pii/S0020025514002904

Castle, T., Johnson, C.G.: Evolving high-level imperative program trees with strongly formed genetic programming. In: Moraglio, A., Silva, S., Krawiec, K., Machado, P., Cotta, C. (eds.) EuroGP 2012. LNCS, vol. 7244, pp. 1–12. Springer, Heidelberg (2012). doi:10.1007/978-3-642-29139-5_1. http://www.cs.kent.ac.uk/pubs/2012/3202/content.pdf CrossRef

Fenton, M., McNally, C., Byrne, J., Hemberg, E., McDermott, J., O’Neill, M.: Automatic innovative truss design using grammatical evolution. Autom. Constr. 39(0), 59–69 (2014). http://www.sciencedirect.com/science/article/pii/S0926580513002124 CrossRef

Forstenlechner, S.: Github repository: HeuristicLab.CFGGP: provides context free grammar problems for HeuristicLab (2016). https://github.com/t-h-e/HeuristicLab.CFGGP. Accessed 24 Jan 2017

Gulwani, S.: Dimensions in program synthesis. In: Proceedings of 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming, PPDP 2010, pp. 13–24. ACM, New York (2010). http://doi.acm.org/10.1145/1836089.1836091

Harman, M., Langdon, W.B., Jia, Y., White, D.R., Arcuri, A., Clark, J.A.: The GISMOE challenge: constructing the pareto program surface using genetic programming to find better programs (keynote paper). In: Proceedings of 27th IEEE/ACM International Conference on Automated Software Engineering (ASE), pp. 1–14, September 2012

Helmuth, T., Spector, L., Matheson, J.: Solving uncompromising problems with lexicase selection. IEEE Trans. Evol. Comput. 19(5), 630–643 (2015)CrossRef

Helmuth, T., Spector, L.: General program synthesis benchmark suite. In: GECCO 2015: Proceedings of 2015 on Genetic and Evolutionary Computation Conference, pp. 1039–1046. ACM, Madrid, 11–15 July 2015. http://doi.acm.org/10.1145/2739480.2754769

10.

Hemberg, E., Ho, L., O’Neill, M., Claussen, H.: A comparison of grammatical genetic programming grammars for controlling femtocell network coverage. Genet. Program. Evol. Mach. 14(1), 65–93 (2013). http://dx.doi.org/10.1007/s10710-012-9171-8 CrossRef

11.

Koza, J.R., Andre, D., Bennett, F.H., Keane, M.A.: Genetic Programming III: Darwinian Invention and Problem Solving, 1st edn. Morgan Kaufmann Publishers Inc., San Francisco (1999)MATH

12.

Landin, P.J.: The next 700 programming languages. Commun. ACM 9(3), 157–166 (1966). http://doi.acm.org/10.1145/365230.365257 CrossRefMATH

13.

Langdon, W.B., Harman, M.: Optimizing existing software with genetic programming. IEEE Trans. Evol. Comput. 19(1), 118–135 (2015)CrossRef

14.

Langdon, W.B., Ochoa, G.: Genetic improvement: a key challenge for evolutionary computation. In: Li, Y. (ed.) Key Challenges and Future Directions of Evolutionary Computation, pp. 3068–3075. IEEE, Vancouver, 25–29 July 2016. http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/langdon_2016_cec.pdf

15.

Le Goues, C., Nguyen, T., Forrest, S., Weimer, W.: GenProg: a generic method for automatic software repair. IEEE Trans. Softw. Eng. 38(1), 54–72 (2012). http://www.cs.virginia.edu/~weimer/p/weimer-tse2012-genprog.pdf

16.

Loughran, R., McDermott, J., O’Neill, M.: Tonality driven piano compositions with grammatical evolution. In: IEEE Congress on Evolutionary Computation, CEC 2015, Sendai, Japan, 25–28 May 2015, pp. 2168–2175. IEEE (2015). http://dx.doi.org/10.1109/CEC.2015.7257152

17.

McKay, R.I.B.: Fitness sharing in genetic programming. In: Proceedings of 2Nd Annual Conference on Genetic and Evolutionary Computation, GECCO 2000, pp. 435–442. Morgan Kaufmann Publishers Inc., San Francisco (2000). http://dl.acm.org/citation.cfm?id=2933718.2933800

18.

McKay, R., Hoai, N., Whigham, P., Shan, Y., O’Neill, M.: Grammar-based genetic programming: a survey. Genet. Program. Evol. Mach. 11(3–4), 365–396 (2010). http://dx.doi.org/10.1007/s10710-010-9109-y CrossRef

19.

Montana, D.J.: Strongly typed genetic programming. Evol. Comput. 3(2), 199–230 (1995). http://dx.doi.org/10.1162/evco.1995.3.2.199 CrossRef

20.

O’Neill, M., Nicolau, M., Agapitos, A.: Experiments in program synthesis with grammatical evolution: a focus on integer sorting. In: 2014 IEEE Congress on Evolutionary Computation (CEC), pp. 1504–1511, July 2014

21.

O’Neill, M., Ryan, C.: Automatic generation of caching algorithms. In: Miettinen, K., Mäkelä, M.M., Neittaanmäki, P., Periaux, J. (eds.) Evolutionary Algorithms in Engineering and Computer Science, pp. 127–134. Wiley, Jyväskylä, 30 May–3 June 1999. http://www.mit.jyu.fi/eurogen99/papers/oneill.ps

22.

O’Neill, M., Ryan, C.: Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Kluwer Academic Publishers, Norwell (2003)CrossRefMATH

23.

Poli, R., Langdon, W.B., McPhee, N.F.: A field guide to genetic programming (2008). (With contributions by J.R. Koza). Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk

24.

Spector, L.: Automatic Quantum Computer Programming: A Genetic Programming Approach, vol. 7. Kluwer Academic Publishers, Boston (2004)MATH

25.

Spector, L., Robinson, A.: Genetic programming and autoconstructive evolution with the push programming language. Genet. Program. Evol. Mach. 3(1), 7–40 (2002). http://hampshire.edu/lspector/pubs/push-gpem-final.pdf CrossRefMATH

26.

Swan, J., Epitropakis, M.G., Woodward, J.R.: Gen-O-Fix: an embeddable framework for dynamic adaptive genetic improvement programming. Technical report CSM-195, Computing Science and Mathematics, University of Stirling, UK, 17 January 2014. http://www.cs.stir.ac.uk/~kjt/techreps/recent.html

27.

Helmuth, T.M., L.S.: Detailed problem descriptions for general program synthesis benchmark suite. Technical report, School of Computer Science, University of Massachusetts Amherst (2015)

28.

Whigham, P.A.: Grammatical bias for evolutionary learning. Ph.D. thesis, New South Wales, Australia (1996). AAI0597571

Titel: A Grammar Design Pattern for Arbitrary Program Synthesis Problems in Genetic Programming
verfasst von: Stefan Forstenlechner
David Fagan
Miguel Nicolau
Michael O’Neill
Verlag: Springer International Publishing
Buch: Genetic Programming
Print ISBN: 978-3-319-55695-6

Electronic ISBN: 978-3-319-55696-3

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-55696-3_17

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"

Premium Partner