自适应调整能量景观，让伊辛机高效求解带约束优化问题。
Self-Adaptive Ising Machines for Constrained Optimization
- 用拉格朗日松弛动态调节能量势，无需预先设定惩罚参数。
- 300变量的二次背包问题，性能优于数字退火机，采样次数少7500倍。
- 适合需要快速求解复杂约束优化的科研与工程应用。
伊辛机（IM）是受物理启发的新型计算架构，用于求解难以处理的组合优化问题。通过将二元变量映射为耦合的伊辛自旋，IM能自然解决无约束优化问题，如图的最大割问题。然而，在实际应用中，约束优化问题仍具挑战性，因需施加大的二次能量惩罚以确保能量最低态对应于满足约束的最优解。为此，我们提出一种自适应伊辛机，通过迭代地利用约束的拉格朗日松弛来重塑能量景观，避免了惩罚参数的预调。在软件模拟的概率比特（p-bit）IM上，我们对多维背包问题（MKP）和二次背包问题（QKP）进行了基准测试，其中后者是带有线性约束的伊辛问题。在300变量的QKP实例中，该算法找到的解优于最先进的伊辛机（如富士通数字退火机），且采样次数减少7500倍。结果表明，在搜索过程中动态调整能量景观可显著加速伊辛机求解约束优化问题。
原文摘要 · Abstract (English)
Ising machines (IM) are physics-inspired alternatives to von Neumann architectures for solving hard optimization tasks. By mapping binary variables to coupled Ising spins, IMs can naturally solve unconstrained combinatorial optimization problems such as finding maximum cuts in graphs. However, despite their importance in practical applications, constrained problems remain challenging to solve for IMs that require large quadratic energy penalties to ensure the correspondence between energy ground states and constrained optimal solutions. To relax this requirement, we propose a self-adaptive IM that iteratively shapes its energy landscape using a Lagrange relaxation of constraints and avoids prior tuning of penalties. Using a probabilistic-bit (p-bit) IM emulated in software, we benchmark our algorithm with multidimensional knapsack problems (MKP) and quadratic knapsack problems (QKP), the latter being an Ising problem with linear constraints. For QKP with 300 variables, the proposed algorithm finds better solutions than state-of-the-art IMs such as Fujitsu's Digital Annealer and requires 7,500x fewer samples. Our results show that adapting the energy landscape during the search can speed up IMs for constrained optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。