引言：大规模重叠问题(Large-Scale Overlapping Problems，LSOPs)是大规模优化领域中极具挑战的一类问题[1-2]，在实际应用领域中普遍存在，例如：多学科设计优化问题、供应链优化问题等。对于大规模重叠问题而言，当前其面临的主要挑战包括：1）整体优化方法难以应对大规模重叠问题高维度挑战；2）基于分解的优化方法难以兼顾大规模重叠问题结构识别的效率和准确性；3）现有研究中所涉及的大规模重叠问题性质较为单一。
为了解决这些挑战，最近华东理工大学与西湖大学可信及通用人工智能实验室合作，在计算智能顶级期刊IEEE TEVC上发表了一篇题为“An Enhanced Differential Grouping Method for Large-Scale Overlapping Problems”的文章。该工作先详细讨论了重叠问题的各项性质，并提出了一种基于两阶段的大规模重叠问题结构识别方法，第一阶段保证了算法的高效性，第二阶段对算法的准确性进行了补偿，并对现有的重叠问题基准进行了扩展。让我们一起来了解一下吧！
原文链接：https://ieeexplore.ieee.org/abstract/document/10504851
1
研究背景
大规模全局优化(Large-scale Global Optimization，LSGO)问题指的是决策变量数目多达数千及以上的优化问题。基于变量之间的可分性，大规模优化问题可以分为以下几类：完全可分问题、部分可分问题、重叠问题、完全不可分问题[3]。完全可分问题和部分可分问题具有明显的独立低维子组，各个低维子组之间不存在交互性。完全不可分问题变量之间耦合关系紧密，交互性程度较高。
图1：大规模优化问题类型
重叠问题是介于上述可分问题和完全不可分问题之间的一类优化问题，最早在CEC 2013 LSGO竞赛中被提出[4]，重叠问题变量之间具有稀疏的交互性结构，不同子组间通过共享变量建立交互性联系，子组之间展现了不同程度的交互性。重叠问题的子组间具有模块化交互结构，为使用协同进化算法(Cooperative Coevolution，CC)处理此类问题提供了可能。
基于分解的协同进化算法需要准确获得目标问题变量间的交互性关系，重叠问题变量间交互性关系较为复杂，具有以下几个特点：
同一个子组内的变量彼此直接交互。
共享变量将所有子组关联在一起，不同子组内的非共享变量间接交互。
一个子组可能与多个子组存在交互关系，交互程度可能不同。
某些共享变量可能存在于多个子组中。
现有的交互性检测方法无法应对重叠问题交互关系复杂带来的结构识别挑战，主要问题如下：
一般的交互性检测方法(DG[5]、RDG[6]、MDG[7]等)忽略了重叠问题潜在的模块化结构，将所有变量归为一个不可分变量组。
专门为重叠问题设计的分解方法(RDG3[8]等)通过断链将重叠问题划分为多个独立子组，造成了结构信息损失，识别结果不准确。
基于构造交互性矩阵的方法(DG2[9]等)可以准确获得重叠问题的交互性结构信息，然而，这类方法成对地检测变量之间的交互作用，计算资源消耗过多。
此外，当前研究中缺少对大规模重叠问题性质的总结与讨论，现有的大规模重叠问题基准也相对单一，只考虑了加性可分的链式拓扑重叠问题。
为了解决上述问题，本文从拓扑结构、共享变量类型和重叠程度三方面对重叠问题的性质进行了全面分析；提出了一种全新的重叠问题结构识别方法，在保证准确解析大规模重叠问题底层结构的前提下，消耗的计算资源约为传统方法的10%，保证了重叠问题交互性结构识别的效率和准确性；从拓扑结构、重叠程度和可分性对重叠问题基准函数进行了扩展，并提出了重叠问题结构识别评估指标。
2
本文所提方法
算法框架
为了解决现有的大规模重叠问题结构识别方法无法兼顾准确性和减少计算资源消耗的挑战，本文提出了一个大规模重叠问题结构识别方法(Overlapping Enhanced Differential Grouping，OEDG)，高效准确地识别重叠问题的底层交互性结构。
OEDG包括两个阶段：重叠问题递归分组阶段和分组结果准确性补偿阶段。第一阶段通过变量-变量集递归交互性检测策略减少了变量-变量检测造成的计算资源消耗冗余，实现了对问题结构的预解析；同时，为了补偿递归检测方法造成的准确性损失，提出了一种基于历史信息的预解析结果改善策略，以极低的计算成本，进一步实现了对问题结构的准确识别。
递归分组
该阶段采用基于二分递归的变量-变量集交互性检测方法，目的是找出重叠问题中的子组集和共享变量集。现有的交互性检测方法可以分为三类，基于有限差分原理的交互性检测方法，基于单调性检测原理的交互性检测方法和基于极小值点偏移原理的交互性检测方法。本文主要采用了基于有限差分原理的交互性检测方法为例（实验部分整合了基于极小值点偏移原理的交互性检测方法，在非加性可分问题上进行了测试），两变量集满足以下条件时则存在交互作用：
OEDG第一阶段执行多次交互性检测循环，每轮循环识别出一个子组和其中的共享变量。每轮循环首先选择一个未检测变量，检测其与整个问题变量组之间的交互关系，获得一个子组，与一般的交互性检测方法(DG、RDG、MDG等)相比，保证了问题结构信息的完整性。随后检测该子组与剩余变量之间的交互关系，获得重叠变量组。重复上述循环，直到检测出所有的子组集和共享变量集。递归分组阶段示意图如图2所示。
图2：递归分组阶段
准确性补偿阶段
通过对第一阶段算法机制的分析，被检测变量选取不当可能会导致不准确的分组结果，体现在识别得到的子组可能是多个最小子组的并集，这是由于被检测变量随机选择到了重叠变量，重叠变量与多个子组存在交互作用。
第二阶段旨在对第一阶段的分组结果进行准确性补偿，从而提高算法的稳定性，准确地获得重叠问题的底层交互结构。该阶段首先使用SUD方法对第一阶段形成的子组进行检测，判断其是否是多个子组的并集。之后使用SD方法进一步对子组并集分解，获得重叠问题最小子组，从而推断出准确的重叠问题交互性结构信息。
考虑重叠问题的特点：同一个子组内的变量彼此直接交互，SUD通过检测某个子组的共享变量组中的所有变量是否彼此交互来判断该子组是否为最小子组。本文通过采用变量-变量组的检测方法提高算法效率，此外，根据重叠问题拓扑结构的不同，可以选择不同的检测机制。例如，对于链式拓扑问题，SUD只需要进行一次交互性检测。对于子组并集，算法对其进一步分解，获得其中的多个最小子组。图3体现了准确性补偿阶段对于OEDG识别重叠问题交互性结构的准确性的提升。
图3：准确性补偿消融实验
3
基准问题
本文从拓扑结构、重叠程度和可分性三方面对现有重叠问题基准进行了扩展，构造了总计59个基准问题，并通过生物基因表达UpSet图刻画了重叠问题变量交互关系。
拓扑类型
本文设置了链式拓扑、环式拓扑和复杂拓扑三种拓扑类型，每种拓扑类型包含12个基准函数，总计36个不同拓扑类型的重叠基准问题。
链式拓扑：采用CEC 2013 LSGO设置方法。
环式拓扑：构造链式拓扑重叠问题首尾子组交互。
复杂拓扑：提出CTOC方法，通过随机决定子组间的交互关系和随机选择共享变量构造复杂拓扑重叠问题。
重叠程度
重叠程度反映了重叠问题中子组的耦合程度，体现在共享变量在所有变量中的比例，根据重叠问题拓扑类型不同，从两方面进行设置。
对于链式拓扑和环式拓扑，改变两个相邻子组间的共享变量数量来设置不同的重叠程度。
对于复杂拓扑，通过改变CTOP中重叠规模和重叠概率两个参数来设置不同的重叠程度。
本文针对链式拓扑、环式拓扑和复杂拓扑三种拓扑类型，各设置5个不同重叠程度的基准函数，共计15个包含不同拓扑结构、不同重叠程度的基准问题。
可分性
基于BNS非加性可分大规模优化问题基准，构造了8个非加性可分链式拓扑重叠问题。
4
实验
本文采用了上述扩展的多组大规模重叠问题基准，分别进行了分解实验、优化实验和扩展实验，来评估本文提出的OEDG的算法的性能。分解实验与三种最先进的针对重叠问题设置的分解方法(RDG、ORDG、DG2)进行比较。在优化实验中，上述四种基于分解的方法的分组结果被整合到CC框架中，并与三种基于非分解的优化方法(CSO、GL-SHADE 、MLSHADE-SPA)进行比较。
分解实验
本文采用函数评估次数来评估不同算法的分解效率，并提出了重叠问题分组准确性指标DA来评估不同算法的分解准确性，DA指标定义如下：
对于不同拓扑类型的重叠问题基准，OEDG获得了最好的分解结果，具有较好的分解效率和较高的分解准确性，分解结果见表1。
表1：不同拓扑类型重叠问题分解结果
对于不同重叠程度类型的重叠问题基准，也表现出较好的分解性能，实验结果见表2。OEDG在较高重叠程度的复杂拓扑重叠问题上未能实现100%准确的分解，原因是随着重叠程度升高，复杂拓扑重叠问题交互性结构复杂度急剧提高，给OEDG算法准确性补偿阶段带来了挑战。
表2：多重叠程度重叠问题分解结果
优化实验
本文将OEDG的优化结果整合到了CBCCO[10]优化框架中，并与3种基于非分解的优化方法和3种基于分解的优化方法对OEDG的优化性能进行了对比，优化结果见表3-5。结果表明，得益于对于重叠问题结构的高效准确识别，OEDG在不同的重叠基准问题上都表现出了较好的优化结果。
表3：不同拓扑类型重叠问题优化结果
表4：不同重叠程度重叠问题优化结果
表5：不同可分类型重叠问题优化结果
扩展实验
为了探究不同类型的优化算法对于不同拓扑结构、不同重叠程度重叠问题的优化表现，并进一步扩展未来的研究方向，本文进行了扩展实验。本文对链式拓扑重叠问题和复杂拓扑重叠问题的重叠程度进一步扩展，讨论基于分解的优化方法和基于非分解的优化方法在这两类问题上的性能。实验结果见图5-6，现有的基于分解的优化方法在处理重叠程度大幅提高的重叠问题时效果劣于整体优化方法，在未来研究中，探索更合理的问题分解方法并利用混合优化框架是解决这些问题的有效途径。
图5：链式拓扑重叠问题优化结果
图6：复杂拓扑重叠问题扩展实验结果
5
总结
本文提出了一种两阶段大规模重叠问题结构识别方法OEDG，两阶段的协同作用保证了OEDG的高效性和准确性，将OEDG的分组结果整合到协同进化框架中，展现了较好的优化性能。本文对重叠问题的性质和分解优化方法进行了全面深入的总结分析，从拓扑类型、重叠程度和可分性三方面扩展了重叠问题基准。
重叠问题的研究尚有多个开放性的方向。首先，可以对重叠问题的性质进行理论分析，并进一步考虑实际问题中重叠问题的建模与优化。其次，设计更高效的协同进化框架解决复杂的大规模重叠问题也有待深入。最后，如何解决冲突共享变量和复杂拓扑结构所带来的优化挑战也是值得深入的课题。
参考文献：
[1] Omidvar M N, Li X, Yao X. A review of population-based metaheuristics for large-scale black-box global optimization—Part I[J]. IEEE Transactions on Evolutionary Computation, 2021, 26(5): 802-822.
[2] Omidvar M N, Li X, Yao X. A review of population-based metaheuristics for large-scale black-box global optimization—Part II[J]. IEEE Transactions on Evolutionary Computation, 2021, 26(5): 823-843.
[3] Chen M, Du W. A Novel Cooperative Co-Evolutionary Framework for Large-Scale Overlapping Problems[C]//2023 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2023: 1-8.
[4] X. Li, K. Tang, M. N. Omidvar, Z. Yang, and Q. K., “Benchmark functions for the CEC’2013 special session and competition on large scale global optimization,” Evolution Computation and Machine Learning Group, RMIT University, Australia, Tech. Rep. ECML-2013 001, 2013.
[5] Omidvar M N, Li X, Mei Y, et al. Cooperative co-evolution with differential grouping for large scale optimization[J]. IEEE Transactions on evolutionary computation, 2013, 18(3): 378-393.
[6] Sun Y, Kirley M, Halgamuge S K. A recursive decomposition method for large scale continuous optimization[J]. IEEE Transactions on evolutionary computation, 2017, 22(5): 647-661.
[7] Ma X, Huang Z, Li X, et al. Merged differential grouping for large-scale global optimization[J]. IEEE Transactions on Evolutionary Computation, 2022, 26(6): 1439-1451.
[8] Sun Y, Li X, Ernst A, et al. Decomposition for large-scale optimization problems with overlapping components[C]//2019 IEEE congress on evolutionary computation (CEC). IEEE, 2019: 326-333.
[9] Omidvar M N, Yang M, Mei Y, et al. DG2: A faster and more accurate differential grouping for large-scale black-box optimization[J]. IEEE Transactions on evolutionary computation, 2017, 21(6): 929-942.
[10] Jia Y H, Mei Y, Zhang M. Contribution-based cooperative co-evolution for nonseparable large-scale problems with overlapping subcomponents[J]. IEEE Transactions on Cybernetics, 2020, 52(6): 4246-4259.
