用图神经网络自动选最佳旅行商求解器，10秒内提升求解质量。
Graph Neural Network-based Algorithm Selection for the Traveling Salesman Problem: A Systematic Study of Cost and Rank Losses under Distinct Budget Regimes
- 直接从原始图数据学实例特征，不用人工设计特征。
- 在10秒和60秒预算下，选出来的解比单个最优求解器更优。
- 适合有性能差异的求解器组合，可做智能调度参考。
自动化算法选择（AS）旨在为每个问题实例从预定义的算法组合中挑选最合适的算法，以提升求解性能。这在旅行商问题（TSP）中尤为重要，因为求解器表现强烈依赖于实例特性。本文提出GNNAS-TSP，一种基于图神经网络（GNN）的AS框架，能直接从原始图数据中学习TSP实例表示，避免了手动特征工程。GNNAS-TSP将算法选择建模为联合成本预测与排序任务。评估了基于成本（均方误差、平均绝对误差、Huber）、基于排序（RankNet、ListNet、LambdaRank）及混合学习目标，在包含链式林-肯尼根、边组装交叉、林-肯尼根-赫尔萨格瑙、多智能体优化系统和康科德求解器的组合上进行实验。使用固定计算预算10秒和60秒。在预留测试集上，所选配置在两个预算下均优于单个最佳求解器（SBS）的归一化解质量。在10秒预算下，算法选择相比SBS实现显著且统计显著的成本改进。结果表明，当求解器间存在可利用的性能差异时，GNNAS-TSP是一种有效的元求解策略。
原文摘要 · Abstract (English)
Automated Algorithm Selection (AS) aims to improve problem-solving performance by selecting, for each problem instance, the most suitable algorithm from a predefined portfolio. This is particularly relevant to the Traveling Salesman Problem (TSP), where solver performance is strongly instance-dependent. We introduce GNNAS-TSP, a Graph Neural Network (GNN)-based AS framework that learns TSP instance representations directly from raw graph data, avoiding manual feature engineering. GNNAS-TSP formulates AS as a joint cost-prediction and ranking task. We evaluate cost-based (mean squared error (MSE), mean absolute error (MAE), and Huber), rank-based (RankNet, ListNet, and LambdaRank), and hybrid learning objectives for a portfolio comprising Chained Lin-Kernighan, Edge Assembly Crossover, Lin-Kernighan-Helsgaun, Multiagent Optimization System, and Concorde. Experiments use fixed computational budgets of 10 and 60 seconds. On the held-out test set, the selected configurations improve on the Single Best Solver (SBS) in normalized solution cost at both budgets. For the 10s budget, AS achieves substantial and statistically significant cost improvement over SBS. Overall, the results suggest that GNNAS-TSP is a useful meta-solving strategy when exploitable variation exists across solver performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。