用目标值引导偏好优化，提升组合优化的效率与精度
BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
- 基于最优解锚定构建偏好对，更好平衡探索与利用
- 通过目标差异自适应调整梯度，无需奖励模型或参考策略
- 在三种典型调度问题上显著缩小最优差距，适合现有模型无缝接入
神经组合优化（NCO）为解决NP难问题提供了新思路。然而，现有基于强化学习的方法因奖励稀疏和解空间利用率低，存在样本效率差的问题。本文提出最佳锚定与目标引导的偏好优化（BOPO），利用解的目标值构建偏好关系。该方法包含：(1) 最佳锚定偏好对构造机制，促进解的探索与利用；(2) 目标引导的成对损失函数，根据目标值差异自适应缩放梯度，不再依赖奖励模型或参考策略。在作业车间调度（JSP）、旅行商问题（TSP）和柔性作业车间调度（FJSP）上的实验表明，BOPO优于当前最先进的神经方法，在高效推理下显著缩小最优性差距。该方法与架构无关，可无缝集成至现有NCO模型中，并确立了偏好优化在组合优化中的系统性框架。
原文摘要 · Abstract (English)
Neural Combinatorial Optimization (NCO) has emerged as a promising approach for NP-hard problems. However, prevailing RL-based methods suffer from low sample efficiency due to sparse rewards and underused solutions. We propose Best-anchored and Objective-guided Preference Optimization (BOPO), a training paradigm that leverages solution preferences via objective values. It introduces: (1) a best-anchored preference pair construction for better explore and exploit solutions, and (2) an objective-guided pairwise loss function that adaptively scales gradients via objective differences, removing reliance on reward models or reference policies. Experiments on Job-shop Scheduling Problem (JSP), Traveling Salesman Problem (TSP), and Flexible Job-shop Scheduling Problem (FJSP) show BOPO outperforms state-of-the-art neural methods, reducing optimality gaps impressively with efficient inference. BOPO is architecture-agnostic, enabling seamless integration with existing NCO models, and establishes preference optimization as a principled framework for combinatorial optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。