李晨, 陈逸东, 陆忠华, 杨雪莹, 王子田, 迟学斌. 基于归一分解的并行多目标Dividing Rectangles算法[J]. 计算机研究与发展.
 引用本文: 李晨, 陈逸东, 陆忠华, 杨雪莹, 王子田, 迟学斌. 基于归一分解的并行多目标Dividing Rectangles算法[J]. 计算机研究与发展.
Li Chen, Chen Yidong, Lu Zhonghua, Yang Yueying, Wang Zitian, Chi Xuebin. A Parallel Multi-Objective Dividing Rectangles Algorithm Based on Normalized Decomposition[J]. Journal of Computer Research and Development.
 Citation: Li Chen, Chen Yidong, Lu Zhonghua, Yang Yueying, Wang Zitian, Chi Xuebin. A Parallel Multi-Objective Dividing Rectangles Algorithm Based on Normalized Decomposition[J]. Journal of Computer Research and Development.

## A Parallel Multi-Objective Dividing Rectangles Algorithm Based on Normalized Decomposition

• 摘要: 多目标优化问题普遍存在且难以解决，目前多采用多目标进化算法进行求解. 然而，这些方法通常在种群初始化阶段和进化过程中包含随机操作以保持多样性，导致了其结果不可复现且缺乏全局收敛的理论保证. 鉴于此，提出了一种基于归一分解的多目标Dividing Rectangles算法，首先通过一种可较好捕捉复杂前沿的归一分解方法将原问题分解为一系列子问题，以降低问题计算复杂度；其次，采用Dividing Rectangles算法同时优化分解得到的子问题，并在优化过程中基于全局关联机制将生成的候选解分配给相应的子问题，以更好地保留优秀候选解并提高算法搜索效率；最后，证明了算法的收敛性. 此外，为了进一步提高计算效率，提出了一种基于自适应关联迁移策略的多层次多粒度并行方案，并基于该方案对所提出的算法进行了并行化. 将所提算法应用于多个基准优化问题，实验结果表明，相比于NSGA-II，所提串行算法能够产生收敛性、多样性更为优越的帕累托最优解集，并行算法可在大规模缩短问题求解时间的同时，进一步提升帕累托前沿近似精度.

Abstract: Multi-objective optimization problems are common in real-world applications. However, the high computational complexity severely hinders their solution. Currently, multi-objective evolutionary algorithms are mostly used for their solving. Nevertheless, these methods usually contain random operations in the process of population initialization and evolution to maintain diversity, which leads to non-reproducibility and lacking the theoretical guarantee of global convergence. Therefore, a novel multi-objective Dividing Rectangles algorithm is introduced based on decomposition strategy. In this algorithm, the original problem is decomposed into a series of subproblems by a normalized decomposition method that can better capture the complex frontier to reduce the computational complexity of the problem. Meanwhile, the Dividing Rectangles algorithm is used to simultaneously optimize the decomposed subproblems, and the generated candidate solutions are assigned to the corresponding subproblems based on the global association mechanism in the optimization process to better retain the good candidate solutions and improve the algorithm search efficiency. Finally, the convergence of the algorithm is demonstrated. To further improve the computational efficiency, a multi-level and multi-granularity parallel scheme based on the adaptive associative migration strategy is proposed, based on which the proposed algorithm is parallelized. Furthermore, the proposed algorithm and its parallel version are applied to several benchmark optimization problems, and the experimental results show that the proposed algorithm can obtain a Pareto set with better convergence and diversity than NSGA-II, and the parallel version can further improve the accuracy of Pareto frontier approximation while massively reducing the problem-solving time.

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈