双罗马支配问题：一种迭代局部搜索方法

《Engineering Applications of Artificial Intelligence》：Double Roman Domination Problem: An iterated local search approach

　　

近年来，图支配问题吸引了学术界与实践界的广泛关注。在这类问题中，需要选取一个顶点子集，使得图中的每个顶点要么属于该子集，要么与至少一个被选顶点相邻。其中，最广泛扩展的变体之一是罗马支配问题（RDP），其通过为顶点赋值来在特定防护规则下保证覆盖。该研究针对双罗马支配问题（DROMDP），这是RDP的一个更为严格的扩展，其中施加了更强的支配条件，以保证即使在潜在顶点失效的情况下仍能维持覆盖。

本文提出了一种基于迭代局部搜索（ILS）的算法框架，并结合两种构造过程、两种局部搜索方法以及两种扰动机制，以求解高质量解。所得结果与当前最先进的方法——基于蚁群优化（ACO）的方法——进行了比较，结果表明，ILS是求解DROMDP最具竞争力的算法。上述结论得到了大规模计算实验的支持，其中包括对不同组成部件的消融研究、统计检验，以及关于ILS在任意实例上成为最佳算法概率的贝叶斯分析。

本文发表于《Engineering Applications of Artificial Intelligence》，研究对象为双罗马支配问题（DROMDP, Double Roman Domination Problem），属于图支配（graph domination）与组合优化领域中的重要NP-hard问题。研究背景在于，图支配模型能够刻画通信网络监测、无线传感器部署、公共服务调度、信息传播以及网络安全防护等多类现实任务。与经典支配集问题相比，罗马支配问题（RDP, Roman Domination Problem）通过标签赋值方式表达资源防护强度，而双罗马支配问题则进一步提高了对节点覆盖与冗余的要求，使网络在节点故障或攻击情境下仍具备可用性与鲁棒性。因此，DROMDP比RDP更贴近高可靠网络设计需求，但也带来了更高的求解难度。

现有问题主要体现在两个方面。其一，DROMDP已被证明为NP-hard问题，说明在现实规模网络上难以依靠精确算法获得可接受时间内的最优解。其二，虽然已有研究提出了相应求解方法，但在解质量、计算代价以及算法稳定性方面仍有进一步提升空间。特别是在复杂网络结构下，如何高效探索可行标记空间，并在保证可行性的同时尽可能降低目标函数值，即最小化所有节点标签之和，仍是该问题的核心挑战。基于上述原因，开展针对DROMDP的高效近似算法研究具有明确理论价值与应用意义。

论文首先对问题进行了形式化定义。给定图G=(V,E)，其中V为节点集合，E为边集合，定义函数f:{1,2,…,n}→{0,1,2,3}为每个节点赋予标签。DROMDP要求满足如下约束：若f(v)=0，则v至少应有两个邻居节点被赋值2，或者至少一个邻居节点被赋值3；若f(v)=1，则v至少应有一个邻居节点被赋值2或3；若f(v)≥2，则无需附加约束。在此基础上，目标函数定义为最小化∑_v∈Vf(v)。该定义体现出DROMDP并非单纯追求覆盖，而是在覆盖约束下进一步追求资源配置成本最小化。研究人员还通过示例说明了不可行解、可行解与最优解之间的差异，帮助明确问题的约束结构与优化目标。

为求解该问题，研究人员提出了一种迭代局部搜索（ILS, Iterated Local Search）算法。该算法由初始化、扰动和局部改进三个核心阶段构成，并且每个阶段均设计了两种可替代策略，以增强算法的适应性与搜索能力。初始化阶段采用两种贪婪构造方式：一种从DROMDP的平凡劣解出发并逐步改造，另一种从理论上最优但不可行的解出发，在达到可行性时停止。扰动阶段通过修改一定比例节点的标签来实现搜索多样化，并设计了两种扰动机制。局部改进阶段则围绕节点次序展开，一种按节点度升序遍历，另一种按相反顺序遍历，通过持续尝试降低目标函数值来强化解的质量。整体上，该方法遵循元启发式（metaheuristic）的一般思想，即在局部开发与全局探索之间保持平衡，以在短时间内逼近高质量可行解。

用于开展研究的主要关键技术方法可概括如下：第一，采用迭代局部搜索（ILS）作为总体元启发式框架，通过“构造—局部优化—扰动—再优化”的循环进行解空间搜索；第二，设计两类贪婪初始化策略，分别从可行劣解与不可行优起点构造初始解；第三，设计两类局部搜索策略，依据节点度排序方向不同对标签配置进行改进；第四，设计两类扰动机制，通过部分节点标签修改增强跳出局部最优的能力；第五，采用消融实验、统计检验与贝叶斯分析评估各算法组件贡献及整体优越性。论文未涉及样本队列来源问题，实验对象为DROMDP测试实例集合。

研究结果部分可以依据论文主体中的小标题进行概括。

State of the art
该部分综述了DROMDP的研究现状，并说明其在网络安全建模中的现实意义。研究人员指出，DROMDP能够体现更高层次的可用性与冗余性，因此比一般支配模型更适于刻画节点失效或遭受攻击下的安全网络设计问题。文中同时指出DROMDP具有NP-hard性质，甚至在若干特殊图类上依然难解。这一综述为后续采用近似算法而非精确算法提供了理论依据，也明确了本文工作相对于既有研究的切入点，即在保持较低计算代价的前提下改进求解性能。

Algorithmic approach
该部分系统介绍了所提出的ILS算法。研究人员认为，由于DROMDP属于NP-hard问题，面对真实复杂网络时，精确方法并不适用，近似算法更具实际可行性。因此，论文选择以ILS作为算法骨架，因为局部搜索通常是元启发式中最有力的组成部分，而ILS正是围绕局部搜索进行构建。该方法从一个初始解出发，经局部搜索到达局部最优，再通过扰动操作跳出当前区域，继续进行局部改进，由此反复迭代。该部分的核心结论是：通过为初始化、局部搜索和扰动三大模块分别设计双变体，算法能够更有效利用问题结构信息，在保证搜索效率的同时提高解质量。

Computational results
该部分用于验证算法性能，并分析各组成部分的作用。研究人员将所提方法实现于Java 21环境，并在Apple M4平台上进行计算实验。实验不仅包含最终算法与现有最先进方法的比较，还包括参数设定与组件贡献评估。根据摘要与结论信息，计算结果表明，ILS在DROMDP求解中表现出显著竞争力，优于基于蚁群优化（ACO, Ant Colony Optimization）的现有代表性方法。进一步地，消融实验表明，不同构造方式、局部搜索策略和扰动机制均对最终性能产生实质影响，说明算法设计并非单一组件驱动，而是多个模块协同作用的结果。统计检验与贝叶斯分析进一步增强了结论可信度，其中贝叶斯分析显示，所提ILS在任意实例上成为最佳算法的概率达到92%。这一结果说明，该方法不仅在平均性能上占优，而且具有较强的稳健性。

Conclusions
该部分总结指出，本文提出了一种能够在较短计算时间内为DROMDP找到高质量解的ILS算法。算法设计包含两种构造方法、两种局部搜索过程以及两种扰动机制，并对它们进行了系统比较。研究结果表明，这些启发式策略能够利用问题特定信息探索有前景的搜索区域，而无需付出过大的计算代价。这一结论通过广泛计算实验得到了支持。换言之，研究人员证明了，针对DROMDP这类具有严格可行性约束的图优化问题，精心设计的ILS框架能够在效率与解质量之间取得良好平衡，并具有超越现有先进方法的实际效果。

从全文看，论文的重要意义主要体现在三个层面。第一，在方法层面，研究构建了一个面向DROMDP的专用ILS框架，并通过多变体设计提升了元启发式求解该类图优化问题的精细化程度。第二，在实验层面，论文不仅报告结果，还通过消融研究、统计检验和贝叶斯分析系统评估组件贡献与算法优势，提高了结果的透明性与可重复性。第三，在应用层面，DROMDP对高可靠网络中的冗余防护建模具有直接价值，因此更优的求解算法有助于通信网络、安全基础设施与相关资源部署问题中的优化决策。

对讨论部分进行凝练可知，论文强调DROMDP所刻画的是一种更严格、更贴近现实网络安全需求的支配机制。由于问题本身复杂，算法设计必须充分结合其约束结构。本文通过构造、局部优化与扰动机制的组合，展示了问题知识驱动的启发式设计如何在不增加过多计算成本的前提下提升性能。实验结果也说明，面向复杂组合优化问题时，模块化元启发式框架与针对性搜索策略的结合，是获得稳定高质量结果的有效路径。

研究结论部分可译为：本研究提出了一种ILS算法，用于在较短计算时间内为DROMDP寻找高质量解。该ILS设计包括两种构造方法、两种局部搜索过程以及两种扰动机制，并对这些方法进行了展示与相互比较。所提出的启发式方法利用了问题的特定信息，以在无需大量计算开销的情况下探索搜索空间中的有前景区域，这一点已通过大规模计算实验得到证明。