用AI自动发现组合优化中的偏好目标,提升求解效率。
AutoPref: Automatic Discovery of Task-Specific Preference Objectives for Neural Combinatorial Optimization

- 将偏好目标拆分为信号提取与权重分配两部分,构建可搜索的程序化空间。
- 在TSP、CVRP等4类问题上均优于人工设计基线,且规模扩展性好。
- 适合研究神经组合优化与自动化算法设计的学者参考。
组合优化问题(COPs)支撑诸多现实决策,但其指数级搜索空间导致高质量解代价高昂。神经组合优化(NCO)通过强化学习快速学习构造策略,而基于偏好的NCO则通过相对解质量提升样本效率。现有偏好目标将信号提取方式与配对权重设定合并为固定、通用的形式,缺乏灵活性。本文提出AutoPref,首个由大模型引导的自动化偏好目标发现框架。它将目标分解为成对损失程序(定义学习信号)与集合感知权重程序(决定每对贡献),二者组合形成统一的程序化目标空间,涵盖现有方法作为特例。为使搜索可行,引入分阶段条件搜索策略,利用行为门控过滤无效程序,仅在短周期训练评估中保留可行方案。在旅行商问题(TSP)、车辆路径问题(CVRP)、装箱问题(FFSP)和作业车间调度问题(JSSP)上,AutoPref在不同问题规模下持续超越强基准,验证了自动化目标发现的有效性与可扩展性。
原文摘要 · Abstract (English)
Combinatorial optimization problems (COPs) underpin many real-world decisions, but their exponentially large search spaces make high-quality solutions costly to obtain. Neural combinatorial optimization (NCO) learns fast construction policies, typically with reinforcement learning (RL), while preference-based NCO improves sample efficiency by learning from relative solution quality. However, existing preference objectives combine two distinct design choices in manually specified, one-size-fits-all formulations: what learning signal to extract from each solution pair and how to weight each pair relative to the sampled set. We present AutoPref, the first LLM-guided framework for automated preference-objective discovery in NCO. AutoPref factorizes the objective into a pairwise loss program, which defines the learning signal, and a set-aware weighting program, which determines each pair's relative contribution. Their composition forms a unified programmatic objective space containing existing preference objectives as special cases. To make its search tractable, we introduce a staged conditional search strategy with behavioral gates that filter inadmissible programs before short-horizon training and evaluation. Across TSP, CVRP, FFSP, and JSSP, AutoPref consistently outperforms strong hand-designed baselines across problem scales, demonstrating the benefits and scalability of automated objective discovery for NCO.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。