机器学习增强的 Tabu Search 用于战术无线网络设计

# 机器学习增强的禁忌搜索用于战术无线网络设计
来源：https://arxiv.org/html/2608.28627

###### 摘要
在现实的作战约束条件下设计高性能战术无线网络，会带来具有挑战性的组合优化问题，其中候选解决方案的评估依赖于详细的物理模型和流量感知模型。尽管经典的元启发式算法（如禁忌搜索）为探索大规模搜索空间提供了有效的机制，但由于每次迭代都需要评估大量候选移动，其计算成本依然很高。本文提出了一种数据驱动的框架，通过学习来指导禁忌搜索的移动选择过程，从而提升其效率。我们的方法并非改变邻域结构，而是利用在优化过程中生成的搜索轨迹所包含的信息。在每次迭代中，我们记录基于边的改进与非改进变换，以及一组描述性特征，这些特征捕捉了网络的结构、几何和性能特性。利用这些信息训练一个图神经网络，以预测候选移动对目标函数的影响。随后，将训练好的模型集成到禁忌搜索算法中，根据预测质量对候选变换进行排序，从而减少代价高昂的目标函数评估次数，同时保持对搜索空间的有效探索。在合成基准实例上的实验结果表明，所提出的学习辅助禁忌搜索在显著减少计算时间的同时，能够持续产生比标准算法质量更高的解决方案。这些发现突显了通过利用搜索轨迹中蕴含的隐式知识，将机器学习与元启发式算法相结合的潜力，为大规模网络设计问题的更高效求解方法铺平了道路。

*关键词：* 战术无线网络设计；机器学习；元启发式；图神经网络。

## 1 引言
无线通信系统在传统电信基础设施不可用、受损或不足的环境中扮演着至关重要的角色。这在应急响应、军事行动和偏远地区部署中尤其如此，必须快速部署临时战术无线网络，以确保地理分散位置之间的可靠通信。此类网络的设计自然产生了一个具有挑战性的组合优化问题。需要做出若干相互依赖的决策，包括选择一个中心协调节点、构建可行的网络拓扑以及配置通信链路和无线资源。这些决策对网络性能有重大影响，因为它们直接影响信号质量、干扰水平和有效吞吐量。

元启发式方法，如禁忌搜索，为解决这类优化问题提供了灵活且有效的框架。它们特别适用于那些由于巨大的搜索空间和评估候选解决方案的高计算成本而使精确方法变得不切实际的实例。然而，禁忌搜索算法的效率关键取决于其邻域的探索方式。在战术无线网络设计问题中，每次迭代可能涉及大量的候选拓扑修改，穷举评估所有修改在计算上可能是禁止的。这一观察促使我们将机器学习集成到搜索过程中。学习组件并非替代优化算法，而是旨在通过识别更有可能产生高质量解决方案的候选移动来指导邻域探索。这样，机器学习在元启发式中充当决策支持机制，使算法能够在保持原始优化框架的可行性约束和评估程序的同时，专注于搜索空间中最有希望的区域。

在本文中，我们提出了一种用于战术无线网络设计的机器学习引导的禁忌搜索算法。所提方法从先前生成的搜索轨迹中学习，在候选邻域移动进行昂贵的计算评估之前对其进行优先级排序。目标是在保持（甚至可能提高）所获得解质量的同时，提高搜索效率。

这项工作对战术无线网络设计问题做出了若干贡献。我们提出了一个机器学习引导的优化框架，将学习组件集成到搜索过程中，以提高优化过程的效率。我们还开发了一个基于图的学习模型，该模型利用网络的结构特征和依赖于解的特征来识别有前景的邻域移动。最后，我们进行了广泛的计算研究，以评估所提方法的有效性，并分析学习组件对解质量、搜索效率和性能的影响。

本文其余部分的组织结构如下。第2节（https://arxiv.org/html/2608.28627#S2）介绍战术无线网络设计问题。第3节（https://arxiv.org/html/2608.28627#S3）回顾关于无线网络设计、元启发式以及用于组合优化的机器学习的相关文献。第4节（https://arxiv.org/html/2608.28627#S4）描述基线拓扑禁忌搜索算法，包括其边交换邻域结构。第5节（https://arxiv.org/html/2608.28627#S5）介绍所提出的机器学习引导框架。它描述了学习引导的移动选择策略、训练数据集的生成以及基于图神经网络的边分类器设计，包括特征表示、网络架构和训练目标。第5.5节（https://arxiv.org/html/2608.28627#S5.SS5）随后介绍了完整的机器学习引导禁忌搜索算法。计算实验和性能分析在第6节（https://arxiv.org/html/2608.28627#S6）报告。最后，第7节（https://arxiv.org/html/2608.28627#S7）总结了论文并概述了未来的研究方向。

## 2 问题描述
完整的战术无线网络设计问题的详细描述见\[1 (https://arxiv.org/html/2608.28627#bib.bib1)\]。在本节中，我们简要回顾理解所提出的学习引导禁忌搜索框架所需的主要元素。该问题的实例由一组n个节点定义，每个节点关联固定的地理坐标。网络必须构建为连接所有节点的树形拓扑。选定一棵树后，一个节点被指定为总控枢纽（master hub），树从此根节点向外定向。总控枢纽充当中心协调节点，而每个其余节点恰好有一个前驱节点，可以有多个后继节点。

每个节点都配备一个无线电接口，连接到两个多波束天线。无线电在两个信道上运行，每个信道可以分配两个可用传输频率之一。通信链路可以在点对点（PTP）模式（节点与单个后继节点通信）或点对多点（PMP）模式（节点同时服务于多个后继节点）下运行。这些设计选择，结合天线配置和信道/频率分配，决定了信号质量、链路间干扰，最终影响可实现的网络吞吐量。

图1（https://arxiv.org/html/2608.28627#S2.F1）引自\[1 (https://arxiv.org/html/2608.28627#bib.bib1)\]，说明了网络设计过程的主要步骤。给定初始节点集，首先构建树形拓扑以建立所有节点之间的连接性。然后选择一个节点作为总控枢纽（图中由黑色方块表示）。直接连接到总控枢纽的节点随后被分为两组：一组灰色节点（示例中为两个节点）和一组白色节点（示例中为一个节点）。该图还突出了不同的链路配置：实线表示点对点连接，而虚线表示点对多点连接。然后分配通信信道，图中以红色和蓝色分别表示两个信道。最后，为每个信道分配传输频率；例如，红色信道使用4500 MHz和5000 MHz的频率，而蓝色信道使用2000 MHz和2400 MHz的频率。该图未显示激活的天线波束或其精确方向，它们通过单独的几何过程确定。请参见图1说明：图1：战术无线网络设计过程示意图，引自\[1 (https://arxiv.org/html/2608.28627#bib.bib1)\]。

在这一阶段，区分拓扑、配置和由此产生的解决方案非常重要。一个拓扑T仅指定网络的连通性，即哪些节点对通过边连接。在评估其性能之前，必须做出许多额外的配置决策。以下示例说明了这些决策的性质。必须首先从n个节点中选择一个作为总控枢纽。如果选定的枢纽有x个邻居，则这些邻居可以以2^{x-1}种不同的方式分为两组。此外，必须为每条边分配两个可用频率之一，从而产生2^{n-1}种可能的频率分配。这些只是配置过程中涉及的决策的一些示例，它们之间存在很强的相互依赖性。因此，单个拓扑可能允许极其大量的可行配置。

\[1 (https://arxiv.org/html/2608.28627#bib.bib1)\]中提出的流程结合了多种启发式方法，将搜索限制在有限的有希望的候选集中，从而构建了这样一个配置。尽管生成的配置通常质量良好，但对于给定的拓扑，并不保证最优性。在本文其余部分中，我们将应用于拓扑T的此启发式配置过程产生的解决方案表示为s(T)。理想情况下，一个拓扑的质量应由其最佳可行配置的目标值来定义。由于穷举评估拓扑诱导的所有配置在计算上难以处理，我们转而通过上述过程返回的启发式解s(T)来评估拓扑。

我们现在定义用于评估任何解s的目标函数f(s)。设s是一个边集为E的解。对于每条边uv∈E，使用物理层模型计算直接吞吐量TP_{uv}，该模型考虑了信号特性以及在相同频率上运行的链路之间的干扰。有关此计算的更多详细信息，请参阅\[1 (https://arxiv.org/html/2608.28627#bib.bib1)\]。

考虑三种流量场景。设n^X_{uv}表示边uv在场景X下承载的流数量，d_v表示在有根有向树中节点v的后代数量。在场景A中，每条边关联单个流，因此n^A_{uv}=1。场景B对应于总控枢纽与所有其他节点之间的同时通信；在这种情况下，如果边从u指向v，则n^B_{uv}=d_v，否则n^B_{uv}=d_u。最后，场景C考虑每对节点之间的双向通信。当边从u指向v时，由此产生的边负载为n^C_{uv}=2d_v(|V|-d_v)，否则为n^C_{uv}=2d_u(|V|-d_u)。

目标是最大化三种场景下最小有效吞吐量和平均有效吞吐量的加权组合。具体来说，p控制这两个标准之间的权衡，ω_X表示与场景X∈{A,B,C}相关的权重，目标函数f(s)定义为：

f(s) = \sum_{X \in \{A,B,C\}} \omega_X \left( \min_{uv \in E} \frac{TP_{uv}}{n^X_{uv}} + p \cdot \operatorname*{mean}_{uv \in E} \frac{TP_{uv}}{n^X_{uv}} \right).

设计约束限制了可行拓扑的集合，因此并非每棵树都对应一个有效的网络拓扑。例如，总控枢纽最多连接20个邻居节点，而其他每个节点最多连接11个邻居。任何违反一个或多个这些约束的拓扑T被认为是不可行的，相应解的目标值通过设置f(s(T)) = -\infty进行惩罚。

尽管具有启发式性质，但从拓扑T生成解s(T)的配置过程在计算上仍然昂贵。因此，本讨论的关键要点是应尽可能减少调用此过程的次数。

## 3 文献综述
机器学习在组合优化领域引起了越来越多的关注，特别是对于那些精确方法在大规模或复杂实例上计算不可行的问题。Bengio等人\[2 (https://arxiv.org/html/2608.28627#bib.bib2)\]提供了一个全面的方法论概述，介绍了如何将学习技术集成到优化算法中，以直接构建解决方案或支持特定的算法决策。

更具体地说，Cappart等人\[3 (https://arxiv.org/html/2608.28627#bib.bib3)\]研究了图神经网络在组合优化和推理中的应用，强调了它们利用许多优化问题底层图结构的能力。类似地，Peng等人\[18 (https://arxiv.org/html/2608.28627#bib.bib18)\]综述了图学习方法，并讨论了如何利用基于图的表示来学习结构化优化问题的决策策略。

已有多种基于学习的方法被提出来增强精确和启发式优化算法。例如，Khalil等人\[10 (https://arxiv.org/html/2608.28627#bib.bib10)\]引入了一个用于混合整数规划中变量分支的机器学习框架，其中模型从强分支信息中学习分支决策。Gasse等人\[8 (https://arxiv.org/html/2608.28627#bib.bib8)\]将混合整数规划表示为二分图，并采用图卷积神经网络结合模仿学习，以改进分支定界算法中的分支决策。类似地，Paulus和Krause\[17 (https://arxiv.org/html/2608.28627#bib.bib17)\]开发了一种基于学习的分支定界深度搜索策略，其中图神经网络预测变量赋值并指导原始启发式决策。这些研究表明，机器学习可以有效地学习那些传统上基于计算昂贵的程序或手工设计启发式的算法决策。

许多组合优化问题可以自然地表示为图，这使得图神经网络特别适合于在此类设置中学习决策规则。Dai等人……（后续内容按相同原则翻译）