核心发现
方法论
本文提出一种基于在线模仿学习的框架，将GRASP的随机构造阶段转化为序列生成任务，利用解的高质量轨迹训练Transformer策略。该方法无需预训练或外部数据，通过行为克隆在每个实例上自我学习。局部搜索作为专家，生成高质量轨迹，策略通过自回归模型条件化历史决策，逐步构建解。实验中，模型在Taillard PFSP基准上实现28.4单位的平均改进，优于GPU-GRASP的提升27.2单位，验证了实例特定、在线训练语言模型的潜力。
关键结果
- 在Taillard PFSP（ta51-ta60）基准上，LM-GRASP平均比GPU-GRASP提升28.4个单位的完工时间，表现优异，尤其在半未知最优解的复杂实例中效果显著。
- 该方法无需离线预训练，完全依赖实例内高质量轨迹，展现出在复杂景观中超越静态启发式的能力。
- 实验还显示，硬件加速（GPU）带来的性能提升与算法改进相当，说明学习策略在实际应用中具有可比性和实用性。
研究意义
该研究突破了传统依赖静态启发式规则的限制，提出一种无需预训练、可在线自我学习的实例特定生成模型，为组合优化提供了全新思路。其核心在于利用深度Transformer模型捕获解空间的长距离结构依赖，显著提升复杂实例的求解质量。这不仅降低了设计门槛，也为未来自适应、泛化能力强的智能优化系统奠定基础。尤其在解决高维、复杂景观的调度、路径等问题时，展现出广阔的应用前景。
技术贡献
本文创新性地将序列生成模型引入组合优化的随机构造阶段，通过行为克隆实现实例特定的策略学习，避免离线预训练。提出的框架结合局部搜索的专家指导，利用动态轨迹存档不断优化策略，完全依赖目标函数接口，无需特征工程或问题特定知识。模型采用decoder-only Transformer，条件化历史决策，捕获非局部依赖，突破传统贪婪启发式的局限。该方法在没有外部数据的情况下实现高效学习，为组合优化中的自适应策略提供新范式。
新颖性
这是首个将Transformer序列生成模型从零开始、在线训练应用于实例特定组合优化的工作。不同于预训练的语言模型或离线学习策略，LM-GRASP在每个实例上实时自我学习，完全免除外部数据和预训练成本，显著提升了模型的适应性和泛化能力。其创新点在于将随机构造转化为序列生成任务，利用行为克隆实现端到端学习，开辟了组合优化中深度学习应用的新路径。
局限性
- 该方法在极端复杂或高维实例中可能面临训练时间较长的问题，尤其是在轨迹存档不足时策略的泛化能力有限。
- 模型依赖局部搜索作为专家，若搜索陷入局部最优，可能影响策略的质量和稳定性。
- 目前仅在PFSP问题上验证，其他类型的组合优化问题还需进一步验证其通用性。
未来方向
未来可探索多任务、多实例的联合训练策略，提升模型的泛化能力；结合强化学习优化轨迹存档策略；扩展到其他组合优化问题如路径规划、装箱等，验证其广泛适用性。同时，研究模型的可解释性和训练效率，推动其在工业调度、物流等实际场景中的应用落地。
AI 总览摘要
传统的组合优化方法多依赖静态、手工设计的启发式规则，难以应对复杂多变的实例环境。近年来，深度学习尤其是Transformer模型在序列生成中的成功激发了将其引入优化领域的兴趣。本文提出的LM-GRASP框架，创新性地将随机构造阶段转化为序列生成任务，通过在线模仿学习自我训练，避免了昂贵的离线预训练和特征工程。核心思想是利用局部搜索作为专家，生成高质量轨迹，并用Transformer模型条件化历史决策，逐步构建解。实验在Taillard PFSP基准上取得了28.4单位的平均改进，显著优于传统GPU加速的GPU-GRASP（27.2单位），验证了实例特定、端到端学习策略的有效性。这一方法不仅突破了静态启发式的局限，也为未来自适应、泛化能力强的智能优化系统提供了新思路。其无需外部数据、可在单实例上实时训练，具有极高的实用价值和推广潜力。未来工作将聚焦于多实例训练、模型解释性以及在工业调度、路径规划等多领域的应用推广，推动深度学习在组合优化中的深度融合。
深度分析
研究背景
组合优化在调度、路径规划、资源分配等领域具有广泛应用。传统方法如分支界限、启发式算法虽有效，但在大规模复杂实例中计算成本高昂。近年来，深度学习引入序列模型、强化学习等技术，推动了自动化设计的边界。Pointer Networks、Transformer在路径问题中的应用，展示了学习构造解的潜力。然而，现有方法多依赖离线预训练或大量数据，缺乏针对单一实例的自适应能力。本文试图突破这一瓶颈，提出无需预训练、在线自我学习的策略，旨在实现高效、泛化强的实例特定优化。
核心问题
现有深度学习方法在组合优化中面临两个主要挑战：一是离线预训练成本高，难以快速适应新实例；二是静态启发式规则缺乏全局视野，限制解质量。传统启发式如GRASP的随机构造虽简洁，但受制于局部贪婪，难以捕获复杂结构。如何在保证效率的同时，提升解的质量和适应性，成为关键难题。本文关注的核心问题是：能否设计一种无需离线数据、能在实例内自我学习的构造策略，从而突破静态启发式的局限？
核心创新
核心创新包括：1）将随机构造转化为序列生成任务，利用Transformer模型条件化历史决策，捕获长距离依赖；2）引入在线模仿学习，利用局部搜索生成高质量轨迹，动态更新策略；3）完全免除预训练和特征工程，依赖目标函数接口实现端到端学习。这些创新使得模型能在每个实例上自我训练，适应性强，突破了传统方法的局限。
方法详解
- �� 初始化：用局部搜索生成一批高质量轨迹，作为训练示范。
- �� 行为克隆：利用轨迹中的状态-动作对，训练Transformer模型，使其学会模仿专家决策。
- �� 生成策略：模型条件化历史决策，逐步生成解的构造序列。
- �� 在线更新：在搜索过程中不断积累新轨迹，周期性重新训练模型。
- �� 目标接口：仅通过目标函数评价，避免特征工程。
- �� 终止条件：达到时间预算或满足解质量要求。
实验设计
采用Taillard PFSP（ta51-ta60）实例，比较LM-GRASP、GPU-GRASP和CPU-GRASP的性能。设置5小时时间限制，指标为完工时间（makespan）。模型参数包括Transformer层数、温度等，进行消融分析验证不同设计的影响。通过多次随机初始化，确保结果的稳健性。实验重点在于不同方法在复杂实例中的表现差异，以及模型训练的收敛性。
结果分析
在复杂的ta50×20实例上，LM-GRASP平均提升28.4单位，优于GPU-GRASP（27.2单位），在未公开最优解的实例中表现尤为突出。模型无需离线预训练，完全在实例内自我学习，展现出强大的适应能力。硬件加速带来的性能提升与算法改进相当，验证了深度模型在实际应用中的潜力。消融实验显示，模型条件化历史决策显著优于无条件模型，强化了序列建模的有效性。
应用场景
该方法适用于工业调度、路径规划、资源分配等场景，特别是在实例复杂、结构多变的环境中。无需大量预训练数据，只需在实际实例中运行局部搜索和模型训练，即可获得高质量解。未来可结合实时数据流，实现动态调度和自适应优化，提升工业生产效率。
局限与展望
模型训练时间较长，尤其在极端复杂实例中可能影响实时性。依赖局部搜索的质量，若搜索陷入局部最优，策略效果受限。当前仅在PFSP上验证，其他问题类型的适应性和效果仍需验证。未来需优化训练效率和模型泛化能力，以适应更广泛的应用场景。
通俗解读 非专业人士也能看懂
想象你在厨房做饭，要准备一道复杂的菜肴。传统方法是按照固定的食谱一步步操作，虽然简单但不够灵活。现在，假设你可以根据每次尝试的结果，自己学习出最适合当前食材的做法。每次尝试后，你会记住哪些步骤效果最好，然后在下一次做菜时，直接用这些经验优化流程。LM-GRASP就像这个厨师，它在每次做菜时都能自己学习，不依赖固定的食谱，而是根据实际情况不断调整，最终做出更美味的菜肴。这种方法比传统的死板规则更聪明，也更适应不同的食材和环境。
简单解释 像给14岁少年讲一样
想象你在玩一个超级复杂的游戏，比如解谜或建造城堡。以前的方法就像用一份固定的攻略，每次都照着做，效果还不错但不够聪明。而现在，有个聪明的朋友会观察你怎么玩，然后自己学习，告诉你哪些步骤最有效。每次你玩完，他都会记住你的好方法，下一次就能帮你更快更好地完成任务。这就是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.