More Web Proxy on the site http://driver.im/

research-article

Solving the exponential growth of symbolic regression trees in geometric semantic genetic programming

Authors:

Joao Francisco B. S. Martins,

Luiz Otavio V. B. Oliveira,

Luis F. Miranda,

Felipe Casadei,

Gisele L. PappaAuthors Info & Claims

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 1151 - 1158

https://doi.org/10.1145/3205455.3205593

Published: 02 July 2018 Publication History

Abstract

Advances in Geometric Semantic Genetic Programming (GSGP) have shown that this variant of Genetic Programming (GP) reaches better results than its predecessor for supervised machine learning problems, particularly in the task of symbolic regression. However, by construction, the geometric semantic crossover operator generates individuals that grow exponentially with the number of generations, resulting in solutions with limited use. This paper presents a new method for individual simplification named GSGP with Reduced trees (GSGP-Red). GSGP-Red works by expanding the functions generated by the geometric semantic operators. The resulting expanded function is guaranteed to be a linear combination that, in a second step, has its repeated structures and respective coefficients aggregated. Experiments in 12 real-world datasets show that it is not only possible to create smaller and completely equivalent individuals in competitive computational time, but also to reduce the number of nodes composing them by 58 orders of magnitude, on average.

References

[1]

Julio Albinati, Gisele L. Pappa, Fernando E. B. Otero, and Luiz Otavio V. B. Oliveira. 2015. The Effect of Distinct Geometric Semantic Crossover Operators in Regression Problems. In 18th European Conference, EuroGP 2015 (LNCS), Penousal Machado, Malcolm I. Heywood, James McDermott, Mauro Castelli, Pablo García-Sánchez, Paolo Burelli, Sebastian Risi, and Kevin Sim (Eds.), Vol. 9025. Springer International Publishing, 3--15.

[2]

Julio Albinati, Gisele L. Pappa, Fernando E. B. Otero, and Luiz Otavio V. B. Oliveira. 2015. The Effect of Distinct Geometric Semantic Crossover Operators in Regression Problems. In Genetic Programming, Penousal Machado, Malcolm I. Heywood, James McDermott, Mauro Castelli, Pablo García-Sánchez, Paolo Burelli, Sebastian Risi, and Kevin Sim (Eds.). Springer International Publishing, Cham, 3--15.

[3]

W. Banzhaf, P. Nordin, R.E. Keller, and F.D. Francone. 1998. Genetic Programming --- an Introduction: on the Automatic Evolution of Computer Programs and Its Applications. Morgan Kaufmann Publishers.

Digital Library

[4]

Lawrence Beadle and Colin G Johnson. 2008. Semantically driven crossover in genetic programming. In Evolutionary Computation, 2008. IEEE Congress on. IEEE, 111--116.

Digital Library

[5]

Lawrence Beadle and Colin G Johnson. 2009. Semantically driven mutation in genetic programming. In Evolutionary Computation, 2009. IEEE Congress on. IEEE, 1336--1342.

Digital Library

[6]

Mauro Castelli, Sara Silva, and Leonardo Vanneschi. 2015. A C++ framework for geometric semantic genetic programming. Genetic Programming and Evolvable Machines 16, 1 (Mar 2015), 73--81.

Digital Library

[7]

Mauro Castelli, Leonardo Vanneschi, and Aleš Popovič. 2016. Controlling individuals growth in semantic genetic programming through elitist replacement. Computational intelligence and neuroscience 2016 (2016), 42.

Digital Library

[8]

Mauro Castelli, Leonardo Vanneschi, and Sara Silva. 2013. Prediction of high performance concrete strength using Genetic Programming with geometric semantic genetic operators. Expert Systems with Applications 40, 17 (2013), 6856--6862.

Digital Library

[9]

Mauro Castelli, Leonardo Vanneschi, and Sara Silva. 2014. Prediction of the Unified Parkinson's Disease Rating Scale Assessment Using a Genetic Programming System with Geometric Semantic Genetic Operators. Expert Systems with Applications 41, 10 (2014), 4608 -- 4616.

[10]

Janez Demšar. 2006. Statistical comparisons of classifiers over multiple data sets. The Journal of Machine Learning Research 7 (2006), 1--30.

Digital Library

[11]

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

Digital Library

[12]

M. Lichman. 2015. UCI Mach. Learning Repository. (2015). http://archive.ics.uci.edu/ml

[13]

Alberto Moraglio. 2011. Abstract convex evolutionary search. In Proceedings of the 11th workshop on Foundations of genetic algorithms (FOGA '11). ACM, 151--162.

Digital Library

[14]

Alberto Moraglio. 2014. An efficient implementation of GSGP using higher-order functions and memoization. In: Johnson, C., et al. (eds.) Semantic Methods in Genetic Programming, Ljubljana, Slovenia, 13 Sept. 2014. Workshop at Parallel Problem Solving from Nature 2014 conference. (2014).

[15]

Alberto Moraglio, Krzysztof Krawiec, and Colin G. Johnson. 2012. Geometric Semantic Genetic Programming. In Parallel Problem Solving from Nature, PPSN XII (part 1), Carlos A. Coello Coello, Vincenzo Cutello, Kalyanmoy Deb, Stephanie Forrest, Giuseppe Nicosia, and Mario Pavone (Eds.). Lecture Notes in Computer Science, Vol. 7491. Springer, 21--31.

Digital Library

[16]

Quang Uy Nguyen, Tuan Anh Pham, Xuan Hoai Nguyen, and James McDermott. 2016. Subtree semantic geometric crossover for genetic programming. Genetic Programming and Evolvable Machines 17, 1 (Mar 2016), 25--53.

Digital Library

[17]

J. Ni, R. H. Drieberg, and P. I. Rockett. 2013. The use of an analytic quotient operator in genetic programming. Evolutionary Computation, IEEE Trans. on 17, 1 (Apr 2013), 146--152.

Digital Library

[18]

L. O. V. B. Oliveira. 2016. Improving Search in Geometric Semantic Genetic Programming. Ph.D. Dissertation. Universidade Federal de Minas Gerais.

[19]

Luiz Otavio V. B. Oliveira, Fernando E. B. Otero, and Gisele L. Pappa. 2016. A Dispersion Operator for Geometric Semantic Genetic Programming. In Proc. of the Genetic and Evolutionary Computation Conference 2016. ACM, 773--780.

Digital Library

[20]

Tomasz P. Pawlak. 2015. Competent Algorithms for Geometric Semantic Genetic Programming. Ph.D. Dissertation. Poznan University of Technology, Pozna'n, Poland.

[21]

Tomasz P Pawlak and Krzysztof Krawiec. 2015. Progress properties and fitness bounds for geometric semantic search operators. Genetic Programming and Evolvable Machines (2015), 1--19.

Digital Library

[22]

Tomasz P Pawlak and Krzysztof Krawiec. 2017. Competent geometric semantic genetic programming for symbolic regression and boolean function synthesis. Evolutionary computation Early Access (2017), 1--36.

[23]

David J Sheskin. 2003. Handbook of parametric and nonparametric statistical procedures (3rd ed. ed.). Chapman & Hal/CRC.

[24]

Leonardo Vanneschi. 2017. An introduction to geometric semantic genetic programming. In NEO 2015. Springer, 3--42.

[25]

Leonardo Vanneschi, Mauro Castelli, Luca Manzoni, and Sara Silva. 2013. A new implementation of geometric semantic GP and its application to problems in pharmacokinetics. In 16th European Conference, EuroGP 2013 (LNCS), Krzysztof Krawiec, Alberto Moraglio, Ting Hu, A. Şima Etaner-Uyar, and Bin Hu (Eds.), Vol. 7831. Springer Berlin Heidelberg, 205--216.

Digital Library

[26]

Leonardo Vanneschi, Sara Silva, Mauro Castelli, and Luca Manzoni. 2014. Geometric Semantic Genetic Programming for Real Life Applications. In Genetic Programming Theory and Practice XI, Rick Riolo, Jason H. Moore, and Mark Kotanchek (Eds.). Springer New York, 191--209.

Cited By

Zhang HChen QXue BBanzhaf WZhang M(2024)A Semantic-Based Hoist Mutation Operator for Evolutionary Feature Construction in RegressionIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.333123428:6(1689-1703)Online publication date: Dec-2024
https://doi.org/10.1109/TEVC.2023.3331234
Nadizar GSakallioglu BGarrow FSilva SVanneschi L(2024)Geometric semantic GP with linear scaling: Darwinian versus Lamarckian evolutionGenetic Programming and Evolvable Machines10.1007/s10710-024-09488-025:2Online publication date: 1-Jun-2024
https://doi.org/10.1007/s10710-024-09488-0
Dick G(2024)An ensemble learning interpretation of geometric semantic genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-024-09482-625:1Online publication date: 11-Mar-2024
https://dl.acm.org/doi/10.1007/s10710-024-09482-6
Show More Cited By

Index Terms

Solving the exponential growth of symbolic regression trees in geometric semantic genetic programming
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
        Supervised learning by regression
    2. Machine learning approaches
      1. Bio-inspired approaches
        Genetic programming

Recommendations

An Investigation of Geometric Semantic GP with Linear Scaling
GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

Geometric semantic genetic programming (GSGP) and linear scaling (LS) have both, independently, shown the ability to outperform standard genetic programming (GP) for symbolic regression. GSGP uses geometric semantic genetic operators, different from ...
Cartesian Genetic Programming as an Optimizer of Programs Evolved with Geometric Semantic Genetic Programming
Genetic Programming
Abstract
In Geometric Semantic Genetic Programming (GSGP), genetic operators directly work at the level of semantics rather than syntax. It provides many advantages, including much higher quality of resulting individuals (in terms of error) in comparison ...
Semantic schema based genetic programming for symbolic regression
Abstract
Despite the empirical success of Genetic programming (GP) in various symbolic regression applications, GP is not still known as a reliable problem-solving technique in this domain. Non-locality of GP representation and operators causes ...
Highlights
- In contrast to natural evolution, genetic programming evolution is not gradual.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

July 2018

1578 pages

ISBN:9781450356183

DOI:10.1145/3205455

Editor:
Hernan Aguirre
Shinshu University
,
General Chair:
Keiki Takadama
The University of Electro-Communications

Copyright © 2018 ACM.

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 the author(s) 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].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conselho Nacional de Desenvolvimento Científico e Tecnológico
Fundação de Amparo à Pesquisa do Estado de Minas Gerais
European Commission under the Cooperation Programme MCTI/RNP

Conference

GECCO '18

Sponsor:

SIGEVO

GECCO '18: Genetic and Evolutionary Computation Conference

July 15 - 19, 2018

Kyoto, Japan

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
209
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)4

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang HChen QXue BBanzhaf WZhang M(2024)A Semantic-Based Hoist Mutation Operator for Evolutionary Feature Construction in RegressionIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.333123428:6(1689-1703)Online publication date: Dec-2024
https://doi.org/10.1109/TEVC.2023.3331234
Nadizar GSakallioglu BGarrow FSilva SVanneschi L(2024)Geometric semantic GP with linear scaling: Darwinian versus Lamarckian evolutionGenetic Programming and Evolvable Machines10.1007/s10710-024-09488-025:2Online publication date: 1-Jun-2024
https://doi.org/10.1007/s10710-024-09488-0
Dick G(2024)An ensemble learning interpretation of geometric semantic genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-024-09482-625:1Online publication date: 11-Mar-2024
https://dl.acm.org/doi/10.1007/s10710-024-09482-6
Bonin LRovito LDe Lorenzo AManzoni L(2024)Cellular geometric semantic genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-024-09480-825:1Online publication date: 21-Feb-2024
https://dl.acm.org/doi/10.1007/s10710-024-09480-8
Bakurov IMuñoz Contreras JCastelli MRodrigues NSilva STrujillo LVanneschi L(2024)Geometric semantic genetic programming with normalized and standardized random programsGenetic Programming and Evolvable Machines10.1007/s10710-024-09479-125:1Online publication date: 8-Feb-2024
https://dl.acm.org/doi/10.1007/s10710-024-09479-1
Vanneschi L(2024)SLIM_GSGP: The Non-bloating Geometric Semantic Genetic ProgrammingGenetic Programming10.1007/978-3-031-56957-9_8(125-141)Online publication date: 3-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-56957-9_8
Zhang HChen QXue BBanzhaf WZhang M(2023)A geometric semantic macro-crossover operator for evolutionary feature construction in regressionGenetic Programming and Evolvable Machines10.1007/s10710-023-09465-z25:1Online publication date: 8-Dec-2023
https://dl.acm.org/doi/10.1007/s10710-023-09465-z
Wittenberg DRothlauf FGagné C(2023)Denoising autoencoder genetic programming: strategies to control exploration and exploitation in searchGenetic Programming and Evolvable Machines10.1007/s10710-023-09462-224:2Online publication date: 8-Nov-2023
https://dl.acm.org/doi/10.1007/s10710-023-09462-2
Wittenberg DRothlauf F(2023)Small Solutions for Real-World Symbolic Regression Using Denoising Autoencoder Genetic ProgrammingGenetic Programming10.1007/978-3-031-29573-7_7(101-116)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-29573-7_7
Leite ASchoenauer M(2023)Memetic Semantic Genetic Programming for Symbolic RegressionGenetic Programming10.1007/978-3-031-29573-7_13(198-212)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-29573-7_13
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents