用课程学习提升遗传编程求解大规模车辆路径问题的性能
Curriculum Learning in Genetic Programming Guided Local Search for Large-scale Vehicle Routing Problems
- 按难易程度逐步引入训练实例，引导模型渐进学习
- 在三个基准方法上实现显著性能提升
- 适合需要高效求解大规模路径优化的工程场景
手动设计车辆路径问题（VRP）的（元）启发式算法是一项极具挑战性的任务，需大量领域知识。近年来，数据驱动方法成为有前景的解决方案，能自动学习在训练实例上表现良好且可泛化到未见测试实例的启发式算法。一种名为GPGLS的方法利用遗传编程（GP）学习引导局部搜索（GLS）中的效用函数，有效求解大规模VRP。然而，学习过程中训练实例的选择仍是一个开放问题，现有研究（包括GPGLS）多依赖随机选择。为此，本文提出新方法CL-GPGLS，将课程学习（CL）引入GPGLS。该方法利用预定义的课程，逐步引入训练实例，从简单任务开始，逐步增加复杂度，使模型更好地适应并优化大规模VRP（LSVRP）。大量实验验证了CL-GPGLS的有效性，在三个基准方法上均实现显著性能提升。
原文摘要 · Abstract (English)
Manually designing (meta-)heuristics for the Vehicle Routing Problem (VRP) is a challenging task that requires significant domain expertise. Recently, data-driven approaches have emerged as a promising solution, automatically learning heuristics that perform well on training instances and generalize to unseen test cases. Such an approach learns (meta-)heuristics that can perform well on the training instances, expecting it to generalize well on the unseen test instances. A recent method, named GPGLS, uses Genetic Programming (GP) to learn the utility function in Guided Local Search (GLS) and solved large scale VRP effectively. However, the selection of appropriate training instances during the learning process remains an open question, with most existing studies including GPGLS relying on random instance selection. To address this, we propose a novel method, CL-GPGLS, which integrates Curriculum Learning (CL) into GPGLS. Our approach leverages a predefined curriculum to introduce training instances progressively, starting with simpler tasks and gradually increasing complexity, enabling the model to better adapt and optimize for large-scale VRP (LSVRP). Extensive experiments verify the effectiveness of CL-GPGLS, demonstrating significant performance improvements over three baseline methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。