【ICML2025】组合优化问题中的偏好优化

强化学习（Reinforcement Learning, RL）已成为神经组合优化中的一项强大工具，使模型能够在无需专家知识的前提下学习解决复杂问题的启发式策略。尽管已有显著进展，现有的RL方法仍面临诸多挑战，例如在庞大的组合动作空间中奖励信号逐渐减弱、探索效率低下等问题，导致整体性能受限。 为此，本文提出了一种新方法——偏好优化（Preference Optimization）。该方法通过统计比较建模，将定量的奖励信号转化为定性的偏好信号，重点关注样本解之间的相对优劣。在方法上，我们通过对奖励函数进行策略重参数化，并引入偏好模型，构建了一个熵正则化的强化学习目标函数，该目标能够使策略直接对齐于偏好信号，同时避免了难以处理的计算复杂度。

此外，我们将局部搜索技术集成进微调阶段（而非作为后处理步骤），用于生成高质量的偏好对，从而帮助策略跳出局部最优陷阱。

在多个基准任务上的实验结果表明，例如旅行商问题（TSP）、容量限制车辆路径问题（CVRP）以及柔性流水车间调度问题（FFSP），我们的算法在收敛效率和解质量方面显著优于现有强化学习方法。