针对大规模路径优化问题,提出局部特化方法,显著提升自动启发式设计效果。
SpecAHD: Localize to Specialize for Automated Heuristic Design in Large-Scale Routing Problems

- 通过上下层协同框架,按局部修复区域定制不同启发式策略
- 在4个路由问题上比最强基线降低57.7%的目标成本
- 适合需要高精度求解的大规模路径优化场景
基于大语言模型的自动启发式设计(AHD)通常在完整实例或固定求解组件中评估可执行程序。在大规模路由问题中,局部重构能缩小每个优化任务的规模,但同一初始解内的修复区域可能具有显著不同的结构,单一构造规则需在其中妥协。本文提出SpecAHD,一种用于实例内特化的耦合双层框架:上层搜索确定暴露的有界修复区域,下层搜索演化出一组互补的可执行启发式以应对生成的修复任务。上层程序决定下层所见的修复任务,而修复结果则决定上层程序的评估。下层目标偏好平均表现良好或解决当前组合包处理不佳的任务的启发式。对于固定上层程序和固定下层候选池诱导的修复任务,该目标为单调子模,允许使用贪心算法获得(1-1/e)近似保证。在四个路由问题及多个LLM骨干网络上,SpecAHD在保留目标成本上比最强竞品基线最多降低57.7%,并在多数公开实例上超越了每实例基线包络。
原文摘要 · Abstract (English)
LLM-based automated heuristic design (AHD) typically scores executable programs on complete instances or within fixed solver components. In large-scale routing problems, localized reconstruction reduces the size of each optimization task, but repair regions within the same incumbent can exhibit substantially different structures. One construction rule must therefore compromise across them. In this paper, we propose SpecAHD, a coupled bilevel framework for within-instance specialization. An upper-level search learns where to expose bounded repair regions, while a lower-level search evolves a complementary repertoire of executable heuristics for the induced repair tasks. The upper-level program determines the repair tasks seen by the lower level, while checked repair outcomes determine how upper-level programs are evaluated. The lower-level objective favors heuristics that perform well on average or solve tasks that the current repertoire handles poorly. For the repair tasks induced by a fixed upper-level program and a fixed lower-level candidate pool, this objective is monotone submodular, allowing greedy repertoire selection with a (1-1/e) approximation guarantee. Across four routing problems and multiple LLM backbones, SpecAHD reduces held-out objective cost by up to 57.7% against the strongest competing AHD baseline and outperforms the per-instance baseline envelope on most public instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。