FastSC:一种针对集合覆盖问题的快速局部搜索算法

《Computers & Operations Research》:FastSC: A fast local search algorithm for the set covering problem

【字体: 大 中 小 】 时间:2026年08月30日 来源:Computers & Operations Research 4.6

编辑推荐:

   摘要 集合覆盖问题(SCP)是经典的组合优化问题之一,具有广泛的应用场景。近年来,许多算法被提出用于求解SCP,尤其是局部搜索算法在求解能力上表现出卓越的性能。在本工作中,我们开发了一种名为FastSC的高效局部搜索算法用于求解SCP。首先,我们提出了一种改进的配置检查策略

  

摘要

集合覆盖问题(SCP)是经典的组合优化问题之一,具有广泛的应用场景。近年来,许多算法被提出用于求解SCP,尤其是局部搜索算法在求解能力上表现出卓越的性能。在本工作中,我们开发了一种名为FastSC的高效局部搜索算法用于求解SCP。首先,我们提出了一种改进的配置检查策略,以防止搜索重复访问之前已探索过的解。其次,我们提出了一种自适应子集选择策略,能够根据实例特性动态调整选择模式。第三,我们实现了一种扰动机制,帮助算法逃离局部最优并探索有前景的解空间。第四,我们提出了一种新的搜索模式,该模式在最优选解下方引入一条间隔线,将解空间划分为两部分,并通过调整间隔线引导算法向高质量解方向收敛。实验结果表明,FastSC与现有的最先进算法具有很强的竞争力,并且在大多数具有挑战性的实例上表现出显著优势。

引言

给定一个元素全集 ?? 和一个子集集合 ??,?? 中的每个子集都是 ?? 中元素的子集,且 ?? 中所有子集的并集包含 ?? 中的所有元素。?? 中的每个子集有一个正整数 ??????????? 作为其代价。集合覆盖问题(SCP)的目标是从 ?? 中选择一组子集,使得它们的并集包含 ?? 中的所有元素,同时所有被选入子集的总代价最小化。SCP 在理论和实践上都具有重要意义,因此引起了研究人员的广泛关注。在理论上,SCP 已被证明是一个 NP 难问题(Karp, 1972),这意味着不存在能在多项式时间内求解 SCP 的算法。在实践中,SCP 已被广泛应用于各种实际场景,例如作业调度(Rubin, 1973, Caprara 等, 1997, Marchiori 和 Steenbeek, 2000)、路径规划(Wu 和 Murray, 2005)、数据库(Munagala 等, 2005)、车辆路径问题(Bramel 和 Simchi-Levi, 1997)、无线传感器网络中的资源分配(Sun, 2017)等。

在近几十年中,大量研究工作致力于开发求解 SCP 的实用算法。在这些研究中,部分研究关注于求解单位代价 SCP(Wang 等, 2017b, Wang 等, 2021, Bautista 和 Pereira, 2007, Gao 等, 2015, Beasley, 2024),其中所有子集具有相同的代价。事实上,单位代价 SCP 是 SCP 的一个特定版本。通过允许子集具有不同的代价,SCP 本质上比单位代价 SCP 更加通用和复杂。例如,警察局、医院和学校等公共设施的选址问题可以被有效地建模为 SCP(Francis 等, 1974, Schilling, 1993, Jain 等, 2013)。城市中的每个社区被视为一个需要被覆盖的元素,每个候选地点被视为一个与唯一代价相关联的子集,任何被选中的候选地点将覆盖一组社区。该问题的目标是:从所有候选地点中选择若干地点,使得每个社区至少被覆盖一次,同时总建设成本最小化。摄像机布设优化也可以建模为 SCP(Kritter 等, 2019),其中目标是:最小化安装在选择位置上的摄像头的总成本,同时确保所有需要监控的区域被充分覆盖。类似地,考虑铁路乘务员调度问题,它也可以自然地建模为 SCP(Heil 和 Buscher, 2020)。具体而言,一系列列车行程必须由选定的乘务员覆盖,目标是使这些乘务员的总成本最小化。由于不同地点关联的成本和不同乘务员的薪酬各不相同,因此将上述问题建模为 SCP 更为合适。因此,在本研究中,我们专注于设计一种求解 SCP 的高效算法。

SCP 在理论和实践上都是一个重要的问题。近年来,大量研究工作致力于开发高效的 SCP 算法。目前,求解 SCP 的主要算法分为精确算法、近似算法和启发式算法。此外,一些约束编码算法也通过将 SCP 转化为其他问题来求解实例。

早期研究采用精确算法(Balas, 1980, Balas 和 Ho, 1980, Beasley, 1987, Beasley 和 J?rnsten, 1992, Etcheberry, 1977, Fisher 和 Kedia, 1990)来处理 SCP,大多数工作基于分支定界或分支切割技术。用于精确算法求解 SCP 实例的常见策略包括:通过使用切割平面来改进界限(Balas, 1980);通过子梯度优化或线性规划松弛的对偶来确定紧致的下界(Balas 和 Ho, 1980, Beasley, 1987, Etcheberry, 1977, Fisher 和 Kedia, 1990);改进分支策略(Beasley 和 J?rnsten, 1992);以及采用对偶路径固定策略来加速分支定界框架(Yamagishi 等, 2026)。虽然精确算法可以保证找到最优解,但当面对大规模 SCP 实例时,这些方法的有效性往往下降,使得此类实例难以被高效求解。

除了精确算法外,早期求解 SCP 的工作也关注了近似算法。为了高效求解 SCP 实例,研究者提出了几种近似算法(Hochbaum, 1982, Levin, 2009, Bansal 等, 2010),这些算法提供了具有理论保证的可行解。然而,在求解 NP 难问题的背景下,具有可证明最坏情况界的近似算法所产生的解通常难以在实践中达到可接受的性能。

为了在可接受的计算时间和解质量之间找到平衡,求解 SCP 的启发式算法也得到了广泛开发。最早提出的求解 SCP 的启发式算法是 Chvatal 的贪心启发式算法(Chvatal, 1979)。此后,一些研究者引入了随机化和概率化方法以进一步改进贪心算法(Feo 和 Resende, 1989, Haouari 和 Chaouachi, 2002, Lan 和 DePuy, 2006),这些方法通常能获得比纯贪心算法更好的解。近期关于贪心启发式算法的研究在解的构建过程中引入了惊奇值的计算(Adamo 等, 2023),显著改进了 Chvatal 的经典贪心算法。除了贪心算法外,大量研究还提出了各种其他启发式算法用于求解 SCP,包括遗传算法(Beasley 和 Chu, 1996, Solar 等, 2002, Bagherinejad 等, 2017, Tayebi 等, 2024)、模拟退火(Jacobs 和 Brusco, 1995, Brusco 等, 1999, Gonzalez 和 Burtscher, 2025)、蚁群算法(Al-Shihabi 等, 2015, Crawford 等, 2014, Sadeghi 等, 2018)、拉格朗日松弛启发式(Beasley, 1990a, Caprara 等, 1999, Ceria 等, 1998)以及局部搜索(Feo 和 Resende, 1995, Gao 等, 2014, Reyes 和 Araya, 2021, Hashemi 等, 2022, Hashemi 等, 2025, Carrabs 等, 2024)。近年来,局部搜索在求解 SCP 方面表现出卓越的性能。Lei 和 Cai(2020)提出了一种结合化简规则的局部搜索算法,通过简化输入实例来减少问题规模,并辅以有效的选择策略和搜索机制在化简空间中寻找解。该方法在求解 SCP 方面展现出显著的性能优势。随后,Beasley(2024)提出了一种通用的数学启发式算法,将贪心初始化与基于汉明距离的局部分支机制相结合,迭代扩展搜索范围以寻找改进的解。此外,Luo 等(2022)引入了元素动态权重方案以及用于子集选择的新组合评分函数。他们的算法在广泛的 SCP 实例上优于其他算法。为了进一步增强算法性能,他们还设计了一个名为 GenSC 的通用参数化局部搜索框架(Luo 等, 2026)用于求解 SCP。该框架配备了多样化的强大算法技术,由自动配置器自动选择和组合。目前,GenSC 在大多数实例上表现出优秀的性能,是最新的 SCP 局部搜索算法。

除了一些专门的 SCP 算法外,约束编码算法也是求解 SCP 的一类常见算法。这些算法首先将给定的 SCP 实例转化为另一个 NP 难问题的实例,然后利用相应的约束算法来处理转化后的实例(Hoffman 和 Padberg, 2009, Saxena 等, 2010, Yelbay 等, 2014)。最常用的约束编码算法是最大可满足性问题(MaxSAT)算法。该方法首先将 SCP 实例编码转化为 MaxSAT 实例——将 SCP 实例中的每个元素视为一个约束,并在该约束中添加包含该元素的子集——然后由 MaxSAT 求解器进行求解(Berg 等, 2019, Nadel, 2019, Chu 等, 2022)。然而,大多数现有的 MaxSAT 求解器都是通用求解器,并未针对 SCP 实例进行优化。因此,MaxSAT 求解器在求解 SCP 实例方面的效率并不令人满意。

在本文中,我们设计了一种局部搜索算法来求解 SCP。我们致力于引入四种新策略以提高算法的效率。本工作的主要贡献总结如下:

第一,我们提出了一种名为 CCV3 的改进配置检查(CC)策略。配置检查策略(Wang 等, 2016, Cai 等, 2013, Wang 等, 2017a, Abramé 等, 2017, Luo 等, 2014)已被广泛应用于局部搜索中以防止循环问题(即重复访问相同的解)。它通过检查子集的配置是否发生变化来决定是否添加该子集。然而,当存在多个具有相同配置的候选子集时,随机选择其中一个可能会遗漏一些更有前景的解。为了解决这一问题,CCV3 进一步使用三种不同的值来区分子集的配置。配置值较高的子集在添加过程中会被赋予更高的优先级。

第二,我们提出了新的元素和子集选择策略,以及自适应子集选择策略。在元素选择阶段,我们利用 CCV3 的搜索信息来指导元素选择。在子集选择阶段,我们通过引入一个辅助概率来自适应调整选择次优子集的概率。此外,基于实例特性,我们进一步设计了一种自适应子集选择策略,在不同实例上选择不同的策略。

第三,我们设计了一种扰动机制来干扰搜索过程。尽管提出的 CCV3 策略可以克服循环问题,但它难以处理算法陷入局部最优的情况。受基于锁定和解锁操作的一般扰动机制的启发(Chen 等, 2023),我们为 SCP 开发了一种专门的扰动机制。具体来说,我们移除候选解中的一些子集以创建一个不可行解,然后锁定剩余子集,在解锁空间中搜索找到可行解。

第四,我们引入了一种利用间隔线加速收敛至更高质量解的搜索策略。间隔线是一个小于最优解代价的正整数,在搜索过程中动态调整。它将解空间中的解代价划分为两部分:第一部分专注于在间隔线以下寻找可行解,第二部分探索最优解的邻域。通过优先处理第一部分并动态调整间隔线,算法可以有效地添加或移除子集以发现更优的可行解。

基于上述思路,我们提出了一种名为 FastSC 的新型局部搜索算法用于求解 SCP。为了评估 FastSC 的性能,我们在广泛的基准测试集上进行了实验。我们将算法与几种现有的最先进 SCP 局部搜索算法进行了比较。由于 SCP 问题可以通过将 SCP 实例转化为 MaxSAT 问题来求解,我们还比较了近年来在 MaxSAT 竞赛中表现优异的算法。实验结果表明 FastSC 达到了优越的性能。此外,消融实验的结果表明每种策略都对算法的性能提升有正面影响。

在下一节中,我们介绍一些定义和技术。在第3节中,我们描述算法的总体框架。在第4节中,我们提出改进的配置检查策略。在第5节中,我们提出自适应选择策略。

第 6 节介绍了扰动机制。第 7 节展示了 FastSC 算法的详细信息。随后,我们进行了实验以评估我们的算法。最后,我们给出了一些结论性说明。

章节片段
预备知识
给定一个包含 ?? 个元素的集合 ??={??1,??2,…,????} 和一个由 ?? 个子集组成的集合 ??={??1,??2,…,????},其中 ???????,且 ?? 中所有子集的并集是 ?? 的全集。每个子集 ????∈?? 都有一个正整数 ???????? 作为其成本,我们用 ?? 表示所有子集的成本集合,即 ??={????????(??1),????????(??2),…,????????(????)}。因此,我们将一个 SCP 实例表示为 ??=(??,??,??)。给定元素 ????∈?? 和子集 ????∈??,如果 ????∈????,则我们视 ???? 被包含在 ???? 中,即 ???? 是 ????-包含的。

FastSC 框架
在本节中,我们首先介绍算法的预处理和初始化方法,然后提供我们的 FastSC 算法的一般框架。

一种改进的配置检查策略
CC 策略已成功应用于许多 NP 难组合优化问题的局部搜索算法中,例如团(Wang et al., 2016)、顶点覆盖(Cai et al., 2013)、支配集(Wang et al., 2017a)、布尔可满足性(SAT)(Abramé et al., 2017)和 MaxSAT(Luo et al., 2014)。CC 策略的工作原理如下:最初,所有变量的配置值被设置为 1,这意味着所有变量都允许被添加到候选解中。在搜索过程中,一个

一种自适应子集选择策略
在本节中,我们引入了新颖的元素和子集选择策略。此外,利用实例的特性,我们进一步设计了一种自适应子集选择策略。

扰动机制
局部搜索算法通常使用一些扰动方法来增加解的多样性并探索一些有前景的空间(Cai et al., 2017b, Wang et al., 2020, Xu et al., 2019)。一个好的扰动方法可以帮助搜索跳出陷阱并找到更好的解决方案。在本节中,我们通过结合解决方案信息和一种新颖的选择策略,提出了一种改进的扰动机制。

FastSC 算法
在本节中,我们引入了一条间隙线,基于当前最佳解的成本将搜索空间分为两部分。为了引导算法走向高质量解决方案,我们提出了更新规则以在搜索过程中动态调整间隙线。随后,我们展示了我们 FastSC 算法的搜索细节。

实验评估
我们进行了实验,在广泛的基准测试上评估了所提出的 FastSC 算法。首先,我们将 FastSC 与几种现有的最优算法进行了比较,并分析了它们之间的关键差异。然后,我们验证了算法中使用的所提出策略的有效性。最后,我们对参数设置进行了详细分析。

结论
在本文中,我们提出了一种名为 FastSC 的有效局部搜索算法来解决 SCP。特别是,我们提出了一种改进的配置检查策略 CCV3 来处理循环问题,并设计了一种自适应子集选择策略来选择要添加到候选解中的子集。然后,我们设计了一种扰动机制来帮助我们的算法扰乱一些搜索空间并快速收敛到新的解决方案。最后,我们通过引入间隙线来引导设计了一种搜索模式

CRediT 作者贡献声明
吴洁宇(Jieyu Wu):原创草稿撰写、验证、方法论、调查、概念化。
潘诗伟(Shiwei Pan):原创草稿撰写、验证、方法论、概念化。
王一原(Yiyuan Wang):审阅与编辑、原创草稿撰写、方法论、概念化。
尹明浩(Minghao Yin):审阅与编辑、原创草稿撰写、方法论、概念化。

致谢
本工作得到中国国家密码科学基金 2025NCSF02046 和国家自然科学基金(批准号 61806050)的资助。

吴洁宇 | 潘诗伟 | 王一原 | 尹明浩
东北师范大学信息科学与技术学院,中国长春
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号