《Swarm and Evolutionary Computation》:Prediction-based dynamic constrained multi-objective optimization via temporal–spatial response error suppression
编辑推荐:
摘要基于预测的动态约束多目标进化算法(DCMOEA)因其能够利用历史信息为新环境提供高质量初始种群而受到越来越多的关注。然而,当学习到的趋势与实际环境变化不匹配时,这些算法会遭受预测偏差的问题。这种预测偏差会导致响应误差,即种群在动态响应后与目标约束帕累托集(CPS)之间的偏
摘要
基于预测的动态约束多目标进化算法(DCMOEA)因其能够利用历史信息为新环境提供高质量初始种群而受到越来越多的关注。然而,当学习到的趋势与实际环境变化不匹配时,这些算法会遭受预测偏差的问题。这种预测偏差会导致响应误差,即种群在动态响应后与目标约束帕累托集(CPS)之间的偏差。该响应误差会持续影响静态优化过程,在有限的计算预算下降低收敛性和覆盖性。为解决这一问题,本文提出了一种基于时空响应误差抑制的预测型DCMOEA。在时间维度上,设计了一种基于卡尔曼滤波的反馈校正迁移策略,用于补偿环境变化序列中累积的预测偏差,从源头抑制响应误差。理论分析建立了一个充分条件,在该条件下反馈校正能够减小质心预测误差。在空间维度上,引入了一种基于子空间锚定的环境选择策略,以在每个非空子空间中保留一个代表性解,防止受响应误差影响区域中的解在环境选择过程中被淘汰。在两个基准测试套件上的实验结果表明,所提出的算法在大多数实例上显著优于七种最先进的DCMOEA,能够找到帕累托最优解。结果还表明,应对响应误差是提高预测型DCMOEA性能的关键因素,为设计预测型DCMOEA提供了新的视角。
引言
动态约束多目标优化问题(DCMOP)是一类具有挑战性的优化问题,其中目标函数、约束条件、决策空间或它们的任意组合随时间变化[1]。此类问题在现实世界应用中经常出现,包括动态调度[2]、资源分配[3]和过程控制[4]。其核心难点在于,此前最优且可行的解在环境变化后可能变得次优或不可行。为了跟踪随时间变化的约束帕累托集(CPS),已开发出具有各种动态响应策略的动态约束多目标进化算法(DCMOEA),用于在环境变化后重新初始化或重构种群[5]。
动态响应策略所提供的初始种群质量在很大程度上决定了算法在新环境中的性能。由于连续环境变化之间的计算预算通常有限,初始种群直接影响后续静态优化的起点。一个在收敛性和覆盖性方面都接近新CPS的高质量初始种群,使优化器能够将有限的预算集中在提升解质量上。反之,质量较差的初始种群则迫使算法将大量预算用于补偿初始偏差,限制了可实现的解质量。
现有DCMOEA可根据其动态响应策略大致分为四类:基于多样性的方法、基于记忆的方法、基于迁移的方法以及基于预测的方法。基于多样性的DCMOEA通过随机扰动或部分重新初始化来增强种群多样性以响应环境变化[5]、[6]、[7]、[8]。基于记忆的DCMOEA在环境表现出可利用的相似性时复用历史解[9]、[10]。基于迁移的DCMOEA通过知识迁移利用历史解在不同环境间的可迁移性[11]、[12]、[13]、[14]。基于预测的DCMOEA通过建模和外推变化趋势,利用历史信息为新环境构建有信息量的初始种群[15]、[16]、[17]、[18]。最近,机器学习与进化计算的日益融合[19]进一步丰富了这些方法的设计;例如,Peng等人[20]采用深度强化学习,根据环境变化后种群的退化模式自适应地选择不同的响应策略组合。其中,基于预测的DCMOEA引起了越来越多的研究兴趣,这归功于它们能够通过建模变化趋势主动估计新CPS的位置,从而在静态优化开始之前提供高质量的初始种群。
然而,预测模型不可避免地会引入预测误差,这源于预测模型的固有局限性:非线性或非平稳的变化模式可能难以被预测模型准确捕获[21];可用的历史环境数量有限,尤其在优化的早期阶段[22];目标函数和约束条件的同时变化可能产生复杂的耦合动态,进一步损害预测保真度[11]。
预测误差反映的是预测本身的准确性。由动态响应产生的种群还受到边界处理和种群选择等操作的影响。在本文中,将整个动态响应后获得的种群与新CPS之间的偏差称为响应误差。该响应误差会带入后续的静态优化中。在有限的计算预算下,初始偏差可能无法得到充分减小,从而对最终种群的收敛性和覆盖性产生不利影响。
在现有DCMOEA中,响应误差及其对后续静态优化的传播问题尚未得到充分解决。在无约束动态多目标优化中,已有若干研究考虑了预测不准确的问题:提出了一种基于误差的校正框架来改进预测解[23],设计了一种基于扩散模型的策略来处理进化信息中的噪声[24]。然而,这些方法并未考虑动态约束引入的额外困难,其中可行域的偏移可能显著放大响应误差。在约束条件下,已有利用历史约束帕累托前沿(CPF)[16]或调整辅助种群角色[18]的静态阶段设计被考虑过,但两者均未明确解决动态响应阶段遗留的响应误差如何在后续静态优化过程中降低种群质量的问题。这一空白促使需要一种专门策略,在两个阶段都抑制响应误差,而不是将动态响应和静态优化孤立对待。
本文提出了一种时空响应误差抑制方法,在动态响应和静态优化两个阶段解决预测型DCMOEA中的响应误差问题。本研究的主要贡献总结如下。
- •
本文提出,在动态响应和后续静态优化两个阶段都解决响应误差问题,对于提高预测型DCMOEA在寻找帕累托最优解方面的性能至关重要。本研究为预测型DCMOEA的设计提供了新方向。
- •
提出了一种预测型DCMOEA,通过结合基于卡尔曼滤波的反馈校正迁移策略和基于子空间锚定的环境选择策略,在两个阶段抑制响应误差。提供理论分析以建立反馈校正能够减小质心预测误差的充分条件。在两个基准测试套件上的实验结果证实,解决响应误差问题能够显著改善动态约束多目标优化的种群收敛性和多样性。
本文其余部分组织如下。第2节介绍DCMOP的定义并回顾现有DCMOEA。第3节详细说明时空响应误差抑制方法。第4节描述整体算法框架并给出复杂度分析。第5节报告实验结果和分析。最后,第6节总结本文并展望未来的工作方向。
章节摘要
相关工作
本节首先介绍DCMOP的数学公式表述,然后根据动态响应策略回顾现有DCMOEA。这些DCMOEA被归类为基于多样性的方法、基于记忆的方法、基于迁移的方法和基于预测的方法。
时空响应误差抑制
本节提出时空响应误差抑制方法,包含两种互补策略:
- •
时间抑制。引入了一种基于反馈校正的卡尔曼迁移策略,用于在动态响应期间减少预测偏差。与现有研究[11]、[15]、[16]、[17]、[18]相比,观测到的质心预测残差被额外用作反馈,以校正种群在环境变化之间的迁移。
- •
空间抑制。基于子空间锚定的
算法框架
本节提出所提算法的整体框架并分析其计算复杂度。在环境变化时,在动态响应阶段应用基于反馈校正的卡尔曼迁移策略,为新环境生成种群。基于子空间锚定的环境选择用于在动态响应过程中以及后续静态优化的每一代更新辅助种群。整体工作流程总结于
实验
本节进行八项实验以评估所提出的算法——基于时空响应误差抑制的DCMOEA(DCMOEA-TSRES)。实验设置在第5.1节中给出。八项实验组织如下。
E1.第一项实验通过将DCMOEA-TSRES与七种基线DCMOEA在76个基准实例上进行比较来评估整体优化性能(第5.2节)。
E2.第二项实验用于验证反馈
结论
本研究解决了预测型DCMOEA中的响应误差问题及其对后续静态优化过程中种群收敛性和覆盖性的不利影响。所提出的时空响应误差抑制方法包含一个基于反馈校正的卡尔曼迁移策略,用于在动态响应阶段减少预测偏差,以及一个基于子空间锚定的环境选择策略,用于在目标空间中保留代表性解
CRediT作者贡献声明
陈元军:撰写——初稿。彭超达:监督指导。吴胜浩:监督指导。吴中国:监督指导。陈凯陈(Kay Chen Tan):监督指导。
利益冲突声明
作者声明不存在可能影响本文所报告工作的已知竞争性经济利益或个人关系。
致谢
本工作部分由广东省基础与应用基础研究基金(资助号2026A1515012270)以及广州市科学技术局(资助号2025A04J5508)资助。
陈元军|彭超达|吴胜浩|吴中国|陈凯陈