用图神经网络指导禁忌搜索,加速战术无线网络设计优化。
Machine Learning-Enhanced Tabu Search for Tactical Wireless Network Design

- 基于搜索轨迹训练GNN,预测候选动作效果以减少评估次数。
- 实验显示计算时间显著降低,解的质量持续优于传统方法。
- 适合需要高效求解大规模网络设计问题的研究者。
在真实作战约束下设计高性能战术无线网络会产生复杂的组合优化问题,候选方案的评估依赖于详细的物理与流量感知模型。尽管经典元启发式算法如禁忌搜索(Tabu Search)能有效探索大搜索空间,但其计算成本高,因每轮迭代需评估大量候选移动。本文提出一种数据驱动框架,通过学习引导禁忌搜索的移动选择过程,提升效率。不改变邻域结构,而是利用优化过程中生成的搜索轨迹信息:每轮记录改进与非改进的基于边的变换及其对应的结构、几何和性能特征。这些数据用于训练图神经网络(GNN),以预测候选移动对目标函数的影响。训练好的模型被集成到禁忌搜索中,按预测质量对候选变换排序,从而减少昂贵的目标函数评估次数,同时保持有效的搜索空间探索。在合成基准实例上的实验表明,所提出的机器学习增强禁忌搜索显著降低计算时间,并始终产生比标准算法更高质量的解。结果凸显了结合机器学习与元启发式算法的潜力,通过挖掘搜索轨迹中的隐含知识,为大规模网络设计问题提供更高效的求解方法。
原文摘要 · Abstract (English)
Designing high-performance tactical wireless networks under realistic operational constraints gives rise to challenging combinatorial optimization problems, where the evaluation of candidate solutions relies on detailed physical and traffic-aware models. Although classical metaheuristics such as Tabu Search offer effective mechanisms for exploring large search spaces, their computational cost remains high because numerous candidate moves must be evaluated at every iteration. In this paper, we propose a data-driven framework that improves the efficiency of Tabu Search by learning to guide its move selection process. Rather than altering the neighborhood structure, our approach exploits the information contained in the search trajectories generated during the optimization process. At each iteration, we record both improving and non-improving edge-based transformations together with a set of descriptive features capturing the structural, geometric, and performance characteristics of the network. This information is used to train a Graph Neural Network (GNN) that predicts the impact of candidate moves on the objective function. The trained model is then integrated into the Tabu Search algorithm to rank candidate transformations according to their predicted quality, thereby reducing the number of costly objective evaluations while maintaining an effective exploration of the search space. Experimental results on synthetic benchmark instances demonstrate that the proposed learning-assisted Tabu Search notably reduces computation time while consistently producing higher-quality solutions than the standard algorithm. These findings highlight the potential of combining machine learning with metaheuristics by leveraging the implicit knowledge embedded in search trajectories, paving the way for more efficient solution methods for large-scale network design problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。