Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Graph representations in genetic programming

Published: 01 December 2021 Publication History

Abstract

Graph representations promise several desirable properties for genetic programming (GP); multiple-output programs, natural representations of code reuse and, in many cases, an innate mechanism for neutral drift. Each graph GP technique provides a program representation, genetic operators and overarching evolutionary algorithm. This makes it difficult to identify the individual causes of empirical differences, both between these methods and in comparison to traditional GP. In this work, we empirically study the behaviour of Cartesian genetic programming (CGP), linear genetic programming (LGP), evolving graphs by graph programming and traditional GP. By fixing some aspects of the configurations, we study the performance of each graph GP method and GP in combination with three different EAs: generational, steady-state and (1+λ). In general, we find that the best choice of representation, genetic operator and evolutionary algorithm depends on the problem domain. Further, we find that graph GP methods can increase search performance on complex real-world regression problems and, particularly in combination with the (1+λ) EA, are significantly better on digital circuit synthesis tasks. We further show that the reuse of intermediate results by tuning LGP’s number of registers and CGP’s levels back parameter is of utmost importance and contributes significantly to better convergence of an optimization algorithm when solving complex problems that benefit from code reuse.

References

[1]
T. Atkinson, D. Plump, S. Stepney, Evolving graphs by graph programming, in European Conference on Genetic Programming. (Springer International Publishing, Cham, 2018), pp. 35–51
[2]
T. Atkinson, D. Plump, S. Stepney, Probabilistic graph programs for randomised and evolutionary algorithms. In: Proc. International Conference on Graph Transformation, ICGT 2018, LNCS (Springer, 2018, vol. 10887, pp. 63–78)
[3]
T. Atkinson, D. Plump, S. Stepney, Evolving graphs with semantic neutral drift. Natural Computing (2019). arXiv:1810.10453
[4]
T. Atkinson, D. Plump, S. Stepney, Horizontal gene transfer for recombining graphs. Genetic Programming and Evolvable Machines (2020)
[5]
Brameier M and Banzhaf W Effective Linear Genetic Programming. Tech. Rep., Department of Computer Science 2001 Dortmund University of Dortmund
[6]
Brameier MF and Banzhaf W Linear Genetic Programming 2007 Berlin Springer
[7]
A. Corradini, U. Montanari, F. Rossi, H. Ehrig, R. Heckel, M. Löwe, Algebraic approaches to graph transformation–part I: basic concepts and double pushout approach, in Handbook Of Graph Grammars And Computing By Graph Transformation: Volume 1: Foundations (World Scientific, 1997), pp. 163–245
[8]
J. Demšar, Statistical comparisons of classifiers over multiple data sets. J.Mach. Learn. Res. 7(1), 1–30 (2006). http://jmlr.org/papers/v7/demsar06a.html
[9]
D. Dua, C. Graff, UCI machine learning repository (2017). http://archive.ics.uci.edu/ml
[10]
C. Fogelberg, M. Zhang, Linear genetic programming for multi-class object classification, in AI 2005: Advances in Artificial Intelligence. (Springer, Berlin Heidelberg, Berlin, Heidelberg, 2005), pp. 369–379
[11]
Fortin FA, De Rainville FM, Gardner MA, Parizeau M, and Gagné C DEAP: Evolutionary algorithms made easy J. Mach. Learn. Res. 2012 13 2171-2175
[12]
B.W. Goldman, W.F. Punch, Reducing wasted evaluations in Cartesian genetic programming, in Genetic Programming. (Springer, Berlin Heidelberg, 2013), pp. 61–72
[13]
Goldman BW and Punch WF Analysis of Cartesian genetic programming’s evolutionary mechanisms IEEE Trans. Evolut. Comput. 2015 19 3 359-373
[14]
S. Harris, T. Bueter, D.R. Tauritz, in A comparison of genetic programming variants for hyper-heuristics, in GECCO 2015 5th Workshop on Evolutionary Computation for the Automated Design of Algorithms , vol. ECADA’15, (Madrid, Spain, 2015), pp. 1043–1050
[15]
P. Kaufmann, R. Kalkreuth, An empirical study on the parametrization of Cartesian genetic programming, in Genetic and Evolutionary Computation (GECCO). (Compendium) (ACM, 2017)
[16]
P. Kaufmann, R. Kalkreuth, in Parametrizing Cartesian genetic programming: an empirical study, in KI 2017: Advances in Artificial Intelligence: 40th Annual German Conference on AI. (Springer International Publishing, 2017)
[17]
P. Kaufmann, R. Kalkreuth, On the parameterization of Cartesian genetic programming, in IEEE Congress on Evolutionary Computation (CEC) (IEEE, 2020)
[18]
P. Kaufmann, M. Platzner, in Advanced techniques for the creation and propagation of modules in Cartesian genetic programming, in Conference on Genetic and Evolutionary Computation (GECCO), (ACM Press, 2008), pp. 1219–1226
[19]
Koza JR Genetic Programming: On the Programming of Computers by Means of Natural Selection 1992 Cambridge, MA, USA MIT Press
[20]
J. McDermott, D.R. White, S. Luke, L. Manzoni, M. Castelli, L. Vanneschi, W. Jaskowski, K. Krawiec, R. Harper, K. De Jong, U.M. O’Reilly, Genetic programming needs better benchmarks, in Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, GECCO ’12 (2012), pp. 791–798
[21]
J. Miller, Cartesian genetic programming: its status and future. Genetic Programming and Evolvable Machines (2019).
[22]
Miller JF and Smith SL Redundancy and computational efficiency in Cartesian genetic programming IEEE Trans. Evol. Comput. 2006 10 2 167-174
[23]
J.F. Miller, P. Thomson, Cartesian genetic programming, in Genetic Programming. ed. by R. Poli, W. Banzhaf, W.B. Langdon, J. Miller, P. Nordin, T.C. Fogarty (Springer, Berlin Heidelberg, Berlin, Heidelberg, 2000), pp. 121–132
[24]
M. Nicolau, A. Agapitos, M.O’Neill, A. Brabazon, Guidelines for defining benchmark problems in genetic programming, in Proceedings of 2015 IEEE Congress on Evolutionary Computation (CEC 2015) (Sendai, Japan, 2015), pp. 1152–1159
[25]
R. Poli, W.B. Langdon, N.F. McPhee, A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk (2008). (With contributions by J. R. Koza)
[26]
M. Schmidt, H. Lipson, in Comparison of tree and graph encodings as function of problem complexity, vol. GECCO ’07, (Association for Computing Machinery, New York, NY, USA, 2007), pp. 1674–1679.
[27]
Sotto LFDP, de Melo VV, and Basgalupp MP λ-LGP: an improved version of linear genetic programming evaluated in the ant trail problem Knowl. Inf. Syst. 2017 52 2 445-465
[28]
L.F.D.P. Sotto, P. Kaufmann, T. Atkinson, R. Kalkreuth, M.P. Basgalupp, in A study on graph representations for genetic programming, in Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO ’20, (Association for Computing Machinery, New York, NY, USA, 2020), pp. 931–939.
[29]
L.F.D.P. Sotto, F. Rothlauf, in On the role of non-effective code in linear genetic programming, in Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’19 (ACM, New York, NY, USA, 2019), pp. 1075–1083
[30]
Turner AJ and Miller JF Neutral genetic drift: an investigation using Cartesian genetic programming Genet. Program Evolvable Mach. 2015 16 4 531-558
[31]
Turner AJ and Miller JF Neutral genetic drift: an investigation using Cartesian genetic programming Genet. Program Evolvable Mach. 2015 16 4 531-558
[32]
V.K. Vassilev, J.F. Miller, The advantages of landscape neutrality in digital circuit evolution, in Evolvable Systems: From Biology to Hardware. ed. by J. Miller, A. Thompson, P. Thomson, T.C. Fogarty (Springer, Berlin Heidelberg, Berlin, Heidelberg, 2000), pp. 252–263
[33]
Walker JA The automatic acquisition, evolution and reuse of modules in Cartesian genetic programming IEEE Trans. Evol. Comput. 2007 12 397-417
[34]
White DR, McDermott J, Castelli M, Manzoni L, Goldman BW, Kronberger G, Jaskowski W, O’Reilly UM, and Luke S Better GP benchmarks: community survey results and proposals Genet. Program. Evol. Mach. 2013 14 1 3-29
[35]
G. Wilson, W. Banzhaf, A comparison of Cartesian genetic programming and linear genetic programming, in Genetic Programming. ed. by M. O’Neill, L. Vanneschi, S. Gustafson, A.I. Esparcia Alcázar, I. De Falco, A. Della Cioppa, E. Tarantino (Springer, Berlin Heidelberg, Berlin, Heidelberg, 2008), pp. 182–193
[36]
T. Yu, J.F. Miller, Neutrality and the evolvability of boolean function landscape. In: Proceedings of the 4th European Conference on Genetic Programming, EuroGP ’01, pp. 204–217. Springer-Verlag, Berlin, Heidelberg (2001). http://dl.acm.org/citation.cfm?id=646809.704083

Cited By

View all
  • (2024)Modular Multitree Genetic Programming for Evolutionary Feature Construction for RegressionIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.331863828:5(1455-1469)Online publication date: 1-Oct-2024
  • (2024)Bridging directed acyclic graphs to linear representations in linear genetic programming: a case study of dynamic schedulingGenetic Programming and Evolvable Machines10.1007/s10710-023-09478-825:1Online publication date: 25-Jan-2024
  • (2023)General Boolean Function Benchmark SuiteProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607131(84-95)Online publication date: 30-Aug-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Genetic Programming and Evolvable Machines
Genetic Programming and Evolvable Machines  Volume 22, Issue 4
Dec 2021
240 pages

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 December 2021

Author Tags

  1. Linear genetic programming
  2. Cartesian genetic programming
  3. Evolving graphs by graph programming
  4. Directed acyclic graph

Qualifiers

  • Research-article

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 21 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Modular Multitree Genetic Programming for Evolutionary Feature Construction for RegressionIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.331863828:5(1455-1469)Online publication date: 1-Oct-2024
  • (2024)Bridging directed acyclic graphs to linear representations in linear genetic programming: a case study of dynamic schedulingGenetic Programming and Evolvable Machines10.1007/s10710-023-09478-825:1Online publication date: 25-Jan-2024
  • (2023)General Boolean Function Benchmark SuiteProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607131(84-95)Online publication date: 30-Aug-2023
  • (2023)Graph-Based Mutations for Music GenerationProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596318(1916-1919)Online publication date: 15-Jul-2023
  • (2023)Towards a General Boolean Function Benchmark SuiteProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3590685(591-594)Online publication date: 15-Jul-2023
  • (2022)Graph-based genetic programmingProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533657(958-982)Online publication date: 9-Jul-2022
  • (2022)The pole balancing problem from the viewpoint of system flexibilityProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3529040(427-430)Online publication date: 9-Jul-2022

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media