Information Fusion in Offspring Generation: A Case Study in Gene Expression Programming

Tonglin Liu, Hengzhe Zhang, Hu Zhang, Aimin ZhouIEEE Access 2020 · OpenReview

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).

An expression tree representing the mathematical function (B-1)+A.

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 linear chromosome representation of the expression tree, illustrating the division into Head and Tail sections.

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

  1. 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.
  2. 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.
  3. 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

Abstract

Gene expression programming (GEP), which is a variant of genetic programming (GP) with a fixed-length linear model, has been applied in many domains. Typically, GEP uses genetic operators to generate offspring. In recent years, the estimation of distribution algorithm (EDA) has also been proven to be efficient for offspring generation. Genetic operators such as crossover and mutation generate offspring from an implicit model by using the individual information. By contrast, EDA operators generate offspring from an explicit model by using the population distribution information. Since both the individual and population distribution information are useful in offspring generation, it is natural to hybrid EDA and genetic operators to improve the search efficiency. To this end, we propose a hybrid offspring generation strategy for GEP by using a univariate categorical distribution based EDA operator and its original genetic operators. To evaluate the performance of the new hybrid algorithm, we apply the algorithm to ten regression tasks using various parameters and strategies. The experimental results demonstrate that the new algorithm is a promising approach for solving regression problems efficiently. The GEP with hybrid operators outperforms the original GEP that uses genetic operators on eight out of ten benchmark datasets.
BibTeX
@inproceedings{liu2020information,
  author = {Tonglin Liu and Hengzhe Zhang and Hu Zhang and Aimin Zhou},
  title = {{Information Fusion in Offspring Generation: A Case Study in Gene Expression Programming}},
  booktitle = {IEEE Access},
  year = {2020},
  url = {https://openreview.net/forum?id=HdKzbZvURe},
}
Figure