LM-GRASP: Instance-Specific Language Models for Combinatorial Construction via Online Imitation Learning
作者: Mohand Mezmaz, Grégoire Danoy
分类: cs.LG
发布日期: 2026-07-30
💡 一句话要点
提出LM-GRASP以解决组合优化中的实例特定学习问题
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 组合优化 在线模仿学习 局部搜索 数据驱动 Transformer 元启发式方法 实例特定学习
📋 核心要点
- 现有的组合优化方法依赖于大量离线数据进行预训练，导致高成本且在新问题上泛化能力差。
- 本文提出LM-GRASP，将GRASP的构造过程转化为在线模仿学习，利用局部搜索作为专家，动态训练构造策略。
- 在Taillard PFSP基准测试中，LM-GRASP的表现优于GPU-GRASP，平均提升28.4个工期单位，显示出实例特定学习的潜力。
📝 摘要（中文）
机器学习在组合优化中的应用通常依赖于通过强化学习训练的神经构造器，这需要大量的离线数据集进行预训练，且在训练分布之外的泛化能力较差。本文提出了一种替代方案：将GRASP的随机构造阶段重新表述为在线模仿学习任务，针对每个问题实例从零开始训练。通过局部搜索程序作为专家oracle，解码器仅使用Transformer作为构造策略。与传统GRASP依赖静态启发式规则不同，我们的方法完全基于数据驱动，构造策略源自搜索过程中发现的高质量解，且无需特定问题的特征工程。LM-GRASP作为一种混合元启发式方法，遵循迭代的学习-推理-改进周期，通过行为克隆在线训练策略，无需外部数据或离线预训练。
🔬 方法详解
问题定义：本文旨在解决组合优化中现有方法的高预训练成本和泛化能力差的问题。传统方法依赖于静态的启发式规则，难以适应新的问题实例。
核心思路：LM-GRASP通过将构造过程视为在线模仿学习任务，针对每个问题实例进行动态训练，利用局部搜索程序作为专家oracle，从而实现数据驱动的构造策略。
技术框架：LM-GRASP的整体架构包括三个主要模块：在线模仿学习模块、局部搜索模块和动态档案管理模块。在线模仿学习模块负责从局部搜索中获取高质量解并训练构造策略；局部搜索模块提供优化解的反馈；动态档案管理模块存储精英轨迹以供训练使用。
关键创新：LM-GRASP的核心创新在于其完全数据驱动的构造策略，避免了传统方法中对问题特征的手动工程设计，且能够在每个实例上进行在线训练。
关键设计：在设计中，LM-GRASP使用解码器仅的Transformer网络作为构造策略，损失函数基于行为克隆，确保策略能够有效学习局部搜索的优质解。
🖼️ 关键图片
📊 实验亮点
在Taillard PFSP基准测试中，LM-GRASP的平均表现优于GPU-GRASP，提升幅度达到28.4个工期单位，显示出其在组合优化问题中的有效性和实用性。这一结果与GPU加速的效果相当，表明在线训练的语言模型在实例特定学习中具有重要价值。
🎯 应用场景
LM-GRASP的研究成果在组合优化领域具有广泛的应用潜力，尤其是在需要快速适应不同问题实例的场景中，如生产调度、物流优化和资源分配等。其在线学习的特性使得该方法能够在动态环境中持续改进，提升决策效率。
📄 摘要（原文）
Machine learning for combinatorial optimization typically relies on neural constructors trained via reinforcement learning on large offline datasets for a fixed problem class-incurring high pretraining costs and generalizing poorly outside the training distribution. We propose an alternative: a metaheuristic framework that reformulates the randomized constructive phase of GRASP as an online imitation learning task, trained from scratch on each problem instance. A local search procedure acts as an expert oracle, while a decoder-only Transformer serves as the constructive policy. Unlike classical GRASP, which relies on static, myopic heuristic rules based on localized scalar costs, our approach is fully data-driven: the construction policy emerges from high-quality solutions discovered during the search itself, with no problem-specific feature engineering required. We instantiate this as LM-GRASP, a hybrid metaheuristic following an iterative learn-infer-improve cycle, training the policy online via behavioral cloning on a dynamic archive of elite trajectories-no external data or offline pretraining needed. The pipeline interfaces with the domain solely through the objective evaluator used by local search. Evaluated on the Taillard PFSP benchmark (ta51-ta60), the most discriminating block due to half its optima being unknown, LM-GRASP outperforms GPU-GRASP by 28.4 makespan units on average-comparable to the gain from GPU acceleration over sequential execution (27.2 units), though with overlapping standard deviations. This suggests instance-specific, online-trained language models are a promising, practical alternative to hand-engineered constructors, especially for landscapes resistant to classical greedy construction.