A Grammatical and Semantic Genetic Programming Technique for Symbolic Regression

• João Marcos de Freitas UFJF
• Heder Soares Bernardino UFJF
• Itamar Leite de Oliveira UFJF

DOI: https://doi.org/10.5753/eniac.2026.31240

Resumo

Symbolic Regression (SR) aims to automatically discover the underlying structure of mathematical models from data, a task frequently addressed using Genetic Programming (GP). While Grammatical Genetic Programming (GGP) successfully introduces necessary syntactic constraints to these models, its standard crossover operators often suffer from search inefficiency by strictly adhering only to derivation rules. Conversely, Semantic Genetic Programming (SGP) leverages semantic evaluations to effectively guide the evolutionary search. To bridge this gap, this paper proposes Grammatical and Semantic Genetic Programming (GSGP), an approach that integrates context-free grammars with semantic evaluations to guarantee both syntactic validity and behavioral relevance. A key contribution of this work is the Roulette Semantic Crossover (RSC), a recombination operator that applies proportional roulette wheel selection based on the inverse semantic distance between candidate subtrees. On a suite of ten classical symbolic-regression functions, RSC attained the largest area under the Performance Profile curves and the highest overall success count among the operators compared, indicating robustness on this set rather than uniform dominance of the final error.

Referências

Barbosa, H. J. C., Bernardino, H. S., and Barreto, A. M. S. (2010). Using performance profiles to analyze the results of the 2006 CEC constrained optimization competition. In Proc. of the Congress on Evolutionary Computation (CEC), pages 1–8. IEEE.

Bongard, J. and Lipson, H. (2007). Automated reverse engineering of nonlinear dynamical systems. Proceedings of the National Academy of Sciences, 104(24):9943–9948.

Cheng, X., Khomtchouk, B., Matloff, N., and Mohanty, P. (2019). Polynomial regression as an alternative to neural nets.

de Freitas, J., Bernardino, H., Guerreiro, J., and Barbosa, H. (2015). Aplicação de uma programação genética gramatical multiobjetivo na inferência da máxima deformação longitudinal de dutos com amassamento. In Proc. of the Iberian Latin American Congress on Computational Methods in Engineering (CILAMCE).

Dolan, E. D. and Moré, J. J. (2002). Benchmarking optimization software with performance profiles. Math. Program., 91(2):201–213.

Forstenlechner, S. (2019). Program Synthesis with Grammars and Semantics in Genetic Programming. PhD thesis, University College Dublin, Ireland.

Huang, H.-H. and He, Q. (2023). Nonlinear regression analysis, page 558–567. Elsevier.

Juvekar, K. and Purwar, A. (2024). Cos-mix: Cosine similarity and distance fusion for improved information retrieval.

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

Langford, J. (2005). The Cross Validation Problem, page 687–688. Springer Berlin Heidelberg.

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

McPhee, N. F., Ohs, B., and Hutchison, T. (2008). Semantic Building Blocks in Genetic Programming, page 134–145. Springer Berlin Heidelberg.

Mukherjee, S. and Sonal, R. (2023). A reconciliation between cosine similarity and euclidean distance in individual decision-making problems. Indian Economic Review, 58(2):427–431.

Nguyen, Q. U., Nguyen, X. H., and O’Neill, M. (2009). Semantic Aware Crossover for Genetic Programming: The Case for Real-Valued Function Regression, page 292–302. Springer Berlin Heidelberg.

Orzechowski, P., La Cava, W., and Moore, J. H. (2018). Where are we now?: a large benchmark study of recent symbolic regression methods. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’18. ACM.

Schmidt, M. and Lipson, H. (2009). Distilling free-form natural laws from experimental data. Science, 324(5923):81–85.

Uy, N. Q., Hoai, N. X., O’Neill, M., McKay, R. I., and Galván-López, E. (2010). Semantically-based crossover in genetic programming: application to real-valued symbolic regression. Genetic Programming and Evolvable Machines, 12(2):91–119.