Genetic programming (GP) has achieved promising performance in image classification. However, GP-based methods usually require a long computation time for fitness evaluations, posing a challenge to real-world applications. Surrogate models can be efficiently computable approximations of expensive fitness evaluations. However, most existing surrogate methods are designed for evolutionary computation techniques with a vector-based representation consisting of numerical values, thus cannot be directly used for GP with a tree-based representation consisting of functions/operators. The variable sizes of GP trees further increase the difficulty of building the surrogate model for fitness approximations. To address these limitations, we propose a new surrogate-assisted GP approach including global and local surrogate models, which can accelerate the evolutionary learning process and achieve competitive classification performance simultaneously. The global surrogate model can assist GP in exploring the entire search space, while the local surrogate model can speed up convergence and further improve performance. Furthermore, a new surrogate training set is constructed to assist in establishing the relationship between the GP tree and its fitness, and effective surrogate models can be built accordingly. Experimental results on ten datasets of varying difficulty show that the new approach significantly reduces the computational cost of the GP-based method without sacrificing the classification accuracy. The comparisons with other state-of-the-art methods also demonstrate the effectiveness of the new approach. Further analysis reveals the significance of the global and local surrogates and the new surrogate training set on improving or maintaining the performance of the proposed approach while reducing the computational cost.
