改进概率比特模拟退火，解决大规模优化中能量停滞问题。
Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization Problems
- 通过部分禁用比特，抑制概率比特的异常振荡。
- 在800至5000节点的16个最大割问题上，平均性能提升至98.4%。
- 适合研究硬件加速优化算法或量子启发计算的读者。
本文深入分析基于概率比特（pSA）的模拟退火算法在求解大规模组合优化问题时的局限性。研究发现，p比特间的意外振荡导致伊辛模型能量无法有效降低，阻碍了pSA在复杂任务中的成功应用。通过仿真揭示，该现象主要源于pSA操作中固有的反馈机制。为此，提出两种新算法：时间平均pSA（TApSA）和停滞pSA（SpSA），均基于部分禁用p比特的设计思想。在典型组合优化问题——最大割（Max-Cut）的16个基准测试中（节点数800至5000），新方法将归一化割值从传统pSA的0.8%提升至平均98.4%，显著改善收敛性能。
原文摘要 · Abstract (English)
This article critically investigates the limitations of the simulated annealing algorithm using probabilistic bits (pSA) in solving large-scale combinatorial optimization problems. The study begins with an in-depth analysis of the pSA process, focusing on the issues resulting from unexpected oscillations among p-bits. These oscillations hinder the energy reduction of the Ising model and thus obstruct the successful execution of pSA in complex tasks. Through detailed simulations, we unravel the root cause of this energy stagnation, identifying the feedback mechanism inherent to the pSA operation as the primary contributor to these disruptive oscillations. To address this challenge, we propose two novel algorithms, time average pSA (TApSA) and stalled pSA (SpSA). These algorithms are designed based on partial deactivation of p-bits and are thoroughly tested using Python simulations on maximum cut benchmarks that are typical combinatorial optimization problems. On the 16 benchmarks from 800 to 5,000 nodes, the proposed methods improve the normalized cut value from 0.8% to 98.4% on average in comparison with the conventional pSA.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。