受进化限制的大规模稀疏多目标优化:基准测试与算法进步

《Engineering Applications of Artificial Intelligence》:Evolutionary constrained sparse large-scale multiobjective optimization: Benchmarking and algorithmic advancements

【字体: 大 中 小 】 时间:2026年09月28日 来源:Engineering Applications of Artificial Intelligence 9.0

编辑推荐:

  • 一个新的测试套件,包含16个可扩展的受限稀疏多目标问题。 • 一个通用的进化框架采用了聚类和自适应约束处理方法。 • 该方法在受限高维情况下的性能优于现有算法。 **引言** 多目标优化问题(MOPs)在现实世界应用中广泛存在,其中需要同时优化多个相互冲突的

  • 一个新的测试套件,包含16个可扩展的受限稀疏多目标问题。
• 一个通用的进化框架采用了聚类和自适应约束处理方法。
• 该方法在受限高维情况下的性能优于现有算法。

**引言**
多目标优化问题(MOPs)在现实世界应用中广泛存在,其中需要同时优化多个相互冲突的目标(Coello, 2007)。由于改善一个目标通常会导致其他目标的恶化,因此最优的权衡解构成了帕累托最优解集(PS),该解集在目标空间中被映射为帕累托前沿(PF)。一类特定的MOPs被称为稀疏大规模MOPs(SLMOPs)(Tian et al., 2020d),它们出现在决策变量数量很大(例如超过100个)且大多数帕累托最优解的变量被设为零的情况下。在这种问题中,稀疏性意味着只有少数决策变量(称为活跃变量)对目标函数有显著贡献,而剩余变量是不活跃的(即设为零或接近零),其影响可以忽略不计。这种结构特性导致决策空间高度不规则和 discontinuous,使得搜索过程变得更加具有挑战性。典型的例子包括投资组合优化(Ponsich et al., 2013),其目标是在最小化风险的同时最大化回报;神经网络训练(Yao, 1993),其目标是最大化准确率的同时最小化模型大小;以及特征选择(Xue et al., 2012),其目标是选择最少的相关特征以提高分类性能同时减少冗余。

进化算法(EAs)通过其基于群体的搜索机制,特别适合解决MOPs,能够有效探索相互冲突的目标之间的复杂权衡(Storn and Price, 1997, Deb et al., 2002)。它们能够在一次运行中逼近帕累托前沿,处理非线性和非凸的搜索空间,并适应动态或黑盒环境,这使得它们特别适用于传统方法可能效果较差的复杂优化问题。然而,SLMOPs由于其高维决策空间和本质上稀疏的解结构,带来了重大的计算挑战。具体来说,高维性和稀疏性的共存导致搜索空间呈指数级扩大,大多数随机生成的解都被不活跃变量主导,从而导致候选解质量低且搜索效率低下。标准的多目标进化算法(MOEAs)在这些问题上遇到了显著困难,因为它们在优化过程中没有明确考虑稀疏性特征,从而导致搜索过程效率低下。为了解决这个问题,首先引入了稀疏MOEA(SparseEA)(Tian et al., 2020c),以及一个稀疏MOP(SMOP)测试套件,该套件提供了可扩展和高维的基准问题。此后,SMOP被广泛用于评估后续稀疏MOEAs(SMOEAs)的性能。现有的SMOEAs主要通过三种方法应对稀疏性和大规模挑战:减少决策空间以简化问题(Tian et al., 2020b, Tian et al., 2022, Ding et al., 2024, Ding et al., 2022)、对变量进行分组以进行共同进化(Wang et al., 2024, Tian et al., 2023, Liu et al., 2024a)以及设计基于稀疏性的进化算子以有效搜索(Wang et al., 2021, Shao et al., 2024a, Kropp et al., 2023, Tian et al., 2020c, Ding et al., 2022, Qi et al., 2024a)。更多细节见第2.2节。

尽管取得了这些进展,但大多数现有研究主要集中在无约束的SLMOPs上,而现实世界应用不可避免地涉及到限制可行解的各种约束。实际上,稀疏性和约束通常是紧密耦合的,这大大增加了问题的复杂性。例如,在投资组合优化中,预算和分配约束限制了选定资产的数量和比例(Jin et al., 2016);在神经网络训练中,计算和内存约束限制了模型的稀疏性(Plagianakos and Vrahatis, 1999);在特征选择中,特征相关性和计算成本等约束进一步复杂化了选择过程(Guo et al., 2011)。在这种条件下,可行区域可能变得高度碎片化甚至不连续,使得传统的SMOEAs难以同时实现可行性、收敛性和多样性。

尽管受限多目标优化已经得到了广泛研究,但现有方法并未专门针对高维决策空间中的稀疏结构进行设计。相反,当前的SMOEAs很少结合有效的约束处理技术(CHTs),因此在处理受限稀疏问题时表现不佳。因此,目前仍存在一个关键的研究空白,即开发能够同时解决稀疏性、大规模决策变量和复杂约束的方法。此外,目前还没有专门的基准测试套件用于评估受限稀疏多目标优化问题,这进一步阻碍了相关算法的发展和公平比较。为了填补这一空白,本文提出了一个名为CSMOP的受限SLMOP测试套件,它通过引入约束来扩展SMOP。通过将不同类型的约束嵌入到原始的SMOP框架中,CSMOP不仅保留了内在的稀疏特性,还引入了多样化且具有挑战性的可行区域,从而为评估受限稀疏优化算法提供了更现实和全面的基准。CSMOP为现有的SMOEAs带来了新的挑战,要求它们整合CHTs以找到满足所有给定约束的稀疏解。更重要的是,稀疏性和约束之间的相互作用引入了探索(识别活跃变量)与可行性(满足约束)之间的基本冲突,这无法通过现有方法有效解决。

为了解决这些挑战,本文进一步提出了一个受限稀疏多目标进化算法框架,称为CSMOEA。其关键思想是在稀疏决策空间中明确平衡多样性保持和在约束下的可行性指导。具体而言,引入了一种基于聚类的交配选择策略来通过鼓励在低密度区域的探索来增强多样性,同时采用自适应的?约束支配原则来动态引导群体向可行区域移动。这两种机制的结合使算法能够有效地 navigate CSMOPs 的复杂搜索空间。本研究的主要贡献总结如下:
1. 提出了一种新的受限稀疏多目标优化基准 CSMOP。本研究通过引入CSMOP测试集来扩展SMOP测试套件,该测试集包含严格的约束,以更真实地反映现实世界的优化场景。CSMOP包括16个问题,涵盖了两种不同类型的约束,为受限SLMOPs提供了更全面和多样化的评估基准。通过增强测试问题的真实性和复杂性,CSMOP 更有效地评估了SMOEAs 在解决受限SLMOPs 时的性能。
2. 开发了一种基于聚类的交配选择算子来应对稀疏高维空间中的多样性损失。为了改进进化优化中的父代选择,我们提出了一种基于第一邻居的快速聚类父代选择算子。该算子根据第一邻居关系对个体进行聚类,并根据簇大小动态调整选择概率,确保来自低密度区域的个体更有可能被选中。通过促进群体多样性和增强全局搜索能力,该算子提高了算法的探索效率。
3. 提出并验证了一个集成多样性增强和自适应约束处理的统一框架(CSMOEA)。所提出的父代选择算子与自适应的?约束支配原则相结合,并嵌入到现有的SMOEAs中。为了验证集成两种算子的框架的有效性,在CSMOP测试套件上进行了全面的实验,将提出的算法与八个结合了CHTs的先进MOEAs进行了对比。实验结果表明,在大多数测试实例中,所提出的算法表现出更优越的性能,有效地解决了受限SLMOPs问题。

本文的其余部分结构如下:第2节回顾了现有的稀疏MOEAs,概述了当前的CHTs,并讨论了受限多目标进化领域的最新进展,强调了解决CSMOPs的动机。第3节介绍了CSMOP测试套件,详细说明了其问题表述和约束类型。第4节介绍了CSMOEA框架,该框架集成了这两种提出的算子,并解释了它们的设计和功能。第5节报告了实验结果,评估了CSMOEA在CSMOP测试套件上的表现,并将其与其他结合了CHTs的SMOEAs进行了比较。最后,第6节总结了本文并指出了潜在的未来研究方向。

**概念片段**
MOPs中的稀疏性指的是帕累托最优解只包含一小部分非零决策变量的情况,而大多数变量仍然是不活跃的。这导致了一个结构化的搜索空间,其中只有有限数量的活跃变量对目标有贡献,从根本上区分了稀疏MOPs和传统的多目标优化问题。然而,大多数现有的MOP测试套件并没有明确建模或允许调整稀疏性。在广泛使用的测试套件中……

**提出的CSMOP测试套件**
本节介绍了提出的CSMOP测试套件的表述,随后介绍了两种类型的约束和18个基准问题的定义。

**提出的CSMOEA框架**
在本节中,我们介绍了用于解决CSMOPs的提出的CSMOEA。虽然现有的SMOEAs在识别稀疏帕累托最优解方面是有效的,但它们缺乏处理约束和在受限可行区域内保持多样性的机制。为了解决这些限制,CSMOEA引入了两个关键组件:(1)一种以多样性为导向的交配选择(DMS)策略,用于在稀疏和受限空间中增强探索;(2)一种以可行性为导向的环境选择……

**实验结果**
为了评估提出的CSMOEA框架的有效性,本节通过将CSMOEA集成到几个代表性的SMOEAs中,并在新设计的CSMOP1–CSMOP16测试问题上评估它们的性能来进行全面实验。比较涉及了几种先进的SMOEAs,根据它们的核心策略进行分类:(1)基于稀疏性驱动的进化算子的SMOEAs,包括SparseEA(Tian et al., 2020c)、SparseEA2(Zhang et al., 2023)、S-NSGA-II……

**结论**
本文研究了受限稀疏多目标优化问题(CSMOPs),这是一类在现实世界场景中经常出现的重要但尚未充分研究的问题,如特征选择、资源分配和神经架构修剪。为了促进系统研究,我们首先提出了一个新的基准套件CSMOP1–CSMOP16,该套件通过结合两种可扩展和结构多样的约束机制来扩展了经典的SMOP框架。这些测试问题……
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号