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

article

Competent geometric semantic genetic programming for symbolic regression and boolean function synthesis

Authors:

Tomasz P. Pawlak,

Krzysztof KrawiecAuthors Info & Claims

Evolutionary Computation, Volume 26, Issue 2

Pages 177 - 212

https://doi.org/10.1162/evco_a_00205

Published: 01 June 2018 Publication History

Abstract

Program semantics is a promising recent research thread in Genetic Programming GP. Over aï dozen semantic-aware search, selection, and initialization operators for GP have been proposed to date. Some of these operators are designed to exploit the geometric properties of semantic space, while others focus on making offspring effective , that is, semantically different from their parents. Only aï small fraction of previous works aimed at addressing both of these features simultaneously. In this article, we propose aï suite of competent operators that combine effectiveness with geometry for population initialization, mate selection, mutation, and crossover. We present aï theoretical rationale behind these operators and compare them experimentally to operators known from literature on symbolic regression and Boolean function synthesis benchmarks. We analyze each operator in isolation as well as verify how they fare together in an evolutionary run, concluding that the competent operators are superior on aï wide range of performance indicators, including best-of-run fitness, test-set fitness, and programï size.

References

[1]

Beadle, L., and Johnson, C. (2008). Semantically driven crossover in genetic programming. In Proceedings of the IEEE Congress on Evolutionary Computation , pp. 111-116.

[2]

Beadle, L., and Johnson, C. G. (2009a). Semantic analysis of program initialisation in genetic programming. Genetic Programming and Evolvable Machines , 10(3):307-337.

[3]

Beadle, L., and Johnson, C. G. (2009b). Semantically driven mutation in genetic programming. In Proceedings of the IEEE Congress on Evolutionary Computation , pp. 1336-1342.

[4]

Burden, R., and Faires, J. (2010). Numerical analysis . Boston: Cengage Learning.

[5]

Caratheódory, C. (1911). Über den variabilitätsbereich der fourierschen konstanten von positiven harmonischen funktionen. Rendiconti del Circolo Matematico di Palermo , 32:193-217.

[6]

Castelli, M., Castaldi, D., Giordani, I., Silva, S., Vanneschi, L., Archetti, F., and Maccagnola, D. (2013). An efficient implementation of geometric semantic genetic programming for anticoagulation level prediction in pharmacogenetics. In Proceedings of the 16th Portuguese Conference on Artificial Intelligence , pp. 78-89. Lecture Notes in Computer Science, vol. 8154.

[7]

Castelli, M., Manzoni, L., and Vanneschi, L. (2012). An efficient genetic programming system with geometric semantic operators and its application to human oral bioavailability prediction. Retrieved from arXiv: 1208.2437.

[8]

Castelli, M., Vanneschi, L., and Popovic, A. (2015). Predicting burned areas of forest fires: An artificial intelligence approach. Fire Ecology , 11(1):106-118.

[9]

Castelli, M., Vanneschi, L., and Silva, S. (2013). Prediction of high performance concrete strength using genetic programming with geometric semantic genetic operators. Expert Systems with Applications , 40(17):6856-6862.

[10]

Castelli, M., Vanneschi, L., and Silva, S. (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):4608-4616.

[11]

Galván-López, E., Cody-Kenny, B., Trujillo, L., and Kattan, A. (2013). Using semantics in the selection mechanism in genetic programming: A simple method for promoting semantic diversity. In Proceedings of the IEEE Congress on Evolutionary Computation , 2972-2979.

[12]

Geman, S., Bienenstock, E., and Doursat, R. (1992). Neural networks and the bias/variance dilemma. Neural Computation , 4(1):1-58.

[13]

Hothorn, T., Hornik, K., van de Wiel, M. A., and Zeileis, A. (2015). Package "coin": Conditional inference procedures in a permutation test framework. Retrieved from http://cran.r-project.org/web/packages/coin/coin.pdf

[14]

Jackson, D. (2010a). Phenotypic diversity in initial genetic programming populations. In Proceedings of the European Conference on Genetic Programming , pp. 98-109. Lecture Notes in Computer Science, Vol. 6021. Istanbul: Springer.

[15]

Jackson, D. (2010b). Promoting phenotypic diversity in genetic programming. In Parallel Problem Solving from Nature , pp. 472-481. Lecture Notes in Computer Science, Vol. 6239.

[16]

Kanji, G. (1999). 100 statistical tests . London: SAGE Publications.

[17]

Koza, J. R. (1992). Genetic programming: On the programming of computers by means of natural selection . Cambridge, MA: MIT Press.

[18]

Krawiec, K., and Lichocki, P. (2009). Approximating geometric crossover in semantic space. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) , pp. 987-994.

[19]

Krawiec, K., and Pawlak, T. (2013a). Approximating geometric crossover by semantic back-propagation. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) , pp. 941-948.

[20]

Krawiec, K., and Pawlak, T. (2013b). Locally geometric semantic crossover: A study on the roles of semantics and homology in recombination operators. Genetic Programming and Evolvable Machines , 14(1):31-63.

[21]

Looks, M. (2007). On the behavioral diversity of random programs. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) , pp. 1636-1642.

[22]

Luke, S. (2010). The ECJ owner's manual--A user manual for the ECJ Evolutionary Computation Library , zeroth edition, online version 0.2 edition. Retrieved from http://cs.gmu.edu/~eclab/projects/ecj/docs/manual/manual.pdf

[23]

Miller, B. L., and Goldberg, D. E. (1995). Genetic algorithms, tournament selection, and the effects of noise. Complex Systems , 9:193-212.

[24]

Moraglio, A. (2011). Abstract convex evolutionary search. In H.-G. Beyer and W. B. Langdon (Eds.), Foundations of genetic algorithms , pp. 151-162. Schwarzenberg, Austria: ACM.

[25]

Moraglio, A., Krawiec, K., and Johnson, C. G. (2012). Geometric semantic genetic programming. In Parallel Problem Solving from Nature , pp. 21-31. Lecture Notes in Computer Science, Vol. 7491.

[26]

Moraglio, A., and Mambrini, A. (2013). Runtime analysis of mutation-based geometric semantic genetic programming for basis functions regression. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) , pp. 989-996.

[27]

Moraglio, A., Mambrini, A., and Manzoni, L. (2013). Runtime analysis of mutation-based geometric semantic genetic programming on Boolean functions. In Foundations of genetic algorithms , pp. 119-132, Adelaide, Australia: ACM.

[28]

Moraglio, A., McDermott, J., and O'Neill, M. (2014). Geometric semantic grammatical evolution. In Semantic Methods in Genetic Programming, Ljubljana, Slovenia . Workshop in Parallel Problem Solving from Nature 2014 conference.

[29]

Nguyen, Q. U., Nguyen, X. H., and O'Neill, M. (2009). Semantics based mutation in genetic programming: The case for real-valued symbolic regression. In Mendel'09 , pp. 73-91.

[30]

Nguyen, Q. U., Pham, T. A., Nguyen, X. H., and McDermott, J. (2016). Subtree semantic geometric crossover for genetic programming. Genetic Programming and Evolvable Machines , 17(1):25-53.

[31]

Pawlak, T. (2014). Combining semantically-effective and geometric crossover operators for genetic programming. In Parallel Problem Solving from Nature , pp. 454-464. Lecture Notes in Computer Science, Vol. 8672.

[32]

Pawlak, T. P. (2015). Competent algorithms for geometric semantic genetic programming. PhD thesis, Poznan University of Technology, Poznan, Poland.

[33]

Pawlak, T. P. (2016). Geometric semantic genetic programming is overkill. In Proceedings of the European Conference on Genetic Programming , pp. 246-260. Lecture Notes in Computer Science, Vol. 9594.

[34]

Pawlak, T. P., and Krawiec, K. (2016a). Progress properties and fitness bounds for geometric semantic search operators. Genetic Programming and Evolvable Machines , 17(1):5-23.

[35]

Pawlak, T. P., and Krawiec, K. (2016b). Semantic geometric initialization. In Proceedings of the 19th European Conference on Genetic Programming , pp. 261-277. Lecture Notes in Computer Science, Vol. 9594.

[36]

Pawlak, T. P., Wieloch, B., and Krawiec, K. (2015a). Review and comparative analysis of geometric semantic crossovers. Genetic Programming and Evolvable Machines , 16(3):351-386.

[37]

Pawlak, T. P., Wieloch, B., and Krawiec, K. (2015b). Semantic backpropagation for designing search operators in genetic programming. IEEE Transactions on Evolutionary Computation , 19(3):326-340.

[38]

Uy, N. Q., Hoai, N. X., O'Neill, M., McKay, R. I., and Galvan-Lopez, E. (2011). Semantically-based crossover in genetic programming: Application to real-valued symbolic regression. Genetic Programming and Evolvable Machines , 12(2):91-119.

[39]

Uy, N. Q., Hoai, N. X., O'Neill, M., McKay, R. I., and Phong, D. N. (2013). On the roles of semantic locality of crossover in genetic programming. Information Sciences , 235:195-213.

[40]

Vanneschi, L., Castelli, M., Manzoni, L., and Silva, S. (2013). A new implementation of geometric semantic GP and its application to problems in pharmacokinetics. In Proceedings of the 16th European Conference on Genetic Programming , pp. 205-216. Lecture Notes in Computer Science, Vol. 7831.

[41]

Vanneschi, L., Castelli, M., and Silva, S. (2014). A survey of semantic methods in genetic programming. Genetic Programming and Evolvable Machines , 15(2):195-214.

[42]

Wieloch, B. (2013). Semantic extensions for genetic programming. PhD thesis, Poznan University of Technology.

[43]

Wieloch, B., and Krawiec, K. (2013). Running programs backwards: Instruction inversion for effective search in semantic spaces. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) , pp. 1013-1020.

[44]

Zhu, Z., Nandi, A. K., and Aslam, M. W. (2013). Adapted geometric semantic genetic programming for diabetes and breast cancer classification. In IEEE International Workshop on Machine Learning for Signal Processing .

Cited By

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
Shi XMinku LYao X(2024)Tree-Based Genetic Programming for Evolutionary Analog Circuit with Approximate Shapley ValueArtificial Intelligence XLI10.1007/978-3-031-77915-2_18(253-267)Online publication date: 17-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-77915-2_18
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
Show More Cited By

Recommendations

Review and comparative analysis of geometric semantic crossovers

This paper provides a structured, unified, formal and empirical perspective on all geometric semantic crossover operators proposed so far, including the exact geometric crossover by Moraglio, Krawiec, and Johnson, as well as the approximately geometric ...
Self-tuning geometric semantic Genetic Programming

The process of tuning the parameters that characterize evolutionary algorithms is difficult and can be time consuming. This paper presents a self-tuning algorithm for dynamically updating the crossover and mutation probabilities during a run of genetic ...
Geometric semantic genetic programming for recursive boolean programs
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

Geometric Semantic Genetic Programming (GSGP) induces a unimodal fitness landscape for any problem that consists in finding a function fitting given input/output examples. Most of the work around GSGP to date has focused on real-world applications and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Evolutionary Computation

Evolutionary Computation Volume 26, Issue 2

Summer 2018

166 pages

ISSN:1063-6560

EISSN:1530-9304

Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 June 2018

Published in EVOL Volume 26, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
58
Total Downloads

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

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

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
Shi XMinku LYao X(2024)Tree-Based Genetic Programming for Evolutionary Analog Circuit with Approximate Shapley ValueArtificial Intelligence XLI10.1007/978-3-031-77915-2_18(253-267)Online publication date: 17-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-77915-2_18
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
Vitel DGaspar AWagner M(2022)Analysis of neutral rewrite operator effects on arithmetic domainProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3534024(2334-2337)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3534024
Jeong HKim JChoi SLee SHeo IKim K(2022)Semantic Cluster Operator for Symbolic Regression and Its ApplicationsAdvances in Engineering Software10.1016/j.advengsoft.2022.103174172:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.advengsoft.2022.103174
Liang JXue Y(2021)Multi-Objective Memetic Algorithms with Tree-Based Genetic Programming and Local Search for Symbolic RegressionNeural Processing Letters10.1007/s11063-021-10497-853:3(2197-2219)Online publication date: 9-Apr-2021
https://dl.acm.org/doi/10.1007/s11063-021-10497-8
Nicolau MAgapitos A(2021)Choosing function sets with better generalisation performance for symbolic regression modelsGenetic Programming and Evolvable Machines10.1007/s10710-020-09391-422:1(73-100)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s10710-020-09391-4
Hodan DMrazek VVasicek ZCoello Coello C(2020)Semantically-oriented mutation operator in cartesian genetic programming for evolutionary circuit designProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390188(940-948)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390188

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents