博文

东北大学刘建昌教授团队丨基于指标和自适应分解的高维多目标进化算法

已有 357 次阅读 2026-6-22 09:10 |个人分类:论文推荐|系统分类:博客资讯

编辑荐语

本期将给大家分享"基于指标和自适应分解的高维多目标进化算法(A many-objective evolutionary algorithm based on indicator and adaptive decomposition)". 如您对本期相关内容有好的理解与建议, 欢迎评论区留言.

高维多目标优化问题广泛存在于工程设计与科学决策中, 然而现有基于分解的进化算法在面对不同类型Pareto前沿时往往顾此失彼, 综合性能显著下降. 本文精准瞄准这一核心困境, 提出一种基于指标和自适应分解的高维多目标进化算法(MaOEA-IAD). 该算法巧妙融合了三种创新设计: 其一, 构建一个实时维护的外部档案库, 用于保存有期望个体并挖掘潜在的前沿参考向量; 其二, 提出一种小生境技术与收敛性指标相结合的综合性能指标, 从而在同一框架下优雅地平衡种群的收敛性与多样性; 其三, 设计参考向量自适应策略与基于空间划分的精英替代策略, 使得算法能够动态调整搜索方向, 显著提升在真实Pareto前沿上的分散能力. 大量仿真实验表明, MaOEA-IAD在面对不同复杂类型的高维多目标问题时, 均能稳健地兼顾收敛性与多样性, 综合性能优于多种主流对比算法. 本工作为高维多目标优化提供了一条兼具理论洞见与实用价值的解决路径, 值得相关领域研究者深入研读与借鉴.

论文介绍

基于指标和自适应分解的高维多目标进化算法

A many-objective evolutionary algorithm based on indicator and adaptive decomposition

田瑾然, 刘建昌†, 张伟, 田家鑫, 刘圆超

机构: 东北大学信息科学与工程学院; 东北大学工业智能与系统优化国家级前沿科学中心

引用: 田瑾然, 刘建昌, 张伟, 等. 基于指标和自适应分解的高维多目标进化算法. 控制理论与应用, 2026, 43(5): 937 – 950

DOI: 10.7641/CTA.2025.40307

全文链接:

http://jcta.alljournals.ac.cn/cta_cn/ch/reader/view_abstract.aspx?file_no=CCTA240307&flag=1

摘要

针对基于分解的高维多目标进化算法在求解不同类型Pareto前沿的问题时综合性能下降的问题, 本文提出一种基于指标和自适应分解的高维多目标进化算法 (MaOEA-IAD). 首先, 设计一个实时维护的外部档案库来保留有期望个体, 以发现潜在的未开发但有前景的参考向量; 同时, 为了评价个体的收敛性和多样性, 提出一种小生境技术与收敛性指标相结合的综合性能指标I(x); 此外, 为了提升算法处理不同Pareto前沿问题时的综合性能, 提出一种参考向量自适应策略, 并与基于空间划分的精英替代策略相结合, 进一步提升算法在真实Pareto前沿上的分散能力. 实验结果表明, 所提算法能够在不同复杂类型的高维多目标优化问题上有效的平衡种群收敛性和多样性, 并具有一定的优越性.

引言

高维多目标优化问题(many-objective optimization problems, MaOPs)广泛存在于工程应用和科学研究领域, 例如工程设计优化[1]和智能医疗决策[2]等. 这些问题的数学描述如下所示:

min F(x) = (f1(x), f2(x), · · · , fm(x)),

s.t. x ∈ Ω,

其中: x = (x1, x2, · · · , xn)是n维的决策变量; F(x)是包含 m 个相互冲突的目标函数的目标向量, 且m> 3; fi(x)是第i个目标函数. 由于各目标之间的相互冲突特性, 不存在一个解可以使各目标同时达到最优[4]. 因此, 希望得到一组折衷解, 尽可能使各目标都达到最优. 这组解在决策空间中称为Pareto最优解集(pareto set, PS), 其所对应的目标函数值称为Pareto最优前沿(pareto front, PF).

多目标进化算法 (multi-objective evolutionary algorithms, MOEAs)具有强大的全局搜寻能力, 其最早被运用于求解多目标优化问题, 可以有效的搜寻出一组均匀分布的Pareto最优解[5] . 然而, 随着科学技术推动着各领域的发展, 越来越多的优化问题开始变得复杂, MOEAs不得不面对MaOPs[6] , 这直接导致传统的MOEAs的综合性能变差. 为了有效处理MaOPs, 研究者们开始对MOEAs的性能、鲁棒性和适应性做出进一步研究, 以设计出可以应用于不同复杂领域 MaOPs的高维多目标进化算法(many-objective evolutionary algorithms, MaOEAs), 并利用大量仿真实验分析MaOEAs 在处理 MaOPs 时的性能表现. 到目前为止, MaOEAs的相关研究工作主要集中在3个方面: 基于支配关系的MaOEAs、基于分解的MaOEAs和基于指标的MaOEAs.

1) 基于支配关系的MaOEAs.

随着优化问题中的目标个数增加, 大多数基于Pareto关系支配的MOEAs性能正在恶化. 因为种群中大多数个体在高维空间中都是互不支配的, 即使很多个体在大多数目标上表现优异, 这种现象被称为支配抵抗 (dominance resistance, DR[7]), 其显著降低了算法的选择压力, 减缓了收敛. 为了解决这个问题, 研究者们进行了许多尝试来改进基于Pareto优势的算法, 如: 集中修改或设计新的Pareto支配关系, 旨在增加个体相互支配的概率, 提升算法的收敛性. 例如, He等[8]利用模糊逻辑的概念设计了一种模糊Pareto支配关系, 并引入NSGA-II和SPEA2中, 实验表明该方法在解决MaOPs时, 比原算法拥有更好的收敛性和多样性; 随后Liu等[9]受到模糊支配的启发, 提出一种基于模糊预测的算法. Yang等[10]提出一种基于grid-dominance的MaOEAs, 通过对目标空间网格化来区分种群个体的相互关系. Tian等[11]提出一种基于小生境技术的强化支配关系, 该方法基于候选个体之间的角度设计了一种自适应聚类策略, 利用每个聚类中收敛性最好的个体作为新的非支配解. 此外, 还有一些新的支配方法, 如fractional-dominance[12], RP-dominance[13], RPS-dominance[14]及DR[15]支配等. 最近, Wang等[16]提出一种PRV-dominance, 该方法设计了一种新的基于目标函数值排序的度量来确定两个个体之间的支配关系, 以提高算法收敛速度.

2) 基于分解的MaOEAs.

基于分解的MaOEAs将MaOPs分解为多个子问题, 每个子问题的最佳候选者形成最终的解集. 该类算法的典型代表是Zhang等[17]提出的基于分解的多目标进化算法 (multiobjective evolutionary algorithm based on decomposition, MOEA/D), 其使用一组预定义的权重向量将MOPs分解成多个子问题, 并同时优化子问题. 结果表明MOEA/D不仅在MOPs上表现优异, 而且能够有效处理 MaOPs. 因此, 在MOEA/D的框架下许多变体算法被提出. 例如, Liu等[18]提出了一种新型的基于分解的多目标优化进化算法(a new version of multiobjective optimization evolutionary algorithm-based decomposition, MOEA/M2M), 它将多目标优化问题分解为一系列更简单的子问题, 然后以协同进化的方式求解它们. 基于非支配遗传算法-Ⅲ(non-dominated sorting genetic algorithm-Ⅲ, NSGA-Ⅲ) [19]对NSGA-II框架进行了改进, 加入了基于参考点的思想, 从而提高了NSGA-III在高维目标上的性能. Yuan 等[20]基于MOEA/D无法在高维空间中保持多样性, 利用解到目标空间中参考向量的垂直距离来维持进化过程中种群的多样性. 为了提高基于分解的算法的性能, Jiang等[21]提出了一种基于参考方向多样性优先的强度Pareto进化算法(strength pareto-based evolutionary algorithm based on reference direction, SPEA/R). 近期, Lucas等[22]受到聚类算法的启发, 提出算法一种基于分解的逆向建模多目标进化算法(an inverse modeling multiobjective evolutionary algorithm based on decomposition, IM-MOEA/D). 该算法使用k-Means聚类方法将种群划分为k个子种群, 然后将目标空间中的均匀样本映射到决策空间, 从而增强多样性.

3) 基于指标的MaOEAs.

基于指标的MaOEAs不同于以上两类算法, 其设计实现简单, 在环境选择中利用所设计的评价指标来衡量候选解的质量, 进而引导种群进化趋向于真实PF. 最早, Zitzler等[23]首次使用性能指标来主导环境选择操作, 提出了基于指标的进化算法(indicator-based evolutionary algorithm, IBEA), 该算法为研究者们设计MOEAs提供了一种新的思路. 随后, Beume等[24]提出基于超体积 (hypervolume, HV)指标的 MOEAs算法, 但是, 该算法在高维目标空间中计算HV指标值的成本呈指数增加. 为了减少在 MaOPs 上的计算成本, Bader等[25]利用 Monte Carlo近似估计法来近似计算HV值, 这种方法明显提高了 MOEAs 的计算效率. 目前基于指标的 MaOEAs 中主要使用到的性能指标还包括: R2指标[26]、Iε+指标[27]、IGD指标 [28]、IGD+指标[29]等. 在这些算法中, 选择对性能指标贡献较大的候选解.

基于分解的进化多目标算法的一个关键特性是生成种群解的质量很大程度上取决于给定问题的PF形状和设定参考向量之间是否一致. 只有当参考向量的分布与待解决问题PF形状一致时, 基于分解的多目标进化算法才能得到最好的结果[30] . 然而, 在处理不规则PF的高维多目标优化问题时, 预先设定一组均匀分布的参考向量可能导致Pareto最优解非均匀分布或者一些设定的参考向量与PF没有交集[31] . 这一问题的潜在解决方案就是寻求参考向量自适应的方法, 其可以在优化过程中逐渐修改权重向量[32–33] . 尽管目前一些基于自适应分解的进化算法对于处理不规则PF问题具有潜在优势, 但这个问题还远未解决. 第一, 预先设置的参考向量对于具有规则PF的多目标优化问题是理想的, 改变参考向量可能会损害算法本身在具有规则PF问题上的性能; 第二, 在进化过程中, 每个参考向量对应一个子问题, 改变参考向量实质上改变了子问题, 这可能会使算法的收敛性显著降低[34]. 基于这些问题, 本文提出一种基于指标和自适应分解的高维多目标进化算法 (MaOEA based on indicator and adaptive decomposition, MaOEA-IAD), 旨在提升算法求解不同类型PF高维多目标优化问题时的综合性能, 以进一步增强算法平衡收敛性和多样性的能力. 与现有基于分解的MaOEAs相比, 本文的主要贡献如下:

1) 提出一种基于I(x)指标的参考向量自适应策略. 在该策略中, 引入一种小生境技术与收敛性指标相结合的综合性能指标I(x), 来评价个体的收敛性和多样性; 此外, 设计了一个实时维护的外部档案库, 以在进化过程中保留有期望的个体, 并进一步探测潜在的未开发但有前景的参考向量. 基于以上两种设计, 参考向量自适应策略能够在种群进化中自适应的添加和删除参考向量, 以提升MaOEA-IAD在处理不同PF问题时的综合性能;

2) 提出一种基于空间划分的精英替代策略, 该策略利用k-means聚类算法对种群空间进行划分, 并在每一子空间中利用遗传操作产生新的子代, 以增加进化种群在真实Pareto最优前沿上的分散和传播. 然后, 对种群中处在拥挤区域或综合性能较差的个体进行替换, 以进一步加强算法的收敛性;

3) 将MaOEA-IAD与4种先进的MaOEAs进行对比实验, 来验证MaOEA-IAD在不同PF问题上的有效性和优势.

本文其它部分安排如下: 第2节介绍背景知识, 第3节提出算法MaOEA-IAD, 第4节进行实验研究, 最后对全文进行总结.

总结

针对现有基于分解的MaOEAs在求解不同类型PF多目标优化问题时综合性能下降的问题, 本文提出一种基于指标和自适应分解的高维多目标进化算法(MaOEA-IAD). 利用一个实时维护的外部档案库来保留有期望个体, 并发现潜在的未开发但有前景的参考向量; 通过设计一种小生境技术与收敛性指标相结合的综合性能指标I(x), 来评价个体的收敛性和多样性. 基于以上两种设计, 提出一种参考向量自适应策略, 提升算法在处理不同PF问题时的综合性能. 为了进一步提升种群个体在真实PF的分散能力, 提出一种基于空间划分的精英替代策略. 通过与 4种先进的高维多目标进化算法的仿真对比实验, 验证了 MaOEAIAD处理不同复杂PF测试问题的有效性. 实验结果表明, MaOEA-IAD能够有效的平衡种群的收敛性和多样性且综合性能优于其他对比算法.

作者简介

田瑾然硕士研究生, 目前研究方向为高维多目标优化;

刘建昌教授, 博士生导师, 目前研究方向为智能控制理论及应用、复杂过程建模、控制与优化、故障诊断;

张伟硕士研究生, 目前研究方向为多目标优化;

刘圆超讲师, 目前研究方向为多目标优化.

期刊介绍

《控制理论与应用》(Control Theory & Applications)是经国家科学技术部批准, 教育部主管, 由华南理工大学和中国科学院数学与系统科学研究院联合主办的全国性一级学术刊物, 1984年创刊, 月刊, 国内外公开发行. 《控制理论与应用》是中国科学引文数据库首批统计源期刊之一，中文核心期刊，入选中国精品科技期刊顶尖学术论文F5000项目，中国科协自动化学科领域高质量科技期刊目录以及中国科协百篇优秀科技论文遴选计划，2021年入选广东省高质量科技期刊建设项目，2022-2024年连续获得基金委资助（科技活动专项）。

期刊封面2.jpg 目录2.jpg