用动态选边策略提升旅行商问题求解效率
Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems
- 引入多臂赌博机模型，每轮动态筛选最优候选边
- 在多个基准测试中显著优于传统静态选边方法
- 适用于多种旅行商问题变体，适合算法优化研究者
解决路径规划问题的算法通常依赖高质量的候选边来引导搜索，以缩小搜索空间并提升效率。然而，许多现有算法（如经典求解旅行商问题的Lin-Kernighan-Helsgaun, LKH）采用固定不变的候选边，这种僵化策略可能导致算法陷入局部最优，限制了找到更优解的能力。为此，我们提出扩展候选边集，纳入更多有潜力的边，并通过多臂赌博机模型在每轮迭代中动态选择最合适的候选边，使LKH能做出更明智的选择，从而获得更优解。在多个TSP基准数据集上的大量实验表明该方法表现优异。此外，我们将该方法应用于针对各类TSP变体设计的LKH-3，结果同样显著提升了其在典型TSP变体上的性能。
原文摘要 · Abstract (English)
Algorithms designed for routing problems typically rely on high-quality candidate edges to guide their search, aiming to reduce the search space and enhance the search efficiency. However, many existing algorithms, like the classical Lin-Kernighan-Helsgaun (LKH) algorithm for the Traveling Salesman Problem (TSP), often use predetermined candidate edges that remain static throughout local searches. This rigidity could cause the algorithm to get trapped in local optima, limiting its potential to find better solutions. To address this issue, we propose expanding the candidate sets to include other promising edges, providing them an opportunity for selection. Specifically, we incorporate multi-armed bandit models to dynamically select the most suitable candidate edges in each iteration, enabling LKH to make smarter choices and lead to improved solutions. Extensive experiments on multiple TSP benchmarks show the excellent performance of our method. Moreover, we employ this bandit-based method to LKH-3, an extension of LKH tailored for solving various TSP variant problems, and our method also significantly enhances LKH-3's performance across typical TSP variants.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。