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

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