基于无导数凸二次逼近的多目标进化算法研究

In recent years, the development of multiobjective evolutionary algorithms have the trends that driven by problem features and the integration of advanced optimization methods. Convex quadratic approximation is a popular local search method. Within the decomposition-based framework, this project aims at studying the convex quadratic approximation in multiobjective evolutionary algorithms for solving various multiobjective problems with difficult features. The main research tasks include: (1) develop efficient multiobjective evolutionary algorithms based on 1-D convex quadratic approximation and diversity strategies for global optimization; (2) apply high-dimensional convex quadratic approximation for speeding up the convergence of interactive multiobjective evolutonary algorithms towards local part of Pareto front， which is suitable for many-objective optimizatoin; (3) study multiobjective evolutionary algorithms with groups by combing randomized convex quadratic approximation for multiobjective optimization problems with bias; (4) investigate the construction of sparse hessian matrix by sparse optimization methods for dealing with large-scale multiobjective optimizaiton problems with many variables. This project expects to develop various convex quadratic approximation for local search in the area of multiobjective optimization.

近年来，多目标进化算法研究呈现出以问题特性驱动设计算法及耦合高级单目标优化技术的趋势。凸二次逼近技术是当前一种流行的无导数局部加速方法。本项目在基于分解算法的框架下，深入研究凸二次逼近方法对多目标进化算法的加速策略，以解决各类具有复杂特征的多目标优化问题。主要包括：(1) 结合各种多样性策略，研究基于一维凸二次逼近方法的多目标进化算法，实现针对多极值多目标优化问题全局寻优；(2) 应用确定高维二次逼近方法对多目标进化算法进行加速，以实现对交互式算法中偏好解的高效逼近, 这类方法适用于超多目标优化问题；(3) 结合随机凸二次加速方法，研究基于分解的分组多目标进化算法，主要针对带Bias特征的多目标优化问题；(4) 利用稀疏优化技术构造具有稀疏性结构的凸二次模型, 以解决变量维数高或函数值评估代价高的多目标优化问题。项目期待利用凸二次逼近设计出能够处理各种复杂多目标问题的高效多目标进化算法。

基于问题特征设计优化算法是进化计算研究领域的主要算法设计指导原则。为弥补进化计算收敛速度的不足，采用传统优化方法进行加速是一种有效的策略。为降低算法的复杂性，采用基于凸二次模型的加速方法是一种简单可行的策略。本项目在基于分解算法的框架下，结合凸二次逼近方法对多目标进化算法的加速策略，以解决各类具有复杂特征的多目标优化问题。主要成果包括: (1) 针对具有偏置类型的多目标问题, 结合随机凸二次模型CMA-ES提出了MOEA/D-CMA算法; (2) 针对退化以及复杂形状帕雷托前沿问题, 提出了基于单变量二次模型加速的MOEA/D改进算法; (3) 针对稀疏重构问题, 结合二次阈值迭代算法提出了基于偏好的MOEA/D分解算法; (4) 针对变维度优化问题, 结合双层分解技术提出了MOEA/D-VLP算法。针对以上几种类型问题，基于凸二次加速技术的新算法明显优于现有的多目标进化算法。