本文介绍了一项针对最大集合k覆盖问题（Maximum Set k-Covering Problem, MKCP）的原创性研究工作。该研究由Yiyuan Wang、Dantong Ouyang、Minghao Yin、Liming Zhang和Yonggang Zhang共同完成，他们分别来自吉林大学计算机科学与技术学院、吉林大学符号计算与知识工程教育部重点实验室以及东北师范大学计算机科学与信息技术学院。这项研究以论文形式发表，题为“A Restart Local Search Algorithm for Solving Maximum Set k-Covering Problem”，于2016年9月19日在线发表于学术期刊《Neural Computing and Applications》上。以下是对这项研究的全面报告。

一、 研究背景与目标

本研究属于组合优化领域。最大集合k覆盖问题（MKCP）是一个著名的NP难问题，在实际应用中具有广泛背景，例如社交网络分析、网络搜索与广告、城市废物管理中的收集点选址、博客热点话题发现以及网络爬虫内容更新等。该问题可描述为：给定一个由n个元素（变量）构成的集合VAR，以及m个VAR的子集构成的集合SET，目标是选择最多k个子集，使得这些被选子集所覆盖的元素总数最大化。

尽管MKCP具有重要的理论和应用价值，但已有的近似算法在实际应用中的性能表现往往不尽如人意，并且针对该问题的启发式算法研究相对较少。同时，局部搜索算法在求解此类问题时，常常会陷入严重的循环问题（cycling problem），即算法在有限的几个解之间反复振荡，无法跳出局部最优。因此，本研究旨在设计一个高效、鲁棒的启发式算法来解决MKCP。具体目标包括：1）设计一种新颖的随机重启机制，以有效缓解局部搜索中的循环问题；2）开发一种高效的邻域搜索方法，以探索尽可能多的可行搜索区域，从而获得高质量的解；3）通过实验验证所提算法在经典测试实例上的性能，并与商业求解器CPLEX进行比较，证明其优越性。

二、 研究方法与流程

本研究提出了一种名为RNKC（Restart Neighborhood Search Algorithm for MKCP）的重启局部搜索算法。该算法的核心流程主要包含两个关键部分：基于随机重启的初始化构造过程和快速的邻域搜索过程。整个算法的顶层框架（Algorithm 1）是一个循环过程，在给定的时间限制内反复执行：首先，通过随机初始化过程生成一个新的候选解；然后，利用邻域搜索方法对该候选解进行改进；最后，在整个运行过程中记录并更新找到的全局最优解。

1. 随机重启初始化构造过程 (Random_Initial Procedure)

为了克服局部搜索算法易陷入局部最优的循环问题，研究者借鉴了随机重启方法的思想，但并非完全随机地生成初始解，而是设计了一种新颖的、基于“Pro% Top List”的初始化策略。

• 核心定义：算法中定义了“覆盖/未覆盖变量”、“得分（Score）”和“Pro% Top List”等关键概念。一个子集的“得分”定义为：若将其加入候选解，能新覆盖多少当前未被覆盖的变量；若将其从候选解中移除，则会导致多少当前已被覆盖的变量变为未被覆盖。“Pro% Top List”则是一个候选列表，其中包含所有得分不低于当前最高得分乘以一个百分比阈值（实验中设为80%）的子集。
• 操作流程：初始化时，候选解为空。算法迭代k次，每次从当前的“Pro% Top List”中随机选择一个子集加入候选解。特别地，为了避免重启后产生过于相似的初始解，算法在每次重启循环的第一次选择时，会禁止选择上一次重启循环中第一个被加入的子集。每次加入一个子集后，算法会更新所有未选子集的得分以及“Pro% Top List”。这种方法既保证了初始解具有一定的质量（偏向于选择能覆盖更多新元素的子集），又通过随机性确保了重启后初始解的多样性，从而有助于跳出之前的搜索区域。

2. 快速邻域搜索方法 (Neighborhood_Search Procedure)

初始化解可能并非高质量的局部最优解，因此需要利用局部搜索进行改进。RNKC采用了一种简单而有效的邻域结构进行搜索。

• 邻域操作：该方法的核心理念是尝试用外部一个高“得分”（即能覆盖较多当前未覆盖元素）的子集，替换掉候选解内部一个低“得分”（即移除后导致较少覆盖损失）的子集。具体操作（Algorithm 3）如下：算法维护一个包含当前候选解中所有子集的索引列表。在循环中，它首先从索引列表中随机选择一个待移除的子集（cs1）并将其暂时移出候选解。接着，从不在当前候选解中的子集里，选择一个得分最高的子集（cs2）加入候选解，形成一个新的候选解。计算新解覆盖的元素数量，如果优于或等于旧解，则接受此次替换，并更新当前解和覆盖数；如果变差，则撤销此次替换操作（将cs1加回，cs2移除）。这个过程持续进行，直到索引列表为空，即对当前解中的每一个子集都尝试过替换操作且未能找到更优解为止。这种邻域搜索方式能够系统地探索当前解附近的结构，寻找改进机会。

3. 实验设计与评估流程

为了验证RNKC算法的性能，研究者进行了全面的计算实验。

• 测试实例：研究采用了75个著名的MKCP测试实例，这些实例源自经典的集合覆盖问题（SCP）测试库（OR-Library）。这些实例分为两大类：70个随机生成实例（如scp4, scp5, …, scpnrh系列）和5个组合问题实例（如scpcyc, scpclr系列）。实例规模从50个变量/500个子集到上万级别的变量/子集不等，密度从0.02%到20%不等，具有广泛的代表性。
• 参数设置与对比基准：对于每个实例，研究者设定了两个k值：k90和k95，分别代表已知最优覆盖数（Best Known Results, BKR）的90%和95%。算法RNKC用C++实现，在Ubuntu系统上运行。由于算法的随机性，每个实例独立运行10次。算法的时间限制设置为100秒。研究者将RNKC与著名的商业数学优化求解器CPLEX（版本未具体说明，但作为标杆）进行对比，CPLEX的运行时间限制设置为1000秒。
• 评估指标：记录RNKC在10次运行中得到的最大目标值（Max）、平均目标值（Avg）、标准差（SD）以及达到最大目标值所需的平均时间（Time）。同时，记录CPLEX在时间限制内找到的解的下界（LB）和上界（UB）。通过比较RNKC得到的Max/Avg与CPLEX的LB/UB，来评估算法在解的质量和求解效率上的表现。

三、 主要研究结果

实验结果表明，RNKC算法在绝大多数测试实例上表现优异，其性能显著优于商业求解器CPLEX。

1. 在k90设定下的结果：如表3所示，在全部75个实例中，RNKC在60个实例上得到的最大解值（Max）优于CPLEX找到的下界（LB），在13个实例上与CPLEX的下界持平，仅在scp410和scpcyc07两个实例上略逊于CPLEX。特别值得注意的是，对于scpcyc11和scpclr13这两个大规模组合问题实例，RNKC得到的结果（Max: 25906, Avg: 25894.0 和 Max: 4045, Avg: 4043.3）大幅优于CPLEX的下界（13287和3839），显示了RNKC在处理大规模复杂实例上的强大潜力。此外，RNKC在15个实例上达到了100%的成功率（10次运行均找到相同的最优值）。在运行时间方面，RNKC在100秒的时间限制内就达到了这些高质量的解，而CPLEX使用了1000秒。

2. 在k95设定下的结果：如表4所示，在k95（更紧的约束）下，RNKC的优势依然明显。除了scp42和scpcyc08两个实例外，RNKC在其余73个实例上的表现均不差于CPLEX。其中，在62个实例上，RNKC的最大解值超过了CPLEX的下界；在11个实例上，两者结果相同。这进一步证明了RNKC算法在不同难度参数下的鲁棒性。

3. 结果分析与逻辑关系：这些实验结果直接验证了研究流程中两个核心设计的有效性。首先，随机重启初始化构造过程（Pro% Top List策略）成功地生成了多样化且质量较高的初始解，为后续的邻域搜索奠定了良好基础，这是算法能够探索不同搜索区域、避免早熟收敛的关键。其次，快速的邻域搜索方法（替换操作）能够有效地在给定初始解的周围进行精细搜索，快速提升解的质量。两者的结合使得RNKC能够在有限的时间内，频繁地跳出局部最优并探索新的有希望的区域，从而最终获得比专注于精确求解的CPLEX在给定时间内更好的可行解。实验结果与算法设计的目标形成了严密的逻辑闭环。

四、 研究结论与价值

本研究成功设计并实现了一种用于求解最大集合k覆盖问题（MKCP）的重启局部搜索算法RNKC。该算法创新性地结合了改进的随机重启机制和高效的邻域搜索方法。实验结果表明，RNKC在广泛的经典测试集上，其求解质量显著优于商业求解器CPLEX，尤其是在处理大规模实例时优势更为明显，且能在更短的时间内获得优质解。

科学价值：本研究为NP难的MKCP问题提供了一个高效、实用的启发式求解框架。所提出的“Pro% Top List”初始化策略和基于替换的邻域搜索方法，为组合优化中局部搜索算法的设计，特别是如何平衡“强化搜索”和“多样化搜索”以克服循环问题，提供了新的思路和方法论参考。

应用价值：RNKC算法可以直接应用于诸多现实世界的MKCP问题，如网络资源选择、设施选址、信息检索优化等，为这些领域的决策提供快速、高质量的解决方案。其代码实现和实验结果为后续研究者和实践者提供了可靠的基准和比较对象。

五、 研究亮点

1. 问题针对性：针对MKCP这一具有重要应用背景但专门启发式算法较少的问题，开展了深入的研究。
2. 算法设计新颖：提出了新颖的“Pro% Top List”随机重启初始化策略，它不是完全随机的“盲重启”，而是利用问题的结构信息进行有偏好的随机化，兼顾了重启的多样性和初始解的质量。
3. 方法有效且简洁：邻域搜索方法设计简单而有效，通过“低分出、高分进”的替换操作，能够快速在解空间中进行局部寻优。
4. 实验验证充分：在大量标准测试实例上进行了系统性的实验，并与强大的商业求解器CPLEX进行了对比，结果具有说服力，明确展示了算法在求解质量和效率上的优势。
5. 可扩展性：作者在结论中指出，未来可以将RNKC的框架应用于其他优化问题，或结合并行计算等技术进一步提升性能，显示了该研究方向的延续性和潜力。

六、 其他有价值的内容

论文在引言和背景部分详细梳理了MKCP的应用场景和与经典集合覆盖问题（SCP）的联系，为读者理解问题的重要性提供了充分的背景信息。此外，论文在讨论初始化策略时，简要回顾并比较了随机重启方法、禁忌搜索（Tabu Search）和配置检查（Configuration Checking）等几种常见的避免循环策略，体现了作者对相关技术的了解，并解释了选择随机重启方法作为基础进行改进的原因。这些内容为相关领域的研究人员提供了有价值的参考。