Semantic-aware Surrogate-assisted Genetic Programming for Feature Construction in Classification

Feature construction is a crucial preprocessing technique in machine learning tasks, which aims at constructing high-level features to improve the performance of learning algorithms. Genetic Programming (GP) is widely used in feature construction tasks due to its flexible representation and powerful search capabilities. Preselection strategy holds promise for enhancing the performance of evolutionary algorithms. It seeks to preselect better individuals prior to fitness evaluation in order to improve population quality. However, since GP individuals are represented as non-numeric programs, it is challenging to accurately assess whether an individual is promising. This paper introduces a semantic-aware surrogate-assisted method aimed at enhancing the efficiency of GP in feature construction. We first defined the semantics of multi-tree GP and propose three distance metrics to measure similarity between individuals. A KNN-based surrogate model is developed to estimate the performance of candidate individuals. Furthermore, a dynamic preselection strategy is proposed to identify promising individuals from the generated candidates. Experimental results on 10 classification datasets demonstrate significant performance advantages of the proposed method over three GP-based feature construction methods. Further experiments demonstrated the value of the proposed surrogate-assisted method and its key components.