arXiv:2601.20868cs.LGcs.AI2026-01被引 8

用动态感知优化生成高效专用求解器,降低调参成本

Rethinking LLM-Driven Heuristic Design: Generating Efficient and Specialized Solvers via Dynamics-Aware Optimization

  • 基于收敛过程设计新评估指标,兼顾性能与效率
  • 运行时间提升4倍以上,跨尺度问题表现更均衡
  • 支持不同数据分布下快速启动,适配成本降90%

大型语言模型(LLM)通过自动化启发式生成推动组合优化发展。现有方法存在两大缺陷:仅以最终解距参考解的差距评价求解器,忽略收敛过程和运行效率;面对分布变化需重新适应,导致专用求解器生成成本高。为此,本文提出动态感知求解器启发式框架DASH,通过收敛感知指标联合优化求解器搜索机制与运行调度,识别高效高性能求解器。同时引入参数化库检索(PLR),在演化过程中存档群体专用求解器,实现针对不同分布的参数感知热启动。在四个组合优化问题上的实验表明,DASH将运行效率提升超4倍,在多种问题规模下兼顾差距与耗时的表现优于现有基线。此外,通过参数感知热启动,面对分布偏移时仍保持更低差距,且减少约90%的LLM适应成本。

原文摘要 · Abstract (English)

Large Language Models (LLMs) have advanced the field of Combinatorial Optimization through automated heuristic generation. Instead of relying on manual design, this LLM-Driven Heuristic Design (LHD) process leverages LLMs to iteratively generate and refine solvers to achieve high performance. However, existing LHD frameworks face two critical limitations: (1) Endpoint-only evaluation, which ranks solvers solely by final gap to a reference solution, ignoring the convergence process and runtime efficiency; (2) High adaptation costs, where distribution shifts necessitate re-adaptation to generate specialized solvers for heterogeneous instance groups. To address these issues, we propose Dynamics-Aware Solver Heuristics (DASH), a framework that co-optimizes solver search mechanisms and runtime schedules guided by a convergence-aware metric, thereby identifying efficient and high-performance solvers. Furthermore, to mitigate expensive re-adaptation, DASH incorporates Profiled Library Retrieval (PLR), which maintains group-specialized solvers for profile-aware warm starts. These solvers are archived concurrently during evolution, allowing DASH to reuse matched specialists across heterogeneous distributions without restarting adaptation. Experiments on four combinatorial optimization problems demonstrate that DASH improves runtime efficiency by over 4 times while outperforming prior LHD baselines in the overall balance between gap and runtime across diverse problem scales. Furthermore, by enabling profile-aware warm starts, DASH maintains lower gap under distribution shift while reducing LLM adaptation costs by about 90%.

组合优化LLM启发式动态优化求解器生成

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