Abstract:

Large-scale overlapping problems are prevalent in practical engineering applications， and the optimization challenge is significantly amplified due to the existence of shared variables. Decomposition-based Cooperative Co-evolution （CC） algorithms have demonstrated promising performance in addressing large-scale overlapping problems. However， certain novel CC frameworks designed for overlapping problems rely on grouping methods for the identification of overlapping problem structures and the current grouping methods for large-scale overlapping problems fail to consider both accuracy and efficiency simultaneously. To address the above problems， a Two-Stage Differential Grouping （TSDG） method for large-scale overlapping problems was proposed， which achieves accurate grouping while significantly reducing computational resource consumption. In the first stage， a grouping method based on the finite difference principle was employed to efficiently identify all subcomponents and shared variables. To enhance both stability and accuracy in grouping， a grouping refinement method was proposed in the second stage to examine the information of the subcomponents and shared variables obtained in the previous stage and correct inaccurate grouping results. Based on the synergy of the two stages， TSDG achieves efficient and accurate decomposition of large-scale overlapping problems. Extensive experimental results demonstrate that TSDG is capable of accurately grouping large-scale overlapping problems while consuming fewer computational resources. In the optimization experiment， TSDG exhibits superior performance compared to state-of-the-art algorithms for large-scale overlapping problems.

Key words: large-scale overlapping problem, differential grouping, Cooperative Co-evolution (CC), computational resource consumption, evolutionary algorithm

摘要：

大规模重叠问题在实际工程应用中普遍存在，重叠问题子组间的共享变量给大规模重叠问题的优化带来了很大困难。基于分解的协同进化（CC）算法在解决大规模重叠问题上表现良好。然而，一些针对重叠问题设计的新型CC框架依赖问题分解方法获得重叠问题结构，而目前针对大规模重叠问题设计的分解方法不能同时兼顾高效性和准确性。为此，提出一种两阶段差分分组（TSDG）方法，在实现精确分组的同时显著减少了计算资源消耗。在第一阶段，采用基于有限差分原理的分组方法高效地识别子组集和共享变量集；第二阶段则提出一种分组改善方法检查前一阶段得到的子组集和共享变量集的信息，改正不准确的分组结果，以提高分组的稳定性和准确性。利用两阶段的协同作用，TSDG实现了对大规模重叠问题高效准确的分解。实验结果表明，TSDG能够在消耗较少计算资源的同时准确地分解大规模重叠问题。在优化实验中，TSDG在大规模重叠问题上的表现也优于对比算法。

关键词: 大规模重叠问题, 差分分组, 协同进化, 计算资源消耗, 进化算法