增强了基于p-bit的模拟化与部分停用在大规模组合优化问题上的融合
Naoya Onizawa1, Takahiro Hanyu2
1Research Institute of Electrical Communication, Tohoku University, Sendai, 980-8577, Japan. naoya.onizawa.a7@tohoku.ac.jp.
Scientific reports
|January 16, 2024
概括
这项研究解决了模拟化与概率位 (pSA) 进行优化的局限性. 新的TApSA和SpSA算法通过管理p-bit振荡来提高性能,增强复杂问题的解决方案.
科学领域:
- 计算科学 计算科学
- 优化算法 优化算法
- 统计物理 统计物理
背景情况:
- 用概率位 (pSA) 模拟回火用于组合优化.
- 由于概率位 (p-bits) 之间的振荡,pSA面临着局限性.
- 这些振荡阻碍了Ising模型中的能量减少,阻碍了复杂的问题解决.
研究的目的:
- 在大规模的组合优化中批判性地研究pSA的局限性.
- 为了确定pSA能量停滞的根本原因.
- 为改善pSA性能提出新的算法.
主要方法:
- 对pSA过程和p-bit振荡进行了深入分析.
- 详细的模拟以了解能量停滞和反机制.
- 开发和测试两个新的算法:时间平均pSA (TApSA) 和停滞pSA (SpSA).
- 在最大切割基准上使用Python模拟实现.
主要成果:
- 确定了pSA中固有的反机制作为破坏性振荡的原因.
- TApSA和SpSA算法是基于p-bits的部分停用而设计的.
- 在16个基准 (800-5000个节点) 上,与传统的pSA相比,提出的方法平均提高了0.8%至98.4%的正常切割值.
结论:
- 拟议的TApSA和SpSA算法有效地减轻了由p-bit振荡引起的pSA限制.
- 这些新的方法为大规模的组合优化问题提供了显著的性能改进.
- 对p-bits的部分禁用是增强模拟回火算法的可行策略.
