Surrogate-Assisted Flip for Evolutionary High-Dimensional Multiobjective Feature Selection

Feature selection (FS), which aims to minimize the classification error and the number of selected features, can essentially be modeled as a multiobjective optimization problem. To deal with such multiobjective FS (MOFS) problems, many multiobjective evolutionary algorithms (MOEAs) have been proposed. These MOEAs can find multiple optimal solutions, whereas substantial computational resources are required for fitness evaluations (FEs). More seriously, due to the high dimensionality and sparsity of FS problems, many FEs will be spent on unpromising solutions, resulting in a meaningless loss of computational resources. In this paper, two innovations are made so as to improve the performance of MOEAs for MOFS. First, we propose a surrogate-assisted flip (SF) strategy for MOEAs to reduce the FE waste on potentially unpromising solutions and improve search efficiency. This SF strategy is free of FE consumption and theoretically can be embedded in any MOEA to deal with MOFS problems. The experimental results show that this SF can improve the performance of different MOEAs, especially in reducing the number of selected features. Second, based on SF, we propose a more efficient SF -assisted MOEA for dealing with high-dimensional MOFS problems. The proposed algorithm divides the whole search space into different subspaces based on redundant feature subsets clustering to achieve parallel search, so as to reduce the search difficulty. The experimental results show that this algorithm is even more competitive than other SF -assisted MOEAs.