arXiv:2608.12443stat.MLcs.AI2026-08

通过结构感知加权优化,提升神经组合优化的训练效果。

SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization

论文配图:SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization
图 1 · 摘自论文原文
  • 用结构相似性加权所有采样解,避免梯度极化与基线冗余。
  • 在TSP、EFL、JSP任务上均优于现有最佳方法。
  • 已落地京东生产系统,适合工业级组合优化场景。

神经组合优化依赖并行采样解进行训练,但现有方法未能充分利用共采样解组中的丰富信息。偏好优化方法仅基于最优解,丢弃其他解的细粒度质量与结构信号,导致梯度信号极化;均值基线则对所有解等权重,使结构相近的解重复传递冗余信息,造成梯度方差高,称为基线冗余。本文提出SSPO(结构感知相似性加权偏好优化),通过差异性加权的留一法基线,联合评估全部B个采样解:结构差异大的解获得更高权重,单一机制同时解决两类问题。该基线采用零参数、问题自适应的解嵌入,由编码器现有节点表示构建。在TSP、EFL和JSP基准测试中,性能持续优于先前最佳锚点与均匀权重基线。直接对比均匀RLOO在TSP和EFL上的结果证实,结构感知加权是提升主因。经SSPO训练的EFL策略已在京东生产设施选址系统中部署,验证了其大规模实际可行性。

原文摘要 · Abstract (English)

Neural combinatorial optimization (NCO) relies on parallel solution sampling for training, yet existing methods fail to fully exploit the rich information latent in a co-sampled solution group. Preference-optimization methods anchor on the single best solution and discard fine-grained quality and structural signal from all other peers-a failure we term gradient signal polarization. Mean-based baselines instead weight peers uniformly, so structurally near-identical peers flood the baseline with redundant information and keep gradient variance high-a failure we term baseline redundancy. We propose SSPO (Structure-Aware Similarity-Weighted Preference Optimization), which scores all $B$ sampled solutions jointly through a dissimilarity-weighted leave-one-out baseline: structurally distinct peers receive higher weight, resolving both failures in a single mechanism. The baseline uses zero-parameter, problem-adaptive solution embeddings built from the encoder's existing node representations. Experiments on TSP, EFL, and JSP benchmarks show consistent gains over prior best-anchor and uniform-weight baselines. A direct comparison against uniform RLOO on TSP and EFL confirms that structure-aware weighting is the primary driver of improvement. The SSPO-trained EFL policy has been deployed in a production facility-location system at JD$\mathord{.}$com, confirming practical viability at scale.

组合优化偏好学习结构感知工业应用

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