Multilayer analysis of population diversity in grammatical evolution for symbolic regression
Authors: 
Gabriel Kronberger, J. Manuel Colmenar, Stephan M. Winkler, J. Ignacio HidalgoAuthors Info & Claims
Abstract
In this paper, we analyze the population diversity of grammatical evolution (GE) on multiple levels of genetic information: chromosome diversity, expression diversity, and output diversity. Thereby, we use a tree-similarity metric from tree-based GP literature to determine similarity of expression trees generated in GE. The similarity of outputs is determined via their correlation. We track the pairwise similarities for all individuals within a generation on all three levels and track the distribution of similarity values over generations. We demonstrate the analysis method using four symbolic regression problem instances and find that the visualization highlights some issues that can occur when using GE such as: large groups of individuals with highly similar outputs, a high fraction of trees with constant outputs, or short and highly similar trees in the early stages of the GE run. Especially in the early phases of GE, we see that a large subset of the population represents equivalent expressions. In early stages, rather short expressions are produced leaving large parts of the chromosome unexpressed. More complex expressions can be derived only after GE has successfully evolved well-working beginnings of chromosomes.
References
[1]
Adamu K, Phelps S (2009) Modelling financial time series using grammatical evolution. In: Proceedings of the workshop on advances in machine learning for computational finance, London, UK
[2]
Adaptive Group BS (2018) ABSys JECO (Java Evolutionary Computation) library. https://github.com/ABSysGroup/jeco
[3]
Bartoli A, De Lorenzo A, Medvet E, and Squillero G Multi-level diversity promotion strategies for grammar-guided genetic programming Appl Soft Comput 2019 83 105599
[4]
Bartoli A, Castelli M, and Medvet E Weighted hierarchical grammatical evolution IEEE Trans Cybern 2020 50 2 476-488
[5]
Burke EK, Gustafson S, and Kendall G Diversity in genetic programming: an analysis of measures and correlation with fitness IEEE Trans Evolut Comput 2004 8 1 47-62
[6]
Burlacu B, Affenzeller M, Kronberger G, Kommenda M (2019) Online diversity control in symbolic regression via a fast hash-based tree similarity measure. In: 2019 IEEE congress on evolutionary computation (CEC), pp 2175–2182. 10.1109/CEC.2019.8790162
[7]
Castejón F and Carmona EJ Automatic design of analog electronic circuits using grammatical evolution Appl Soft Comput 2018 62 1003-1018
[8]
Foster JA (2017) 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 Evol Mach 18(3):395–398. 10.1007/s10710-017-9296-x
[9]
Hidalgo JI, Colmenar JM, Risco-Martín JL, Cuesta-Infante A, Maqueda E, Botella M, and Rubio JA Modeling glycemia in humans by means of grammatical evolution Appl Soft Comput 2014 20 40-53
[10]
Koza JR Genetic programming 1992 Cambridge The MIT Press
[11]
Lourenço N, Pereira FB, and Costa E Unveiling the properties of structured grammatical evolution Genet Program Evolut Mach 2016 17 3 251-289
[12]
Medvet E McDermott J, Castelli M, Sekanina L, Haasdijk E, and García-Sánchez P A comparative analysis of dynamic locality and redundancy in grammatical evolution Genetic programming 2017 Cham Springer 326-342
[13]
Medvet E, Daolio F, Tagliapietra D (2017) Evolvability in grammatical evolution. In: Proceedings of the genetic and evolutionary computation conference, pp 977–984
[14]
Medvet E, Virgolin M, Castelli M, Bosman PA, Gonçalves I, and Tušar T Unveiling evolutionary algorithm representation with DU maps Genet Program Evolut Mach 2018 19 3 351-389
[15]
Michalewicz Z Genetic algorithms data structures evolution programs 1996 New York Springer
[16]
Mingo JM and Aler R Evolution of shared grammars for describing simulated spatial scenes with grammatical evolution Genet Program Evolut Mach 2018 19 1 235-270
[17]
Nicolau M Understanding grammatical evolution: initialisation Genet Progr Evolut Mach 2017 18 4 467-507
[18]
Nicolau M, Agapitos A, O’Neill M, Brabazon A (2015) Guidelines for defining benchmark problems in genetic programming. In: 2015 IEEE congress on evolutionary computation (CEC), IEEE, pp 1152–1159
[19]
O’Neill M and Ryan C Floreano D, Nicoud JD, and Mondada F Genetic code degeneracy: implications for grammatical evolution and beyond Advances in artificial life 1999 Berlin Springer 149-153
[20]
O’Neill M and Ryan C Grammatical evolution IEEE Trans Evolut Comput 2001 5 4 349-358
[21]
Pagie L and Hogeweg P Evolutionary consequences of coevolving targets Evolut Comput 1998 5 401-418
[22]
Poli R, Langdon WB, McPhee NF (2008) A field guide to genetic programming. http://lulu.com and freely http://www.gp-field-guide.org.uk
[23]
Risco-Martín JL, Colmenar JM, Hidalgo JI, Lanchares J, Díaz J (2014) A methodology to automatically optimize dynamic memory managers applying grammatical evolution. J Syst Softw 91:109–123. 10.1016/j.jss.2013.12.044
[24]
Rothlauf F, Goldberg DE (2003) Redundant representations in evolutionary computation. Evol Comput 11(4):381–415. 10.1162/106365603322519288
[25]
Rothlauf F and Oetzel M Collet P, Tomassini M, Ebner M, Gustafson S, and Ekárt A On the locality of grammatical evolution Genet Program 2006 Berlin Springer 320-330
[26]
Valiente G (2001) An efficient bottom-up distance between trees. In: Proceedings eighth symposium on string processing and information retrieval, pp 212–219. 10.1109/SPIRE.2001.989761
[27]
Vladislavleva EJ, Smits GF, and den Hertog D Order of nonlinearity as a complexity measure for models generated by symbolic regression via pareto genetic programming IEEE Trans Evol Comput 2009 13 2 333-349
[28]
Whigham PA et al. Grammatically-based genetic programming Proc Workshop Genet Program Theory Real World Appl 1995 16 33-41
[29]
Whigham PA, Dick G, Maclaurin J, Owen CA (2015) Examining the “Best of Both Worlds” of grammatical evolution. In: Proceedings of the 2015 annual conference on genetic and evolutionary computation, GECCO ’15, ACM, New York, NY, USA, pp 1111–1118. 10.1145/2739480.2754784
[30]
Whigham PA, Dick G, and Maclaurin J On the mapping of genotype to phenotype in evolutionary algorithms Genet Program Evol Mach 2017 18 3 353-361
[31]
White DR, McDermott J, Castelli M, Manzoni L, Goldman BW, Kronberger G, Jaśkowski W, O’Reilly UM, and Luke S Better gp benchmarks: community survey results and proposals Genet Program Evol Mach 2013 14 1 3-29
[32]
Winkler SM (2010) Structural versus evaluation based solutions similarity in genetic programming based system identification. In: González JR, Pelta DA, Cruz C, Terrazas G, Krasnogor N (eds) Nature inspired cooperative strategies for optimization, NICSO 2010, studies in computational intelligence, vol 284, Springer, Granada, Spain, pp 269–282
[33]
Winkler SM, Affenzeller M, Burlacu B, Kronberger G, Kommenda M, Fleck P (2018) Similarity-based analysis of population dynamics in genetic programming performing symbolic regression. In: Genetic programming theory and practice XIV, Springer
Index Terms
- Multilayer analysis of population diversity in grammatical evolution for symbolic regression
Index terms have been assigned to the content through auto-classification.
Recommendations
Measuring and Maintaining Population Diversity in Search-Based Unit Test Generation
Search-Based Software EngineeringAbstractGenetic algorithms (GAs) have been demonstrated to be effective at generating unit tests. However, GAs often suffer from a loss of population diversity, which causes the search to prematurely converge, thus negatively affecting the resulting code ...
Diversity Guided Evolutionary Programming: A novel approach for continuous optimization
Avoiding premature convergence to local optima and rapid convergence towards global optima has been the major concern with evolutionary systems research. In order to avoid premature convergence, sufficient amount of genetic diversity within the evolving ...
Comparative study of diversity based parallel dual population genetic algorithm for unconstrained function optimisations
The genetic algorithms GAs metaheuristic deals with large scale combinatorial optimisation problems. It is biologically inspired by the method, based on the principle of survival of the fittest. In GAs, the concept of multiple populations offers an ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s) 2020.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 August 2020
Author Tags
Qualifiers
- Research-article
Funding Sources
- Christian Doppler Forschungsgesellschaft
- Spanish Government Minister of Science and Innovation
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024