Abstract
Gene expression programming (GEP) is a prominent variant of genetic programming that utilizes a fixed-length linear model to represent complex mathematical expressions. While traditionally reliant on genetic operators like crossover and mutation, recent advancements have highlighted the potential of Estimation of Distribution Algorithms (EDA) for offspring generation. This paper proposes a hybrid offspring generation strategy ($GEP_H$) that fuses individual-level information from genetic operators with population-wide distribution information from a univariate categorical EDA. By implementing a fitness standardization step to stabilize the probabilistic model, the proposed approach addresses common pitfalls such as stochastic sampling drift. Experimental evaluations across ten regression benchmarks demonstrate that the hybrid strategy significantly enhances search efficiency, outperforming standard GEP in 80% of the tested cases.
Introduction: The Evolution of Symbolic Regression
Symbolic regression aims to discover the underlying mathematical structure of a dataset, providing interpretable models that contrast with the "black-box" nature of deep learning. Gene Expression Programming (GEP) has emerged as a robust framework for this task. However, the search process in standard GEP is often driven by "blind" genetic operators. While mutation and crossover are effective at maintaining population diversity and performing local searches, they do not explicitly leverage the statistical trends emerging within the population over successive generations.
Conversely, Estimation of Distribution Algorithms (EDA) offer a more systematic approach by building explicit probabilistic models of the most successful individuals. While EDA can be highly efficient, it is prone to local optima and "stochastic sampling drift," where the model prematurely converges on a suboptimal region of the search space. This research explores the fusion of these two paradigms, aiming to combine the robustness of genetic algorithms with the statistical guidance of EDA.
Methodology: Fusing Individual and Population Information
The core of the proposed $GEP_H$ algorithm is a hybrid strategy that partitions the offspring generation process. In each generation, a portion of the new population is created via traditional genetic operators, while the remainder is sampled from a learned probabilistic model.
GEP Representation
To understand how EDA is integrated, one must first consider the structure of GEP. GEP individuals are represented as fixed-length linear chromosomes, which are then translated into expression trees (ETs).
These trees are encoded into a linear string consisting of a "Head" and a "Tail." The Head can contain both functions (e.g., +, -, *) and terminals (variables or constants), while the Tail is restricted to terminals to ensure that any randomly generated or mutated string can be validly mapped back to a tree structure.
The EDA Component and Fitness Standardization
The EDA component in $GEP_H$ utilizes a univariate categorical distribution. It maintains a probability matrix where each entry $P_{i,j}$ represents the probability of a specific primitive $j$ (like a function or variable) appearing at position $i$ in the chromosome.
A critical challenge in hybridizing EDA with GEP is the varying scale of fitness values across different regression tasks. To prevent the probabilistic model from being skewed by extreme error values, the authors introduce a Fitness Standardization step. By mapping raw fitness values to a standard Gaussian distribution ($\mathcal{N}(0, 1)$), the algorithm ensures that model updates remain stable and consistent, regardless of the dataset's specific loss scale.
Experimental Evaluation
The researchers evaluated the hybrid approach using ten regression datasets from the Penn Machine Learning Benchmark (PMLB), covering a wide range of complexities (from 60 to over 8,000 instances and 4 to 22 features).
Key Findings
- The 10% EDA Ratio: Extensive parameter testing revealed that the optimal balance for offspring generation is approximately 10% EDA-derived and 90% GA-derived. This "10% Rule" suggests that EDA serves best as a specialized search booster, providing statistical direction without overwhelming the diversity-preserving mechanisms of traditional genetic operators.
- Performance Gains: The standardized hybrid model ($GEP_{HSP}$) achieved superior accuracy compared to the baseline GA-based GEP on 8 out of the 10 benchmark datasets.
- Convergence Speed: Analysis of training curves indicated that the hybrid models generally reached lower error thresholds significantly faster than the baseline, demonstrating improved search efficiency.
Conclusion and Future Directions
The fusion of individual-level genetic information and population-level statistical information represents a significant step forward for Gene Expression Programming. By stabilizing the EDA component through fitness standardization, $GEP_H$ provides a more robust and efficient tool for symbolic regression.
Future work will focus on addressing the "univariate assumption." Currently, the EDA model treats each gene position as independent, whereas mathematical expressions inherently involve deep dependencies between operators and their operands. Exploring more complex models, such as Bayesian networks, could capture these relationships and further enhance the algorithm's predictive power. Additionally, the development of adaptive mechanisms to automatically tune the EDA offspring ratio and learning rates during execution remains a high priority.
Summary updated