用正则化朗之万动力学提升组合优化采样效率
Regularized Langevin Dynamics for Combinatorial Optimization
- 引入正则化项控制采样与当前解的距离，增强探索能力
- 在3个经典问题上，运行时间比最先进方法快80%
- 适配传统启发式与神经网络模型，通用性强
本文提出一种简单有效的组合优化采样框架——正则化朗之万动力学（RLD）。该方法基于离散朗之万动力学（LD），但发现直接应用易陷入局部最优。为此，通过约束采样解与当前解的期望距离，有效避免局部极小。在此基础上，构建了两种求解器：一种基于模拟退火（SA），另一种基于神经网络（NN）。在三个经典组合优化问题上的实验表明，两者性能均达到或优于现有最先进方法。特别是，所提SA算法相比前人最佳方法，运行时间最多降低80%，且效果相当或更优。结果证明，RLD为改进传统启发式与神经网络模型提供了有力框架。代码已开源：https://github.com/Shengyu-Feng/RLD4CO。
原文摘要 · Abstract (English)
This work proposes a simple yet effective sampling framework for combinatorial optimization (CO). Our method builds on discrete Langevin dynamics (LD), an efficient gradient-guided generative paradigm. However, we observe that directly applying LD often leads to limited exploration. To overcome this limitation, we propose the Regularized Langevin Dynamics (RLD), which enforces an expected distance between the sampled and current solutions, effectively avoiding local minima. We develop two CO solvers on top of RLD, one based on simulated annealing (SA), and the other one based on neural network (NN). Empirical results on three classic CO problems demonstrate that both of our methods can achieve comparable or better performance against the previous state-of-the-art (SOTA) SA- and NN-based solvers. In particular, our SA algorithm reduces the runtime of the previous SOTA SA method by up to 80\%, while achieving equal or superior performance. In summary, RLD offers a promising framework for enhancing both traditional heuristics and NN models to solve CO problems. Our code is available at https://github.com/Shengyu-Feng/RLD4CO.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。