高维多目标进化算法分析与设计

In recent years, many-objective evolutionary algorithms (MaOEAs) have drawn much attention in the field of evolutionary algorithms, but their theoretical research lags far behind algorithm design and application. In this project, we mainly study the time complexity and convergence rate of MaOEAs. For some popular MaOEAs (such as MOEA/D, NSGA-III), many-objective quasi-boolean functions and combinatorial optimization problem instances (such as SAT problem, 0-1 knapsack problem) can be constructed and generated according to certain probability distributions. Then, the time complexity or convergence order of MaOEAs on these problems will be analyzed. Next, we study the effect and influence of algorithmic parameters and variables. By combining the theory study with the algorithm design, new improved MaOEAs with high efficiency and simplicity can be designed. The research of this project helps to establish the basic theory of MaOEAs, and to facilitate a deeper understanding of their working principle. Moreover, it can build a bridge between the theoretical study and algorithm design.

近年来，高维多目标进化算法在进化算法研究领域非常活跃，但其理论研究远远落后于算法设计和应用。本项目研究高维多目标进化算法的时间复杂性和收敛速率等，针对流行的高维多目标进化算法（如MOEA/D、NSGA-III等），构造高维多目标拟布尔函数和组合优化问题实例（如SAT问题、0-1背包问题等），并依概率分布生成一些高维多目标组合优化问题，分析高维多目标进化算法关于这些问题的计算时间或收敛阶；研究算法参数和变量的作用和影响等。将理论研究策略和结果与算法设计有机结合，设计出简单高效的新的改进高维多目标算法。本项目研究有助于建立高维多目标进化算法基础理论，更好地理解算法的工作原理，以及在算法理论研究和算法设计之间建立联系的桥梁。

项目研究了高维多目标演化算法的时间复杂度，针对当前多目标演化算法难以处理具有复杂Pareto Front (PF)的高维多目标优化问题，例如，混合的PF、退化的PF、不连续的PF等，项目提出了一系列自适应的演化算法来处理此类复杂问题。具体地，在算法设计工作中，本项目重点关注演化算法组件的设计和改进，例如，新颖的选择算子、动态进化策略、混合算法等。在演化理论分析工作中，重点分析了演化多目标算法（如MOEA/D等）的时间复杂性等，并分析了算法参数、变异算子以及分解方法等对收敛性能的影响。另外，本项目探究了演化高维多目标算法在求解实际问题时的效果，例如软件配置问题、基于偏好的软件设计、车辆定位路由问题等。本项目有机地结合了算法设计、理论分析和实际应用，加深了对高维多目标问题的认识，探究了演化算法的工作机理，在理论研究和算法设计之间建立了联系的桥梁，同时也扩展了高维多目标问题的实际应用范围。.整个项目期间的成果以学术论文为主，完成学术论文33篇期刊论文和5篇CCF推荐会议论文，其中包括31篇SCI论文、4篇CCF A类期刊论文和3篇CCF A类会议论文。本项目不仅设计了多个灵活性好、适用性强的多目标演化算法，填补了多个当前研究的空白，还具有广阔的应用前景，为求解实际的高维多目标问题提供了一组高效的工具箱。