一种基于最大平均偏差指标的进化算法,用于求解具有不可检测变化的动态多目标优化问题

《Swarm and Evolutionary Computation》:A maximum mean discrepancy indicator-based evolutionary algorithm for solving dynamic multi-objective optimization problems with undetectable changes

【字体: 大 中 小 】 时间:2026年09月24日 来源:Swarm and Evolutionary Computation 9.6

编辑推荐:

   **摘要** 目前大多数关于动态多目标优化问题的研究都假设环境变化是可以检测到的。然而,在实际应用中,许多环境变化是无法检测的,这对传统的动态多目标进化算法构成了重大挑战。关键问题是如何在不牺牲收敛性的情况下提高种群多样性。为应对这一挑战,本文提出了一种基于最大均值差异指标

  

**摘要**

目前大多数关于动态多目标优化问题的研究都假设环境变化是可以检测到的。然而,在实际应用中,许多环境变化是无法检测的,这对传统的动态多目标进化算法构成了重大挑战。关键问题是如何在不牺牲收敛性的情况下提高种群多样性。为应对这一挑战,本文提出了一种基于最大均值差异指标的进化算法(MMDEA)。首先,设计了一种基于MMD指标的前沿进化评估策略,用于监测进化过程的状态。利用MMD有效度量分布间距离的能力,将其用于识别种群的进化状态。通过计算当前近似最优前沿与前一近似最优前沿之间的MMD指标值,可将种群状态划分为收敛状态或多样性状态。当种群处于收敛状态时,采用收敛增强策略,根据非支配解与其最近支配解之间的偏差来指导进化。当种群处于多样性状态时,提出了一种多样性增强策略,根据非支配解与其最近支配解之间的偏差来指导支配解的进化。针对多种动态多目标优化问题进行了实验,并与几种最先进的算法进行了比较。综合结果表明,所提出的算法在求解存在不可检测变化的问题时非常有效且表现优越。

**引言**

动态多目标优化问题(DMOPs)的特征在于多个目标函数之间存在冲突关系[1]、[2]、[3]。此外,这些目标函数、问题约束以及相关参数可能会随时间而变化[4]、[5]、[6]、[7]。这种动态性会引起目标景观的变化,以及Pareto集(PS)和Pareto前沿(PF)的变化,从而进一步增加优化问题的复杂性,并对优化方法的鲁棒性和适应性提出新的挑战[8]、[9]、[10]。近年来,DMOPs在资源调度[11]、智能路径规划[12]和工业制造[13]等领域引起了广泛的研究关注。值得注意的是,现有技术往往难以检测某些DMOPs中的动态环境变化,甚至可能完全无法识别[14]。一个典型的例子是流化催化裂化过程,由于原料的随机波动、催化剂的缓慢失活以及操作参数的耦合扰动,环境变化的时间和幅度很难准确检测[15]、[16]。具体来说,燃料油性质变化的检测仍然是一个现有技术尚未完全克服的艰巨挑战[17]。因此,本文主要关注具有不可检测变化的DMOPs,对于这些变化,现有技术无法实时识别目标函数及相关元素的变化。

传统多目标优化方法通常在静态多目标优化问题上表现出优异的性能[18]、[19]、[20]。其主要优势在于通过成熟的种群控制机制(如非支配排序和拥挤距离评估)[21]、[22]、[23],有效地平衡了解集向PF的收敛性与前沿区域的分布均匀性。然而,由于缺乏对环境变化的响应机制,这些静态算法无法有效跟踪随时间变化的PF。在动态环境中,这一缺点直接导致种群多样性丧失和解质量下降,最终使这些算法不适合求解DMOPs[24]、[25]、[26]。通过引入环境响应机制,动态多目标进化算法(DMOEAs)展现出优于其静态对应算法的环境适应性。它们不仅能随环境变化跟踪动态PF,还能在迭代过程中生成近似于更新前沿的高质量解集[27]。一般而言,DMOEAs可根据其应对环境变化的不同策略进行分类。

(1)多样性维持方法。这些方法通过在检测到环境变化时以较高概率注入少量随机生成或超变异的个体来缓解种群多样性的枯竭[28]。例如,在DNSGA-II-A [29]和DNSGA-II-B [29]中,使用随机生成的解或通过多项式变异产生的解来替换原始种群中的部分个体。这种策略不仅增强了种群多样性,还确保了种群规模保持不变。Chen等人[30]提出了一种动态双档案进化算法,该算法维持两个互补的协同进化种群,使其能够对环境变化进行自适应重建,并通过交配选择机制促进种群间的交互。Hu等人[31]提出了一种集成分层预测与基于子空间的多样性维持的进化算法。分层预测机制能够对环境变化做出快速响应,而基于子空间的多样性维持策略能够识别并填补种群分布中的间隙,从而在种群多样性与收敛性之间实现更好的平衡。Liu等人[32]提出了一种基于双重突变的进化算法,在该算法中,个体根据种群的探索水平被动态选择进行多项式变异或高斯变异,从而维持种群多样性。此外,Li等人[33]提出了一种基于种群鲁棒性的切换响应框架。该框架通过量化和分类环境变化对种群的影响,在三种响应策略之间进行自适应切换,建立了响应策略与动态环境之间的关联,从而提高了DMOEAs的性能。此外,Ge等人[34]提出了一种具有概率驱动预测和相关性引导迁移的动态多目标优化算法。前者采用判别式预测器在决策空间中挖掘高质量解;后者探索连续精英个体之间的相关性并迁移其变化模式,从而提高种群多样性与分布均匀性。Yu等人[35]提出了一种基于双空间检测的自适应响应算法,该算法通过量化PS和PF的变化将环境变化动态分类为轻微变化或重大变化。在重大变化下,使用门控循环单元预测模型构建高质量初始种群;而对于轻微变化,则分别对PS和PF应用质心引导差分预测和随机解生成,从而增强种群多样性和自适应性能。

(2)多种群方法。多种群方法将种群划分为多个子种群,每个子种群探索不同的子区域,从而在求解DMOPs时维持整体种群多样性[36]。例如,Liu等人[37]提出了一种多种群进化算法,其中每个子种群负责处理决策变量的一个子集,这些子集在评估阶段组合以形成完整解。Xu等人[38]分别基于粒子群优化和NSGA-II算法开发了两种多种群优化方法。两种方法都采用两个子种群,但采用了不同的响应机制。Gong等人[39]提出了一种协同进化优化算法,其中决策变量根据其相似性被分解为若干组,每组分配给一个包含两种响应策略的子种群。Li等人[40]提出了一种基于级联模糊系统的动态多目标优化算法,该算法自适应选择历史Pareto解、多子种群质心和膝点来构建源域。多子种群质心前馈用于建立目标域,并利用核均值匹配估计学习样本,从而有效缓解了进化迁移优化中的负迁移问题。此外,Hu等人[41]提出了一种基于双空间划分的多种群协同进化算法用于求解DMOPs。该算法在目标空间和决策空间中对子种群进行划分,集成双空间信息,从而能够更准确地预测环境变化后新种群更新位置。

(3)基于记忆的方法。基于记忆的方法通过保存和组织来自先前环境的代表性解来增强算法在新环境中的适应性,从而实现在不同设置下的有效知识迁移和重用[42]。例如,在[43]中,构建了一个记忆池来存储候选解的子集,然后在环境变化时利用这些解来指导种群更新。Zou等人[44]提出了一种动态进化环境模型,该模型记录了进化过程的信息,以在新环境中指导个体搜索并保持种群多样性。Chen等人[45]重用历史信息来随机重新初始化种群,从而提高对环境变化的适应性。此外,Peng等人[46]提出了一种具有自适应增强的动态多目标优化进化算法,其中自适应增强响应机制调整了基于预测的、基于记忆的和基于多样性的集成策略的权重,以有效应对DMOPs。

(4)基于预测的方法。基于预测的方法利用历史种群信息构建预测模型,以识别下一环境中的高质量解[47]。例如,Zheng等人[48]提出了一种基于调整参考向量结合多目标进化算法的种群预测方法,该方法通过线性预测来预测非支配解集,自适应调整参考向量,并采用噪声驱动的个体扩展策略来有效跟踪PF并保持种群多样性。Hou等人[49]提出了一种基于时间分布特征并由门控循环单元神经网络辅助的动态多目标预测策略。该策略从历史质心信息构建时间序列,训练模型,并使用门控循环单元网络预测种群,从而提高种群多样性并响应环境变化。Xu等人[50]提出了一种基于决策空间聚类中心线性预测和目标空间诱导突变的算法。该算法利用决策空间中的聚类中心进行线性预测,以捕获种群的进化方向和分布,并在目标空间中应用基于预测的PF的诱导突变策略来选择有希望的个体进行突变,从而提高算法响应环境变化的能力。Sun等人[51]提出了一种基于环境变化程度的决策变量分类策略。该策略设计了一个多区域自适应变化检测模块,相应地分类决策变量,并采用调节方案使个体能够快速接近并沿PF均匀分布。Yang等人[52]提出了MRESN-MOEA/D算法,该算法将多储备池回声状态网络预测器与基于分解的多目标进化算法相结合。它利用分形插值来补偿训练样本不足,并通过多储备池回声状态网络利用决策变量之间的复杂相关性来生成新环境的初始种群,实现了优异的收敛性和多样性。Wang等人[53]提出了一种基于反馈引导迁移和趋势流形预测的动态多目标优化算法。前者通过信息反馈模型从所有历史环境中提取有价值的知识,并通过聚类迁移学习筛选精英个体;后者使用基于搜索信息的概率趋势预测方法,估计整个种群的质心及其对应的流形,二者的协同作用将种群引导向最优搜索方向。Wang等人[54]提出了一种偏好驱动的动态多目标进化算法,该算法通过参考点驱动的进化方向调整、基于角度的区域搜索以及结合线性预测和种群流形估计的混合预测策略,实现了对动态偏好和感兴趣区域的准确跟踪,同时确保了解集的满意收敛性和分布性。Hu等人[55]提出了一种基于相似性识别和知识迁移的动态多目标优化学习算法。该算法通过聚类中心驱动的前馈神经网络学习区域动态规律,利用相似性识别机制从历史环境中提取和迁移有效知识,并通过种群重建策略在解的支配性引导下生成具有优越收敛性和分布性能的最优解。Lei等人[56]提出了一种结合自适应双域变化响应和二次导数预测的变化预测策略。该策略通过自适应双域机制同时监控PS和PF的变化,根据环境特征动态调整决策空间和目标空间之间的预测资源分配,并通过二次导数预测实施主动种群重新初始化,从而显著提高了算法对突然或非线性的变化的响应能力。Wang等人[57]进一步开发了一种基于扩散模型的预测策略,其中采用了一种PS估计方法来构建训练集并指导对新PF的搜索。此外,Hu等人[58]提出了一种基于共享点和多尺度的区域感知预测策略,称为RADMOEA,该策略集成了全局和局部特征。

具体来说,该方法结合了中心点运动建模、基于共享点的子区域划分与局部坐标系构建、个体与移动后最近非支配解的关联,以及高斯扰动来生成新种群,从而增强了在动态环境中对帕累托前沿(PF)的感知和适应性。王等人 [59] 提出了一种基于自适应动态响应的动态多目标进化算法,该算法通过子种群级自适应机制协调了多样性驱动、预测驱动和记忆驱动策略,并根据每个子种群的静态优化距离动态调整策略权重,有效解决了固定策略分配效率低和个体级扰动不稳定的问题,从而实现算法的稳定协调演化。李等人 [60] 提出了一种基于扩散学习的动态多目标进化框架。该框架将跨环境种群进化轨迹作为监督训练数据,引入轨迹对齐损失来约束去噪过程,并利用基于条件扩散模型构建的进化策略。该策略在预设条件下控制去噪的方向和强度,以生成从随机噪声向新环境中的帕累托最优解演化的优化路径。

尽管现有算法在解决动态多目标优化问题(DMOPs)方面取得了相当可观的进展,但大多数都是在环境变化易于检测的假设下设计的 [61]。当环境变化不可检测时,传统检测方法失效,导致支持响应机制无法运行 [32]。此外,环境变化通常会导致种群多样性快速丧失和解决方案质量下降,这是影响算法性能的关键因素。因此,为不可检测的 DMOPs 开发有效的算法具有重要意义。

为了解决上述挑战,我们提出了一种基于最大均值差异(MMD)指标的进化算法,用于解决具有不可检测变化的 DMOPs。本工作的主要贡献总结如下:
• 提出了基于 MMD 指标的前沿进化评估策略,用于评估种群的进化状态。MMD 量化了当前种群与前一个种群的近似最优前沿之间的差异。将获得的 MMD 值与预定义阈值进行比较,将种群状态分类为收敛状态或多样性状态。
• 设计了收敛增强策略,以加速种群收敛。当 MMD 值超过预定义阈值时,识别出种群处于收敛状态。量化非支配解与其最近被支配对应解之间的偏差,以指导非支配解的进化方向,并促进其向 PF 快速收敛。
• 开发了多样性增强策略,以提高种群多样性。当 MMD 值低于预定义阈值时,认为种群处于多样性状态。测量被支配解与最近非支配解之间的偏差来指导它们的进化方向,以增强种群多样性并保持解决方案集的均匀分布。

本文其余部分组织如下。第 2 节概述了 DMOPs 和 MMD。第 3 节介绍了所提出的算法。第 4 节展示了竞赛的实验结果。最后,第 5 节总结了本文。

小节片段
具有不可检测变化的 DMOPs
对于具有不可检测变化的 DMOPs,其数学表达式由 [32]、[62] 给出:其中 x=(x1,x2,…,xd),M 是目标函数的数量,fi 是第 i 个目标函数,Ω 是决策空间,t 代表时间并反映环境变化。

最大均值差异
最大均值差异(MMD)[63]、[64]、[65] 是一种基于核的概率度量,属于积分概率度量(IPMs)的边界族。MMD 是通过核均值嵌入(KME)定义的……

Proposed 方法:MMDEA
本节首先介绍了 MMDEA 的整体框架。随后,我们详细介绍了基于 MMD 指标的前沿进化评估策略。最后,我们介绍了本工作中提出的两个核心策略,即收敛增强策略和多样性增强策略。

实证结果
在本节中,我们进行了一系列实验,以验证 MMDEA 在具有不可检测环境变化的 DMOPs 上的性能。为确保实验结果的可靠性和可复现性,所有测试均在硬件平台上进行:惠普 EliteBook 835 G7 笔记本电脑。具体而言,该设备配备 AMD Ryzen 7 PRO 4750U CPU、集成 Radeon 显卡和 16 GB 内存。在软件方面,所有实验均在 MATLAB R2020a 中编码并运行以……

结论
本文提出了 MMDEA 来解决具有不可检测变化的 DMOPs。首先,基于 MMD 指标的前沿进化评估策略量化种群的进化状态,并自适应地激活差异化策略,以动态平衡探索和利用。它计算连续种群迭代之间的非支配前沿的 MMD,以衡量进化过程中的前沿变化。如果 MMD 值超过预设阈值,则意味着不足……

CRediT 作者贡献声明
李飞:方法论,形式化分析。潘浩:撰写 – 原稿,软件,资金获取。杨凯峰:撰写 – 审阅与编辑,概念化。王浩:撰写 – 审阅与编辑,监督,资源。

利益冲突声明
作者声明,他们没有已知的竞争性经济利益或个人关系,这些关系可能会影响本文报告的工作。

致谢
本工作得到中国国家自然科学基金(批准号 62673006, 61903003)、安徽省自然科学基金(批准号 2308085MF199)、安徽省高校科研项目(批准号 2023AH051124)、安徽省智能拆除装备工程实验室开放项目(批准号 APELIDE2022A007)、安徽省特种重载机器人重点实验室开放项目(批准号 TZJQR001-2021)以及安徽……

李飞|潘浩|杨凯峰|王浩
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号