用在线搜索提升神经优化算法，让小模型也能高效解大问题。
Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation
- 引入有限回溯束搜索策略，改进深度强化学习的组合优化方法。
- 在欧式旅行商问题上，最优解差距优于现有启发式方法。
- 支持离线与在线自适应，适合需要快速调整的工业场景。
我们提出有限回溯束搜索（LRBS），一种基于深度强化学习的组合优化改进启发式方法。利用在欧氏旅行商问题（Euclidean TSP）上预训练的模型，LRBS显著提升了分布内性能和对更大实例的泛化能力，达到的最优解差距优于现有改进启发式方法，并缩小了与顶尖构造性方法的差距。我们还将分析扩展至两种接送类TSP变体以验证结果。最后，我们采用该搜索策略实现预训练改进策略的离线与在线自适应，进一步提升搜索性能，超越近期针对构造性启发式的自适应方法。
原文摘要 · Abstract (English)
We introduce Limited Rollout Beam Search (LRBS), a beam search strategy for deep reinforcement learning (DRL) based combinatorial optimization improvement heuristics. Utilizing pre-trained models on the Euclidean Traveling Salesperson Problem, LRBS significantly enhances both in-distribution performance and generalization to larger problem instances, achieving optimality gaps that outperform existing improvement heuristics and narrowing the gap with state-of-the-art constructive methods. We also extend our analysis to two pickup and delivery TSP variants to validate our results. Finally, we employ our search strategy for offline and online adaptation of the pre-trained improvement policy, leading to improved search performance and surpassing recent adaptive methods for constructive heuristics.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。