A Theoretically Guaranteed Evolutionary Algorithm with Dual-Knowledge Integration for Subset Selection
提出一种集成先验适应度贡献和种群历史统计知识的进化算法，用于子集选择问题，在单调目标函数下达到1−e−γ近似保证，实验在稀疏回归和无监督特征选择中优于现有方法。
Evolutionary algorithms (EAs) have demonstrated excellent performance in many fields, yet their theoretical research remains relatively underdeveloped. As an important combinatorial optimization problem, subset selection provides a critical research avenue to advance the theoretical study of EAs. However, most existing studies focus on solving various variants of subset selection problems, lacking in-depth exploration of more knowledge used in evolutionary operators. This makes it difficult to design EAs that are both more effective and theoretically guaranteed. Therefore, we propose a theoretically guaranteed EA with dual-knowledge integration for subset selection (DKESS). The algorithm integrates two key types of knowledge: the prior fitness contribution knowledge and the population historical statistics knowledge, to comprehensively evaluate the importance of variables and guide the optimization process, thereby enhancing optimization performance with theoretical guarantees. Specifically, we construct a dual-knowledge integration strategy for assessing variable importance, based on which two novel operators are designed: the dual-knowledge guided crossover operator (DKC) and the dual-knowledge guided mutation operator (DKM). These two operators can be used to effectively identify and select high-value variables during the optimization process, thus facilitating the generation of better solutions. Furthermore, we theoretically prove that when the objective function is monotonic, DKESS can achieve the optimal approximation guarantee of 1 − e−γwithin polynomial time. Experimental results on two typical subset selection applications (i.e., sparse regression and unsupervised feature selection) demonstrate that the proposed DKESS outperforms state-of-the-art methods.