面向大规模重叠问题的两阶段差分分组方法  

Two-stage differential grouping method for large-scale overlapping problems

作　　者：田茂江 陈鸣科 堵威 杜文莉[1] TIAN Maojiang;CHEN Mingke;DU Wei;DU Wenli(Key Laboratory of Smart Manufacturing in Energy Chemical Process,Ministry of Education(East China University of Science and Technology),Shanghai 200237,China)

机构地区：[1]能源化工过程智能制造教育部重点实验室(华东理工大学),上海200237

出　　处：《计算机应用》2024年第5期1348-1354,共7页journal of Computer Applications

基　　金：国家重点研发计划项目(2022YFB3305900);国家自然科学基金面上项目(62173144);上海市青年科技启明星计划项目(22QA1402400);上海人工智能实验室资助项目。

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]