基于归一分解的并行多目标Dividing Rectangles算法

• 全文链接
• 请求原文

作   者：

李晨;  陈逸东;  陆忠华;  杨雪莹;  王子田;  迟学斌; 

作者机构：

北京智速科技有限公司;  中国科学院计算机网络信息中心; 

关键词：

目标空间分解;  全局优化;  多目标优化;  并行计算;  Dividing Rectangles算法; 

期刊名称：

计算机研究与发展

i s s n：

1000-1239

年卷期：

2024 年 61 卷 011 期

页   码：

2909-2922

摘   要：

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