一种自适应多目标进化算法,该算法结合了非支配熵技术和多支配筛选方法进行优化

《Expert Systems with Applications》:A self-adaptive multi-objective evolutionary algorithm assisted by non-dominated entropy combined with multi-dominated screening

【字体: 大 中 小 】 时间:2026年01月25日 来源:Expert Systems with Applications 7.5

编辑推荐:

  多目标进化算法在解决复杂问题时面临局部搜索能力不足和收敛性与多样性难以平衡的挑战。本文提出基于非支配熵和多重支配筛选的自适应算法MDEA-NDE,通过动态调整交叉和突变概率增强局部搜索能力,并利用多支配筛选机制优化种群多样性,在UF、CF、DTLZ基准函数上的实验验证了其优越性。

  
王子龙|邵鹏|张少平
江西农业大学计算机与信息工程学院,南昌,中国

摘要

多目标问题存在于生活的各个方面,已经有一些进化算法(EAs)来解决这些问题。然而,对于复杂问题,传统的EAs由于其固有的随机性,每次都难以进行详细的局部探索。此外,在探索过程中,它们的收敛性能较差,种群的多样性也较弱。为了解决这些挑战,本文提出了一种基于非支配熵和多支配筛选的自适应多目标进化算法(MDEA-NDE)。MDEA-NDE引入了两种动态机制:基于拥挤熵的自适应交叉和基于支配的筛选。在MDEA-NDE的进化过程中,通过拥挤熵调整变异因子,以帮助算法提高收敛性能并增强种群多样性。同时,对交叉后的父代进行基于支配的动态筛选,以加强算法的局部搜索能力。为了验证MDEA-NDE的性能,本文选择了三个具有不同特征的基准函数UF、CF和DTLZ来测试MDEA-NDE,并将其与其他先进算法进行比较。结果表明,MDEA-NDE与其他算法相比具有更强的竞争力。此外,Friedman检验统计数据显示MDEA-NDE与其他算法有显著差异。另外,还在一个实际工程案例中对MDEA-NDE进行了评估,证明了其在收敛性和多样性方面的竞争性能。

引言

如今,优化问题在生活中非常普遍。然而,我们遇到的大多数优化问题并不是追求单一目标的优化,而是同时优化多个相互冲突的目标,这些被称为多目标问题(MOPs)(Deb等人,2016年)。例如,在分布式作业车间调度问题中,既要最小化完成时间,又要减少总能耗(Yang等人,2025年);在投资组合中,目标是降低投资风险并增加投资回报(Song等人,2024年);在电网控制中,需要在尽可能减少对环境影响的同时降低成本(Li等人,2024年)。与单一目标算法存在唯一最优解不同,MOPs的特点是一组非支配解,而不是单一最优解(Deb,2001年)。相反,它是一组相对平衡的解,使得两个目标达到相对平衡。在决策空间中,这组解被称为帕累托最优集(PS)(Sun等人,2018年),而其在目标空间中的映射定义为帕累托前沿(PF)(Palakonda等人,2021年)。并且集合中的任何解都不能在每个目标上被同一个解超越,这就是我们所说的支配性(Yuan等人,2015年)。
早期,一些学者提出使用一些传统方法来解决MOPs,如加权求和(Marler和Arora,2010年)和ε-约束方法(Zuluaga等人,2016年),试图将多个目标转化为单一目标进行解决,但这仍然存在一些限制(Marler和Arora,2004年)。权重的设置和约束在解决问题中起着关键作用,通常每次运行只能获得一个解。为了获得近似的PF,需要多次运行算法来调整参数,这使得处理更复杂的情况变得困难。
为了克服传统算法的缺点,一些学者提出使用进化算法(EAs)来解决MOPs(Deb,2011年)。近年来,由于EAs强大的全局搜索能力和一次生成一组近似PS的能力,它们被广泛用于解决MOPs(Zitzler等人,2004年)。其中,非支配遗传算法(NSGA-II)(Deb等人,2002年)和多目标粒子群优化算法(MOPSO)(Coello等人,2002年)的应用最为广泛,例如用于解决节能灵活作业调度的混合遗传算法(Hao等人,2025年),用于规划无人机路径的MOEA(Xu等人,2024年);以及基于电动汽车充电站位置问题的MOEA(Zapotecas-Martínez等人,2024年)等。
尽管这些经典EAs相比传统算法有明显的优势,但随着实际优化问题变得越来越复杂,它们也面临新的挑战。
  • •
    局部搜索能力的弱点。在传统的进化算法中,个体的选择过程是随机的,每个个体对种群的贡献完全不同。因此,当经常使用较不优秀的解时,可能会导致在有限时间内对整个空间的探索不足,从而导致每次生成的PS有显著差异(Cheng等人,2016年)。更重要的是,在父代选择过程中,被支配的个体几乎被同等对待,无论有多少非支配解支配它们。结果,一些进化信息极其有限的解被反复选择,这削弱了向PF的有效局部探索。
  • •
    收敛性和种群多样性之间的不平衡。在传统EAs中,种群通过模拟进化过程中的某些操作来搜索PS。然而,在传统EA中,这些操作发生的概率都是预先设定的。因此,面对一些复杂问题时,传统EA难以同时实现良好的收敛性和种群多样性,从而难以平衡收敛性和种群多样性(Coello,2006年)。然而,非支配解的分布状态在优化过程中是动态变化的。固定的交叉和变异概率无法应对种群密度的变化,当种群变得拥挤时可能导致探索不足,或者当种群稀疏时导致过度随机性。
  • 基于这些问题,许多学者已经提出了一些解决方案,如基于层次估计和聚类的自适应分解MOEA(Zhang等人,2024年),基于多状态强化学习的MOEA(Wang等人,2025年),基于Q学习的MOEA(Song等人,2025年)等。从这些前沿工作中可以看出,将机器学习或智能体等技术引入遗传算法可以使算法在面对复杂问题时具备一定的学习和适应行为,使算法在进化过程中能够动态调整,从而更有效地平衡收敛性和多样性。然而,大多数具有动态调整的算法需要预先训练,因此在算法迭代次数相对较少时难以取得良好结果。相比之下,直接从当前非支配解集合派生的基于分布的指标可以提供即时反馈,而无需额外的学习开销。
    因此,本文提出了一种基于非支配熵和多支配筛选的自适应MOEA(MDEA-NDE)。MDEA-NDE算法的核心是根据非支配解集合中的拥挤熵动态调整下一次进化中每个操作的概率,从而能够根据问题的实际情况进行适应性调整。此外,还引入了一种自适应概率策略,使得种群中被选为交叉父母的每个个体的选择压力不同。一些信息较少的个体受到更大的压力被淘汰,从而增强了算法的能力。因此,贡献如下:•
    提出了一种基于拥挤熵的自适应策略。通过考虑种群中非支配解的分布,动态确定下一次进化过程中的参数,以平衡算法的两种能力。
  • •
    提出了一种多支配筛选方法。基于种群中的支配关系,将被更多非支配解支配的个体筛选出来,从而降低它们被选为下一代交叉父母的概率,从而提高算法的收敛性。
  • 章节片段

    MOPs

    MOEAs的主要目的是同时优化多个相互冲突的目标,找到一个好的近似真实PF,并使找到的种群在近似PF上尽可能均匀分布。如今,已经提出了许多方法来改进这些算法,如基于w-支配关系的MOEA(Szlapczynski和Szlapczynska,2021年),使用支配树的MOEA(Shi等人,2009年),基于epsilon支配的多目标算法(Chalabi等人,2023年)等

    MDEA-NDE的流程图

    图2显示了MDEA-NDE的流程图。其中,It表示当前迭代次数,MaxIt表示最大迭代次数,蓝色区域表示基于群体熵的适应,绿色区域表示多优势筛选。详细过程将在后续章节中介绍。

    多支配筛选

    算法的收敛性是评估其质量的重要指标。更好的收敛性表明算法可以更快地找到PS。然而,并非所有个体

    实验

    在本章中,将测试MDEA-NDE。使用了三个基准问题,即UF(Zhang等人,2009年);DTLZ(Deb等人,2005年)和CF(Zhang等人,2009年),并采用了两个指标来评估算法。这三个基准问题涵盖了现实世界优化过程中遇到的大多数挑战。通过常见的双目标和三目标问题测试了MDEA-NDE的性能。

    关于自适应方法的讨论

    在第4.3节中,对提出的两种方法进行了消融实验。如表2所示,在引入多支配筛选后,UF7上的平均IGD值从1.85 × 10?1降低到1.56 × 10?1,而进一步结合基于拥挤熵的适应后,IGD值降低到1.17 × 10?1。在DTLZ1上也观察到了类似的改进,IGD值从5.79 × 10?2降低到4.13 × 10?2

    结论

    为了增强局部搜索能力和实现收敛性与种群多样性之间的平衡,本文提出了两种自适应策略:基于多支配的筛选和基于非支配熵的自适应交叉和变异操作符。这种多支配筛选在早期迭代中选择交叉父母时,根据一个解被支配的次数动态筛选出一些处于较低非支配水平的解,从而

    CRediT作者贡献声明

    王子龙:概念化、方法论、调查、撰写——原始草稿、撰写——审阅与编辑。邵鹏:资金获取、方法论、撰写——审阅与编辑、监督、调查。张少平:方法论、撰写——审阅与编辑、监督、调查。

    利益冲突声明

    作者声明他们没有已知的可能会影响本文所述工作的竞争性财务利益或个人关系。

    致谢

    本工作得到了江西省自然科学基金(20252BAC240193)、江西省社会科学规划项目(21GL12)和江西省高等教育人文社会科学规划项目(GL22232)的资助。
    相关新闻
    生物通微信公众号
    微信
    新浪微博
    • 搜索
    • 国际
    • 国内
    • 人物
    • 产业
    • 热点
    • 科普

    热点排行

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

      版权所有 生物通

      Copyright© eBiotrade.com, All Rights Reserved

      联系信箱:

      粤ICP备09063491号