arXiv:2510.11121cs.LG2025-10被引 5

小模型经强化学习微调后生成的交叉算子超越人工设计,提升车辆路径求解效率。

Refining Hybrid Genetic Search for CVRP via Reinforcement Learning-Finetuned LLM

  • 用强化学习微调小模型,生成可编译、可执行且性能优的交叉算子
  • 在1000节点的大规模问题上,新算子显著优于人工设计的算子
  • 适合需要高效求解车辆路径问题的研究者与工业应用

尽管大型语言模型(LLMs)被越来越多地用于自动设计车辆路径问题(VRPs)的启发式算法,但当前最先进的方法主要依赖于像GPT-4这样的大规模通用模型。本文挑战这一范式,证明经过精心微调的小型专用LLM能生成性能超越人工设计启发式的组件。我们提出RFTHGS,一种用于微调小型LLM以生成高性能交叉算子的强化学习框架,应用于混合遗传搜索(HGS)求解容量限制车辆路径问题(CVRP)。该方法采用分层课程奖励函数,逐步引导模型生成可编译、可执行,最终表现优于人类专家设计的算子。结合算子缓存机制,避免重复并促进多样性。大量实验表明,微调后的LLM生成的交叉算子在小规模到1000节点的大规模实例中均显著优于原版专家设计算子,且性能超越主流神经组合优化基线、提示驱动方法及商用LLM如GPT-4o和GPT-4o-mini。

原文摘要 · Abstract (English)

While large language models (LLMs) are increasingly used as automated heuristic designers for vehicle routing problems (VRPs), current state-of-the-art methods predominantly rely on prompting massive, general-purpose models like GPT-4. This work challenges that paradigm by demonstrating that a smaller, specialized LLM, when meticulously fine-tuned, can generate components that surpass expert-crafted heuristics within advanced solvers. We propose RFTHGS, a novel Reinforcement learning (RL) framework for Fine-Tuning a small LLM to generate high-performance crossover operators for the Hybrid Genetic Search (HGS) solver, applied to the Capacitated VRP (CVRP). Our method employs a multi-tiered, curriculum-based reward function that progressively guides the LLM to master generating first compilable, then executable, and finally, superior-performing operators that exceed human expert designs. This is coupled with an operator caching mechanism that discourages plagiarism and promotes diversity during training. Comprehensive experiments show that our fine-tuned LLM produces crossover operators which significantly outperform the expert-designed ones in HGS. The performance advantage remains consistent, generalizing from small-scale instances to large-scale problems with up to 1000 nodes. Furthermore, RFTHGS exceeds the performance of leading neuro-combinatorial baselines, prompt-based methods, and commercial LLMs such as GPT-4o and GPT-4o-mini.

车辆路径强化学习小模型启发式优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。