Iterative genetic programming builds feature subsets for high-dimensional classification

High-dimensional data have become the defining challenge of modern machine learning, and a team of researchers in China has now unveiled a new evolutionary algorithm that promises to make sense of the overwhelming number of variables found in gene expression studies, financial datasets, and other domains where thousands of features must be distilled into a handful of genuinely informative signals. The method, called a multi-tree and multi-strategy iterative genetic programming algorithm, or MMSGP, is described in a study published in the journal Applied Intelligence. Its central achievement is a substantial improvement in classification accuracy across twelve high-dimensional benchmark datasets, outperforming five established baseline methods on most of them, while simultaneously tackling three long-standing weaknesses of genetic programming when applied to data with enormous feature counts.

The problem MMSGP addresses is deceptively simple to state but notoriously difficult to solve. High-dimensional data, such as microarray gene expression profiles that may contain tens of thousands of genes measured across only a few hundred samples, are riddled with redundancy, sparsity, and nonlinear relationships. Most individual features carry little discriminative power on their own, and the relationships that matter are often hidden in complex interactions among variables. Machine learning models trained directly on such data suffer from the curse of dimensionality: they overfit, they train slowly, and they generalize poorly. Dimensionality reduction is therefore essential, and two broad families of techniques exist. Feature extraction methods, such as principal component analysis and locally linear embedding, transform the original variables into new synthetic dimensions, but the resulting features are difficult to interpret. Feature selection methods retain original features, preserving interpretability, but they cannot capture interactions that only emerge when features are combined.

Genetic programming offers a third path. Inspired by biological evolution, it evolves populations of tree-structured computer programs, in this case mathematical expressions that combine original features with arithmetic or logical operators to construct entirely new, discriminative features. Because these constructed features are explicit formulas, they remain interpretable, a property that has made genetic programming increasingly attractive in the era of explainable artificial intelligence. Yet when the number of candidate features is huge, standard genetic programming stumbles. The authors of the new study identify three specific failure modes. First, the random selection of terminal nodes, the leaves of the evolving trees that represent individual features, produces large numbers of low-quality individuals in the initial population, wasting computational effort on expressions built from noisy or irrelevant variables. Second, fixed evolutionary strategies, meaning a single unchanging set of selection, crossover, and mutation operators, limit the algorithm’s ability to discover genuinely informative features as the search progresses. Third, the vast search space itself demands an effective dimensionality reduction mechanism, without which the evolutionary process wanders through a combinatorial labyrinth.

MMSGP responds to each of these challenges with a dedicated mechanism. The first innovation is a feature-importance-based terminal node selection. Rather than choosing features at random when building the leaves of program trees, the algorithm consults a measure of each feature’s importance, derived from the kind of scoring used in tree-based ensemble models, and biases the initial population toward features that already show evidence of relevance to the classification task. This simple change dramatically improves the average quality of individuals in the population from the very first generation, giving evolution a stronger starting point and reducing the number of useless programs that must be culled in early rounds.

The second innovation is a triple iterative strategy that governs how the population evolves over time. Instead of relying on one fixed evolutionary recipe, the algorithm cycles through three complementary strategies, each emphasizing a different aspect of the search: one promotes exploitation of currently promising individuals, another encourages exploration of under-visited regions of the feature space, and a third balances the two by maintaining population diversity. By iterating among these strategies, the algorithm avoids the premature convergence that plagues single-strategy evolutionary methods, in which the population collapses onto a mediocre solution early and never recovers. The authors report that this iterative guidance effectively steers the search toward informative feature combinations that fixed strategies tend to miss.

The third pillar of MMSGP is a dynamic dual-subset feature selection mechanism designed to tame the search space itself. The algorithm adaptively partitions the available features into two subsets, one containing features judged especially valuable for constructing discriminative expressions and the other holding the remainder. As evolution proceeds, the composition of these subsets is updated dynamically in response to which features the evolving programs actually use and how well the constructed features perform. By concentrating computational attention on the valuable subset while still allowing occasional excursions into the broader pool, the mechanism reduces the effective dimensionality the algorithm must navigate at any given moment, cutting computational cost without sacrificing the diversity needed to find unexpected feature interactions.

The empirical case for MMSGP rests on experiments across twelve high-dimensional datasets drawn from the kinds of applications where dimensionality is most punishing, including gene expression data and other domains characterized by sparse, redundant, nonlinear variables. The authors compared MMSGP against five baseline methods, and the results were decisive. MMSGP achieved higher average balanced classification accuracy than every baseline on nine of the twelve datasets, and it surpassed all of them in macro F1-score, a metric that accounts for both precision and recall across classes and is particularly informative when class distributions are imbalanced, on ten of the twelve datasets. Balanced accuracy and macro F1 were chosen deliberately because high-dimensional biomedical datasets frequently exhibit class imbalance, and ordinary accuracy can mask poor performance on minority classes.

To verify that the gains truly come from the proposed components rather than incidental tuning, the researchers conducted ablation studies, systematically removing or disabling individual parts of the algorithm and measuring the resulting performance drop. These experiments confirmed the contribution of each of the three core mechanisms: the feature-importance-based terminal selection, the triple iterative strategy, and the dynamic dual-subset feature selection. Removing any one of them degraded classification performance, indicating that the components are complementary rather than redundant, each addressing a distinct bottleneck in the evolutionary feature construction pipeline.

The significance of the work extends beyond its benchmark numbers. Unlike black-box dimensionality reduction, the features MMSGP constructs are symbolic expressions that a domain expert can read, dissect, and test. In cancer classification from microarray data, for example, an evolved expression combining the levels of a handful of genes might suggest a biologically meaningful interaction worth experimental follow-up, something a principal component could never offer. The authors and a growing body of literature on explainable artificial intelligence by genetic programming view this interpretability as a key advantage in domains such as biomedicine, where decisions must be transparent and auditable. The study also builds on a rich lineage of research, including earlier multi-tree genetic programming approaches for feature construction, multi-objective evolutionary methods for high-dimensional classification, and hybrid schemes combining filters with genetic algorithms, positioning MMSGP as a synthesis that corrects the specific weaknesses of its predecessors.

The research was carried out by Chen Zhang, Zezhong Zhang, Youping Tu, Honghao Zhu, Xiaofeng Wang, and Xuhui Zhu, with affiliations spanning the School of Artificial Intelligence and Big Data at Hefei University, the State Key Laboratory for Novel Software Technology at Nanjing University, the Intelligent Interconnected Systems Laboratory of Anhui Province at Hefei University of Technology, and the School of Computer Science and Information Engineering at Bengbu University. The work was supported by the Fundamental Research Funds for the Central Universities of China, the National Key Laboratory of Computer Software Technology at Nanjing University, and the Program for Scientific Research Innovation Team in Colleges and Universities of Anhui Province. The datasets analyzed in the study are available from the corresponding author on reasonable request, and the implementation builds on established evolutionary computation tooling, including the widely used DEAP library for evolutionary algorithms in Python.

For practitioners, the arrival of MMSGP signals a maturing of evolutionary feature engineering for the high-dimensional era. Genetic programming has been applied to feature construction since the early 2000s, but its vulnerability to enormous feature spaces has kept it in the shadow of simpler filter and wrapper methods in many production settings. By demonstrating that intelligent initialization, adaptive multi-strategy evolution, and dynamic search-space narrowing can together lift evolutionary feature construction above five strong baselines on the majority of twelve challenging datasets, the study offers a template that other researchers can extend, whether toward multi-objective formulations that jointly optimize accuracy and feature count, toward integration with deep learning pipelines, or toward deployment on real-world clinical and financial data where the thousands of candidate variables are not an abstraction but the daily reality. As machine learning continues to confront datasets that dwarf the assumptions of classical algorithms, evolution, guided carefully and iteratively, is proving it still has a great deal to teach.