tutorial

GPDL: a framework-independent problem definition language for grammar-guided genetic programming

Authors:

Gabriel Kronberger,

Michael Kommenda,

Stefan Wagner,

Heinz DoblerAuthors Info & Claims

GECCO '13 Companion: Proceedings of the 15th annual conference companion on Genetic and evolutionary computation

Pages 1333 - 1340

https://doi.org/10.1145/2464576.2482713

Published: 06 July 2013 Publication History

Get Access

Abstract

Defining custom problem types in genetic programming (GP) software systems is a tedious task that usually involves the implementation of custom classes and methods including framework-specific code. Users who want to solve a custom problem have to know the details of the targeted framework, for instance cloning semantics, and often have to write a lot of boilerplate code in order to implement the necessary functionality correctly. This can lead to frustration and hinders new developments and the application of GP to solve interesting problems.

In this contribution we propose a framework-independent definition language for GP problems that can reduce the required effort and facilitate the integration of new problem types. We draw a parallel between the implementation of compilers for programming languages and the implementation of GP problems and reuse the well-established concept of attributed grammars with semantic actions to define computational symbols, semantics and structural constraints for GP. This goes beyond previous work in the area of context-free-grammar GP and grammatical evolution, because we also interweave the definition of symbol semantics and the target function with the definition of the grammar.

This paper describes the proposed GP problem definition language (GPDL) and exemplary definitions of two popular benchmark problems using GPDL. We also describe a reference implementation of a GPDL compiler for HeuristicLab.

References

[1]

W. W. Cohen. Grammatically biased learning: Learning logic programs using an explicit antecedent description language. Artif. Intell., 68(2):303--366, 1994.

Digital Library

Google Scholar

[2]

H. Dobler. Top-down parsing in Coco-2. SIGPLAN Notices, 26(3):79--87, Jan. 1991.

Digital Library

Google Scholar

[3]

H. Dobler and K. Pirklbauer. Coco-2: A new compiler compiler. SIGPLAN Notices, 25(5):82--90, May 1990.

Digital Library

Google Scholar

[4]

Y. Hasegawa and H. Iba. Latent variable model for estimation of distribution algorithm based on a probabilistic context-free grammar. IEEE Transactions on Evolutionary Computation, 13(4):858--878, Aug. 2009.

Digital Library

Google Scholar

[5]

D. Knuth. Semantics of context-free languages. Mathematical Systems Theory, 2(2):127--145, 1968.

Crossref

Google Scholar

[6]

M. Kommenda, G. Kronberger, S. Wagner, S. Winkler, and M. Affenzeller. On the architecture and implementation of tree-based genetic programming in HeuristicLab. In Proc. of the 14th GECCO, GECCO Companion '12, pages 101--108, New York, NY, USA, 2012. ACM.

Digital Library

Google Scholar

[7]

J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.

Digital Library

Google Scholar

[8]

R. I. McKay, N. X. Hoai, P. A. Whigham, Y. Shan, and M. O'Neill. Grammar-based genetic programming: a survey. Genetic Programming and Evolvable Machines, 11(3/4):365--396, Sept. 2010.

Digital Library

Google Scholar

[9]

M. O'Neill and C. Ryan. Grammatical Evolution: Evolutionary Automatic Programming in a Arbitrary Language, volume 4 of Genetic programming. Kluwer Academic Publishers, 2003.

Digital Library

Google Scholar

[10]

B. J. Ross. Logic-based genetic programming with definite clause translation grammars. New Generation Computing, 19(4):313--337, 2001.

Digital Library

Google Scholar

[11]

S. Wagner. Heuristic optimization software systems - Modeling of heuristic optimization algorithms in the HeuristicLab software environment. PhD thesis, Institute for Formal Models and Verification, Johannes Kepler University, Linz, 2009.

Google Scholar

[12]

J. A. Walker and J. F. Miller. The automatic acquisition, evolution and reuse of modules in cartesian genetic programming. IEEE Transactions on Evolutionary Computation, 12(4):397--417, Aug. 2008.

Digital Library

Google Scholar

[13]

P. A. Whigham. Grammatically-based genetic programming. In J. P. Rosca, editor, Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, pages 33--41, Tahoe City, California, USA, 9 July 1995.

Google Scholar

Cited By

View all

Scheibenpflug ABeham AKommenda MKarder JWagner SAffenzeller MEsparcia-Alcázar A(2015)Simplifying Problem Definitions in the HeuristicLab Optimization EnvironmentProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2768463(1101-1108)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739482.2768463
Kronberger GKommenda MWinkler SAffenzeller M(2015)Using Contextual Information in Sequential Search for Grammatical Optimization ProblemsComputer Aided Systems Theory – EUROCAST 201510.1007/978-3-319-27340-2_52(417-424)Online publication date: 17-Dec-2015
https://doi.org/10.1007/978-3-319-27340-2_52
Kronberger GKommenda M(2015)Search Strategies for Grammatical Optimization Problems—Alternatives to Grammar-Guided Genetic ProgrammingComputational Intelligence and Efficiency in Engineering Systems10.1007/978-3-319-15720-7_7(89-102)Online publication date: 11-Mar-2015
https://doi.org/10.1007/978-3-319-15720-7_7
Show More Cited By

Index Terms

GPDL: a framework-independent problem definition language for grammar-guided genetic programming
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

XPL

Languages that are used for Software Language Engineering (SLE) offer a range of features that support the construction and deployment of new languages. SLE languages offer features for constructing and processing syntax and defining the semantics of ...
Embedded parser generators
Haskell '11: Proceedings of the 4th ACM symposium on Haskell

We present a novel method of embedding context-free grammars in Haskell, and to automatically generate parsers and pretty-printers from them. We have implemented this method in a library called BNFC-meta (from the BNF Converter, which it is built on). ...
Exact Schema Theory and Markov Chain Models for Genetic Programming and Variable-length Genetic Algorithms with Homologous Crossover

Genetic Programming (GP) homologous crossovers are a group of operators, including GP one-point crossover and GP uniform crossover, where the offspring are created preserving the position of the genetic material taken from the parents. In this paper we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '13 Companion: Proceedings of the 15th annual conference companion on Genetic and evolutionary computation

July 2013

1798 pages

ISBN:9781450319645

DOI:10.1145/2464576

Editor:
Christian Blum
IKERBASQUE and University of the Basque Country UPV/EHU, Spain
,
General Chair:
Enrique Alba
University of Malaga, Spain

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Tutorial

Conference

GECCO '13

Sponsor:

SIGEVO

GECCO '13: Genetic and Evolutionary Computation Conference

July 6 - 10, 2013

Amsterdam, The Netherlands

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
89
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Scheibenpflug ABeham AKommenda MKarder JWagner SAffenzeller MEsparcia-Alcázar A(2015)Simplifying Problem Definitions in the HeuristicLab Optimization EnvironmentProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2768463(1101-1108)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739482.2768463
Kronberger GKommenda MWinkler SAffenzeller M(2015)Using Contextual Information in Sequential Search for Grammatical Optimization ProblemsComputer Aided Systems Theory – EUROCAST 201510.1007/978-3-319-27340-2_52(417-424)Online publication date: 17-Dec-2015
https://doi.org/10.1007/978-3-319-27340-2_52
Kronberger GKommenda M(2015)Search Strategies for Grammatical Optimization Problems—Alternatives to Grammar-Guided Genetic ProgrammingComputational Intelligence and Efficiency in Engineering Systems10.1007/978-3-319-15720-7_7(89-102)Online publication date: 11-Mar-2015
https://doi.org/10.1007/978-3-319-15720-7_7
Leroux COtero FJohnson CArnold D(2014)A genetic programming problem definition language code generator for the epochX frameworkProceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2598394.2605691(1149-1154)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2598394.2605691

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

XPL

Embedded parser generators

Exact Schema Theory and Markov Chain Models for Genetic Programming and Variable-length Genetic Algorithms with Homologous Crossover