arXiv:2502.05221math.OCcs.AI2025-02

将黑化扩散引入DIFUSCO框架,探索连续时间建模在旅行商问题中的优化潜力。

Blackout DIFUSCO

  • 采用连续时间扩散框架替代离散方法,实现更平滑的状态演化。
  • 通过线性观测时间调度,提升扩散过程的自然过渡性。
  • 在困难区域细化时间切片,增强重构阶段的精度与稳定性。

本研究探索将黑化扩散(Blackout Diffusion)集成到DIFUSCO框架中,用于组合优化,特别针对旅行商问题(TSP)。受离散时间扩散模型(D3PM)保持结构完整性成功的启发,我们将该范式拓展至连续时间框架,利用黑化扩散的独特性质。连续时间建模带来更平滑的转换和更精细的控制,假设可提升解的质量。为此提出三项关键改进:首先,从基于离散时间的模型转向连续时间框架,提供更精细灵活的表述;其次,优化观测时间调度,确保扩散过程全程平滑线性,实现状态演化的自然推进;最后,在第二项改进基础上,通过在模型难处理区域引入更细粒度的时间切片,提升反向生成阶段的准确性和稳定性。尽管实验结果未超越基线性能,但验证了这些方法在简化与复杂性之间取得良好平衡的有效性,为基于扩散的组合优化提供了新视角。本文首次将黑化扩散应用于组合优化,为该领域后续发展奠定基础。代码已开源:https://github.com/Giventicket/BlackoutDIFUSCO。

原文摘要 · Abstract (English)

This study explores the integration of Blackout Diffusion into the DIFUSCO framework for combinatorial optimization, specifically targeting the Traveling Salesman Problem (TSP). Inspired by the success of discrete-time diffusion models (D3PM) in maintaining structural integrity, we extend the paradigm to a continuous-time framework, leveraging the unique properties of Blackout Diffusion. Continuous-time modeling introduces smoother transitions and refined control, hypothesizing enhanced solution quality over traditional discrete methods. We propose three key improvements to enhance the diffusion process. First, we transition from a discrete-time-based model to a continuous-time framework, providing a more refined and flexible formulation. Second, we refine the observation time scheduling to ensure a smooth and linear transformation throughout the diffusion process, allowing for a more natural progression of states. Finally, building upon the second improvement, we further enhance the reverse process by introducing finer time slices in regions that are particularly challenging for the model, thereby improving accuracy and stability in the reconstruction phase. Although the experimental results did not exceed the baseline performance, they demonstrate the effectiveness of these methods in balancing simplicity and complexity, offering new insights into diffusion-based combinatorial optimization. This work represents the first application of Blackout Diffusion to combinatorial optimization, providing a foundation for further advancements in this domain. * The code is available for review at https://github.com/Giventicket/BlackoutDIFUSCO.

组合优化扩散模型连续时间旅行商问题

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