Improving the efficiency of GP-GOMEA for higher-arity operators

Thalea Schlender, Mafalda Malafaia, Tanja Alderliesten, Peter A. N. Bosman

Abstract

Symbolic Regression (SR) aims to discover human-readable mathematical expressions that fit data. GP-GOMEA is a state-of-the-art SR algorithm that uses fixed-size tree templates to prevent bloat. However, supporting high-arity operators (e.g., ternary if-then-else) requires large templates that lead to search inefficiencies. This paper introduces Semantic Subtree Inheritance (SSI) and Greedy Child Selection (GCS) to optimize the use of these templates. Experimental results on continuous and discontinuous Feynman benchmarks demonstrate that these enhancements significantly improve $R^2$ performance and search efficiency, especially in complex search spaces with higher-arity operators.

Introduction

In the field of explainable AI (XAI), Symbolic Regression (SR) is highly valued for producing "white-box" models. Unlike neural networks, SR outputs mathematical expressions that are inherently interpretable. A leading approach, GP-GOMEA, utilizes a fixed-size tree template to manage complexity and prevent uncontrolled growth (bloat).

However, a significant challenge arises when incorporating high-level operators, such as Gaussian functions or ternary if-then-else statements. To accommodate the maximum possible arity (number of children) at any node, the entire template must be expanded. This results in numerous "syntactic introns"—unused slots in the template when simpler operators (like addition) are selected. Standard GP-GOMEA ignores these slots, leading to a sparse and inefficient search process as the operator set grows.

Figure 1: Comparison between a standard expression tree (a) and a higher-arity 'Gaussian' operator (b) which simplifies the structure but requires a wider template.

Methods

To address these scalability issues, the authors propose three primary adaptations:

  1. Expanded Operator Set: Inclusion of Boolean logic (>, <, AND, OR) and the if-then-else operator to naturally model discontinuities and piece-wise functions.
  2. Semantic Subtree Inheritance (SSI): Unlike standard GOMEA, which swaps genetic material based on fixed template positions, SSI focuses on functional context. It allows a "good" subtree rooted with a specific operator (e.g., sin) to be transplanted into a recipient tree at any node using the same operator, regardless of its geometric position.
  3. Greedy Child Selection (GCS): GCS optimizes child assignment within the template. Instead of default positioning, it treats the arrangement of children as a mini-optimization problem, testing different combinations to find the configuration that yields the best fitness for a parent operator.

Experimental Evaluation

The proposed methods were evaluated using:

  • Feynman Equations: A standard benchmark of 100+ physics-derived symbolic regression problems.
  • Discontinuous Feynman Sets: A custom benchmark combining Feynman equations with Boolean logic and if-then-else statements to simulate complex piece-wise relationships.
  • Complexity Scaling: Tests spanned tree depths from 3 to 6 and operator set sizes from 4 to 22.

Results and Discussion

The enhancements demonstrated clear performance benefits, particularly as problem complexity increased. SSI and GCS generally improved $R^2$ metrics across all configurations, with the most significant gains observed in ternary configurations where the branching factor was 3.

Figure 4: Critical Difference (CD) plots using the Nemenyi test, showing the statistical superiority of SSI and GCS variants across different operator set sizes and arities.

Statistical analysis via the Nemenyi test confirmed that SSI was almost always beneficial. GCS was most effective when considering operators up to arity 2 within ternary templates. These improvements allow the algorithm to produce shallower, more interpretable trees by effectively utilizing higher-level operators rather than relying on deep, nested arithmetic approximations.

Conclusion

The introduction of Semantic Subtree Inheritance and Greedy Child Selection effectively mitigates the "intron problem" in GP-GOMEA. By prioritizing functional context over geometric position and optimizing child placement, these methods enable efficient search in high-arity spaces. Future work will explore partial inheritance and semantic inheritance for leaf nodes to further enhance convergence in real-world, high-dimensional datasets.

Summary updated

BibTeX
@inproceedings{schlender2024improving,
  author = {Thalea Schlender and Mafalda Malafaia and Tanja Alderliesten and Peter A. N. Bosman},
  title = {{Improving the efficiency of GP-GOMEA for higher-arity operators}},
  booktitle = {GECCO},
  year = {2024},
  doi = {10.1145/3638529.3654118},
}
Figure