面向子模约束优化的多目标演化学习理论与方法研究

In many machine learning tasks, optimization usually comes with constraints, which must be satisfied by the final solutions. Thus, how to effectively solve constrained optimization problems is an important research direction in machine learning. Recently, by treating the constraint violation degree as another explicit minimization objective, multi-objective evolutionary algorithms (MOEAs) have been applied to solve some constrained optimization problems in machine learning. However, due to the weak theoretical foundation of MOEAs, the development of multi-objective evolutionary learning has been hindered greatly. This project first studies one of the most important theoretical problems of MOEAs, the computational complexity analysis. Particularly, it proposes to develop a general approach for the computational complexity analysis of MOEAs. According to the theoretical results, this project then proposes to study the design of multi-objective evolutionary learning methods with theoretical guarantee. Particularly, for the submodular constrained optimization problem which has wide applications in machine learning, it is to develop effective MOEAs with theoretical guarantee, and further parallelize the proposed MOEAs to make the computational complexity decrease linearly with the number of processors and the quality of the produced solution keep unchanged. It is expected to publish 4-6 papers in “IEEE Trans.” level international journals, conferences and domestic top journals, apply 1-2 patents, and supervise multiple graduate students.

在许多现实的机器学习任务中，往往要求优化某个目标的同时，所找到的解要满足一定的约束条件，因此，有效地进行约束优化是机器学习领域的一个重要研究方向。近年来，通过把对约束条件的违反程度视为另一个优化目标，多目标演化算法开始被用于求解机器学习中的一些约束优化问题，但由于其理论基础较为薄弱，多目标演化学习技术的发展受到了阻碍。本项目首先围绕多目标演化算法的计算复杂度分析这一核心理论问题进行研究，提出一种针对多目标演化算法计算复杂度的一般分析方法。在理论结果的基础上，本项目针对在机器学习中有广泛应用的两类子模约束优化问题，分别提出计算复杂度有理论保证的多目标演化算法，并对其并行化，使计算复杂度线性下降的同时性能保持不变。计划在 IEEE Trans 级别国际期刊和会议、国内一级学报发表论文4-6篇，申请专利1-2项，培养2-3名研究生。

本项目围绕面向子模约束优化的多目标演化学习理论与方法开展研究，旨在研究多目标演化算法的基础理论，并在理论结果的指导下，针对在机器学习中具有广泛应用的子模约束优化问题设计安全且高效的多目标演化学习算法。项目主要研究内容包括多目标演化算法的计算复杂度分析、面向子模约束优化的安全多目标演化算法、面向大规模子模约束优化的高效多目标演化算法。通过开展本项目，项目组提出了分析多目标演化算法计算复杂度的通用方法；针对各种子模约束优化问题，提出了性能带理论保证的多目标演化算法，证明出它们均能获得目前已知的最佳多项式时间近似保证；针对子模约束优化的大规模应用场景，提出了并行多目标演化算法，可获线性加速比。在此基础上，项目组共发表论文21篇，其中IEEE Transactions级别期刊或CCF A类会议论文17篇，项目负责人入选“中国科协青年人才托举工程”，培养硕士研究生2人。