Semantic valued schema theory of genetic programming in symbolic regression

Abstract Schema Theory offers a principled lens for analyzing the dynamics of Evolutionary Algorithms (EAs), yet its extension to Genetic Programming (GP) is obstructed by the nonlinear structure of GP trees and the irregular correspondence between syntax and semantics. These characteristics prevent classical, structure-based schema formulations from capturing the mechanisms that determine how information is preserved, disrupted, and propagated during GP evolution. Motivated by the significant role of semantics in GP, this study introduces Valued Schema Theory (VST), which characterizes a schema through both its semantic output and the quantity of effective genetic material it carries. Beyond providing a semantic definition of schemata, the proposed theory models the flow of value through GP populations. It describes schema dynamics through a pessimistic survival inequality that integrates selection pressure, crossover-induced structural disruption, and the differing robustness of significant meaning and zero-valued regions. This formulation yields a tractable account of how meaningful information spreads while non-informative regions function as protective buffers. The novelty of VST lies in redefining schema as a semantic-valued unit characterized by output behavior and effective semantic material, while preserving the disruption-centered form of pessimistic schema analysis to maintain the explainability of Building Blocks. Empirical evaluation across four representative benchmark tasks covering Boolean regression, numerical symbolic regression, and symbolic-regression-like classification shows that VST achieves consistently high accuracy in predicting schema-frequency transitions. These results indicate that VST captures the microscopic mechanisms through which semantic information is redistributed during GP evolution, providing a coherent account of GP’s underlying search dynamics.