在大型图中针对加权总支配问题进行的广泛邻域搜索及深度优化

《Knowledge-Based Systems》：A large neighborhood search with deep optimization for the weighted total domination problem in massive graphs

　　书丽·胡 | 文文 | 翟玲 | 姜琪丽 | 苗子清 | 李瑞志 | 尹明浩
东北师范大学信息科学与技术学院，长春，中国

**摘要**
加权总支配问题（WTDP）是总支配集问题的一个重要推广，它结合了顶点权重和边权重，以优化实际应用中的成本，例如信息传播和分布式网络设计。在这项研究中，我们设计了一种高效的大型邻域搜索与深度优化的破坏-修复-改进算法，用于处理大规模图中的WTDP问题，整个过程分为三个阶段。首先，我们应用了两种新的简化策略来减小原始图的大小，然后提出了一种贪婪启发式方法来构造一个有希望的初始解。其次，我们应用了一种新型的破坏-修复-改进大型邻域搜索算法来细化初始解。为了指导搜索过程，我们提出了一种新的顶点选择策略，该策略结合了动态评分函数和增强型的三值两级配置检查机制。为了改进解的质量，我们引入了三种操作符：收缩、交换和扩展，以获得有希望的高质量解。第三阶段，当大型邻域搜索长时间未能改进解时，我们通过引入策略性扰动来避免局部最优解。我们在352个基准实例上评估了我们的算法，包括37个大规模真实世界图和315个合成实例。在大型图上，它获得了29个新的上界，并与五个最佳已知结果相匹配。在较小的实例上，它获得了6个新的上界，并与309个最佳已知结果相匹配。这些结果证明了我们方法的优异解质量和在大多数情况下的竞争效率。

**引言**
在无向图中，支配集是一部分顶点，图中的每个顶点要么属于这个子集，要么与其相邻。作为图论中的一个基本概念，由于在无线自组织网络中的单向链接[1]、多文档摘要[2]、社交网络[3]等领域的广泛应用，支配集已经被广泛研究。支配集的一个严格推广是总支配集（TDS），它满足图中的每个顶点（包括TDS中的顶点）都必须与TDS中的至少一个顶点相邻的条件。因此，TDS问题在实际场景中成为一个更稳健的模型。最小总支配集（MTDS）问题是找到具有最小基数的TDS。MTDS可以应用于需要总支配性来提高系统可靠性的领域，例如分布式网络设计[4]、自组织无线网络[5]和网关放置问题[6]。然而，在许多现实世界场景中，节点和边与不同的消耗成本相关联，这增加了使用加权图来建模这些问题的需求。在这项研究中，我们解决了加权总支配问题（WTDP），它是MTDS问题的一个推广，目的是找到具有最小顶点和边总成本的TDS。在简单的无向图中，MTDS是NP难的[7]，而当所有顶点权重设置为1且边权重设置为0时，WTDP也是NP难的[8]。

WTDP将顶点权重和边权重都纳入总支配模型中，提供了更好的建模能力。一个显著的应用是减少社交网络中信息传播的成本。它选择关键成员作为中介，这些关键成员影响他们的邻居，以确保网络中的每个个体至少有一个渠道来获取信息。即使关键成员也需要与其邻域内的另一个关键成员至少有一个连接，以确保持续可靠的访问信息。在现实环境中，考虑多个成本因素（包括关键成员的雇佣成本、到达每个非关键成员的最小传播成本以及关键成员之间的通信成本）是至关重要的。图1展示了一个例子，其目标是识别具有最小总成本的关键成员集。

**最近的研究**
由于WTDP的广泛应用，许多研究人员提出了各种方法。这些方法可以分为两类：精确算法和启发式算法。马等人[8]（2019年）首次提出了三种整数线性规划（ILP）公式用于WTDP，并在Erd?s–Rényi随机图上对其进行评估，图的大小为|V|∈{20,50,100}，获得了45个实例（简称为MA）。他们的模型可以在1800秒的时间限制内将所有20个和50个顶点的实例求解为最优解，而在100个顶点的实例中没有一个可以在时间限制内求解为最优解，而且获得的可行解通常存在较大的最优性差距。álvarez-Miranda和Sinnl[9]（2021年）引入了两种混合整数规划（MIP）公式，称为F1和F2，并将它们嵌入到分支剪枝框架中，得到了加强的变体F1+和F2+。其中，F2+是最有效的精确方法：它将所有45个MA实例都求解为最优解，并且比马等人的ILP公式快500倍，在|V|=50的情况下。在新的AMS基准集上，该集的大小为|V|∈{75,100,125}，F2+在时间限制内将135个实例中的112个求解为最优解。我们注意到，尽管MA和AMS都包含|V|=100的实例，但MA使用的是[1,5]范围内的随机权重，而AMS是在固定权重范围内生成的。总体而言，他们的精确方法可以在1800秒内处理多达125个顶点的实例。

随后，Kapunac等人[10]（2023年）重新实现了[9]中的F2公式作为代表性的精确基线，因为分支剪枝变体（F1+和F2+）无法从可用信息中重建，且对他们研究的更大实例不实用。最终的F2模型只能将一些最多125个顶点的实例求解为最优解，并且在他们扩展的NEW基准集（|V|∈{250,500,1000}）中未能在1800秒内解决任何实例。这些结果进一步说明了精确算法在处理大规模图时的有限可扩展性，从而激发了开发启发式和元启发式方法来处理大规模图的兴趣。álvarez-Miranda和Sinnl[9]（2021年）开发了一种遗传算法（GA），其中初始解是通过贪婪随机自适应搜索程序（GRASP）构建的。这种启发式方法从完整的顶点集开始，移除那些导致目标值最大下降的顶点，直到没有移除操作能够带来改进为止。它通过GRASP程序引入了一些随机性，然后通过局部搜索评估单顶点翻转操作。交叉是通过获取两个父支配集的并集来实现的，这是在基于集合的解表示下的自然选择，并应用相同的贪婪移除和局部搜索程序来细化并集。此外，变异随机移除一部分顶点，然后应用他们的原始启发式方法来恢复可行性，再进行局部改进。选择基于解的大小和目标值。在他们的实验中，作者认为具有较小种群规模的GA1是一个稳健的设置，在这种选择下，他们的GA在135个AMS实例中的105个实例内获得了最佳解。此外，GA在他们提出的F1、F2、F1+和F2+方法都无法解决的实例上表现更好，只有在精确方法已经达到最优解的情况下才不及它们。

Kapunac等人[10]（2023年）为WTDP提出了一种基本的变邻域搜索（VNS）算法，从随机生成的初始解开始。摇动程序通过每次迭代增加一个单位被移除的顶点数量来探索逐渐增大的邻域。结合了两种首次改进的局部搜索：1-反转操作符（LS1）和1-交换操作符（LS2），在交换之前还尝试插入一个顶点，这种策略已被证明是有效的。为了指导搜索，作者设计了一个能够评估可行和不可行解的适应度函数。此外，他们重新实现了álvarez-Miranda和Sinnl[9]的GRASP和GA方法，并通过生成135个NEW实例（|V|∈{250,500,1000}来进一步扩展了基准集，在这些实例上，他们的VNS获得了107个最佳已知解，而GA和GRASP分别获得了64个和1个。在AMS实例上，VNS获得了135个最佳结果中的132个，略低于re-MIP在两个实例上获得的最优结果，但在另一个实例上的表现比re-MIP差1.33%。在AMS和NEW两个基准集上，它的平均运行时间与GA相当。

Wen Sun等人[11]（2024年）为WTDP提出了一种基于知识的迭代局部搜索（KILS）算法。在进行了1度简化后，KILS从完整的顶点集开始，并根据搜索过程中积累的历史信息向量迭代移除顶点来构建初始可行解。随后的基于解的迭代局部搜索过程采用了两阶段局部搜索方法。这包括使用移除-插入和翻转操作进行最佳改进探索，然后在实现对最佳解的改进时进行学习驱动的扰动。为了避免重复访问先前探索的解，KILS使用每个解派生的六个哈希向量。在315个基准实例（MA、AMS、NEW）和27个真实世界实例（SNAP）上的实验表明，KILS获得了所有最佳已知结果，报告了93个新的上界，并与249个现有最佳结果相匹配（包括所有165个已知最优解）。它的性能也优于re-MIP、re-GA和VNS[10]，同时在MA和AMS组上的运行时间不到它们的10%。

Casado等人在2024年的一篇会议论文[12]中首次为WTDP提出了一种基本的VNS启发式方法，其中初始解是通过简单的偏向性GRASP构建的。他们在随后的期刊文章[13]（2025年）中开发了一个更全面的框架，基于跳跃变量邻域搜索（JVNS），并方法论上研究了多种构建策略和局部搜索组件。特别是，他们检查了三种构建策略：一种基于直接评估目标函数；第二种根据可行性应用两个比率规则；以及一种基于概率采样从结合质量和多样性的分数中选择顶点的偏向性抓取构建（BGC）。这些构建与两种局部改进程序结合使用：预测性局部搜索，在执行移动之前预测目标值；以及限制探索到可行邻域解的减少局部搜索（RLS）。初步测试表明，BGC与RLS结合提供了最有效的初始解。使用这种初始化，作者调整了JVNS，它与基本VNS的不同之处在于它以固定跳跃改变邻域大小，而不是逐个增加，并且还在他们的研究中研究了多启动JVNS变体。最终的BGC-GRASP+JVNS配置优于精确方法和álvarez-Miranda和Sinnl[9]重新实现的GA。JVNS在MA实例上解决了44个问题，在AMS集合上获得了124个最佳解，而GA只解决了112个，且运行时间大约减半。在扩展的CSM集合（|V|∈{200,350,500}）上，JVNS找到了所有最佳解，而GA只找到一个，这展示了其明显的优越性。

除了这些传统的元启发式方法之外，Simunics[14]（2024年）提出了一些预处理简化方法，并为自适应大型邻域搜索（ALNS）设计了一组破坏和修复启发式方法，结合了图神经网络（GNN）引导的破坏操作符，这些操作符使用顶点分数作为WTDP的选择权重。这种在搜索期间自适应选择的破坏和修复操作符组合是ALNS的特征，而传统的大型邻域搜索（LNS）通常使用单一的固定破坏和修复方案。GNN在AMS基准集（|V|∈{75,100,125}上进行了训练和评估。对于每一类，生成了1000个训练图和250个验证图。与基线ALNS相比，GNN引导的ALNS将达到已知最佳解的运行比例从大约81%略微提高到85%，并且在不同的运行和实例类别中表现出相当大的方差。不同的GNN架构显示出几乎相同的ALNS性能，用随机值替换学习到的分数得到的结果与基线相似。与álvarez-Miranda和Sinnl[9]的GA相比，ALNS变体（无论是否带有GNN指导）总体上表现相当，在较不密集的图上表现略好，而在更密集的图上GA表现更好。因此，作者得出结论，进一步的改进更有可能来自于改进ALNS方法，而不是开发更复杂的GNN模型。这一结论与他们的实验观察结果一致，即尽管ALNS变体使用了更丰富的破坏和修复操作符，但其改进效果仍然较为有限。根据文献，目前针对WTDP表现最佳的启发式算法是Wen Sun等人[11]（2024年）提出的KILS。KILS已经在包括MA（|V|∈{20,50,100}）、AMS（|V|∈{75,100,125}）、NEW（|V|∈{250,500,1000}）以及27个实际SNAP实例（|V|范围从1912到82,168）在内的多种基准测试中得到了验证。它在所有352个实例上都取得了最佳结果，并报告了93个新的上界值。其他具有竞争力的启发式算法包括Kapunac等人[10]（2023年）提出的VNS和Casado等人[13]（2025年）提出的JVNS。尽管这些方法是在不同的基准测试集上评估的，但它们报告的结果都显示出了较强的性能。在NEW实例上，VNS报告了107个最佳已知结果；在CSM集（|V|∈{200,350,500}）上，JVNS报告了135个最佳已知结果。在AMS上，VNS和JVNS分别取得了132和124个最佳结果；在MA上，VNS解决了所有45个实例，而JVNS解决了44个实例。至于精确算法，álvarez-Miranda和Sinnl[9]（2021年）提出的MIP模型是最有效的。其中，F2公式后来被Kapunac等人[10]（2023年）重新实现为re-MIP，该算法在相应研究的时间限制内将MA、AMS、NEW和SNAP集合中的总共165个实例解决了最优解。

为了清晰起见，所回顾的算法按时间顺序在表1中进行了总结。本研究提出了一种高效的大邻域搜索算法，名为DeepOpt-LNS，用于解决大规模图中的WTDP问题。该算法整合了几种新颖策略。首先，我们开发了两种有效的简化规则来减小原始图的大小，并提供了这些规则正确性的正式证明。然后使用一种贪婪启发式方法来构建高质量的初始解。基于此，我们设计了一个新的破坏-修复-改进的LNS框架。在这个框架内，引入了一种顶点选择策略，该策略结合了一个动态评分函数和一个增强的两级三值配置检查机制。为了进一步强化搜索，提出了三种专门的改进操作符——收缩、交换和扩展。此外，为了逃避局部最优解并保持搜索多样性，DeepOpt-LNS在搜索停滞时通过战略性扰动整合了深度优化技术。最后，我们通过引入更大的实际图实例扩展了现有的基准测试，并进行了全面实验以证明所提算法的有效性。

本文的其余部分组织如下：第2节介绍了用于构建WTDP的基本定义和符号。第3节介绍了支持候选解评估的辅助函数。第4节描述了整个DeepOpt-LNS框架。第5节介绍了贪婪构建和简化策略。第6节详细介绍了大邻域搜索过程，第7节介绍了深度优化技术。第8节提供了实验结果和分析。最后，第9节总结了本文并指出了未来工作的方向。

初步知识
给定一个无向图G(V,E)，V是顶点集，E是边集。顶点和边的数量分别为n和m。用e(u,v)表示连接顶点u和v的边。每个顶点v∈V被赋予一个正整数权重w(v)，每条边e∈E被赋予一个正整数权重c(e)。函数dist(u,v)表示顶点u和v之间的最小跳跃次数。用Ni(v)={u∣dist(u,v)=i,u∈V}表示顶点v的第i层邻居集。我们定义Nk(v)=?

用于高效评估的辅助函数
在介绍整体搜索框架和详细的邻域策略之前，我们介绍了一些能够高效评估候选解的辅助机制。首先，我们介绍了一些在整个算法中反复使用的辅助概念和更新机制。

WTDP要求解决方案满足两个基本方面：(i)可行性，即选定的顶点集必须构成一个TDS；以及(ii)最优性，这可以通过...

DeepOpt-LNS框架
上述辅助函数被整合进来以提高计算效率。本节介绍了所提出的DeepOpt-LNS算法的整体框架，该框架将增强的扰动机制（DeepOpt）与LNS框架相结合。完整的伪代码在算法3中提供，图4展示了执行流程。算法首先对输入图应用简化规则，然后构建一个可行的且有希望的初始解。

贪婪构建与新简化策略
为了在保持效率的同时构建高质量的初始解，我们设计了新的简化策略来减小图的大小。然后，应用贪婪构建过程来获得初始解。初始解构建的这两个组件在本节中有详细介绍。

LNS框架
LNS已被证明对许多组合优化问题有效，包括旅行商问题[16]、车辆路由[17]等。在传统的局部搜索中，邻域较小，因为每次移动只会导致微小的变化（例如，交换或重新定位一个或两个元素），从而产生多项式数量级的潜在下一步解集。在LNS中，邻域较大，因为许多元素被移除后会被最优或启发式地重建。

深度优化与轻量级改进
为了在LNS停滞时逃避局部最优解，我们借鉴了DeepOpt[22]的思想，引入了一种基于扰动的优化机制，该机制对于大规模图特别有效。在其原始设计中，DeepOpt首先移除某些顶点以多样化搜索，而当前解决方案中的其余元素被暂时锁定。在第二阶段，搜索被限制在受移除影响的指定深度内的局部解空间内。

实验评估
本节报告了所提出的DeepOpt-LNS算法的实验评估。我们首先介绍了研究中使用的基准实例（第8.1节）和用于比较的算法（第8.2节）。接下来，我们介绍了实验设置，包括实验程序、计算环境、参数配置以及在所有结果表中一致使用的符号（第8.3节）。然后，我们报告了所有基准组的实验结果。

结论
在这项工作中，我们提出了一种名为DeepOpt-LNS的大邻域搜索与深度优化算法，用于解决WTDP问题。它包含三个关键部分：两种新的改进简化策略、结合动态评估函数和增强型树值两级配置检查的新顶点选择策略，以及具有深度优化的破坏-修复-改进大邻域搜索。结果表明，DeepOpt-LNS显著优于当前最先进的WTDP启发式算法。

作者贡献声明
胡淑丽：撰写——审阅与编辑、撰写——初稿、验证、软件、方法论、调查、形式分析、概念化。文文：撰写——审阅与编辑、撰写——初稿、验证、软件、方法论、调查、形式分析、概念化。凌典：撰写——审阅与编辑、可视化、验证、软件、形式分析。李嘉琪：撰写——审阅与编辑、调查、形式分析、数据整理。廖志清：撰写——利益冲突声明
作者声明他们没有已知的竞争财务利益或个人关系可能影响本文所述的工作。