.png){kind=icon}
返回
A tree search algorithm towards solving Ising formulated combinatorial optimization problems
.png){kind=icon}
OA
AI
DOI：10.1038/s41598-022-19102-x.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Simulated annealing (SA) attracts more attention among classical heuristic algorithms because many combinatorial optimization problems can be easily recast as the ground state search problem of the Ising Hamiltonian. However, for practical implementation, the annealing process cannot be arbitrarily slow and hence, it may deviate from the expected stationary Boltzmann distribution and become trapped in a local energy minimum. To overcome this problem, this paper proposes a heuristic search algorithm by expanding search space from a Markov chain to a recursive depth limited tree based on SA, where the parent and child nodes represent the current and future spin states. At each iteration, the algorithm selects the best near-optimal solution within the feasible search space by exploring along the tree in the sense of look ahead. Furthermore, motivated by the coherent Ising machine (CIM), the discrete representation of spin states is relaxed to a continuous representation with a regularization term, which enables the use of the reduced dynamics of the oscillators to explore the surrounding neighborhood of the selected tree nodes. We tested our algorithm on a representative NP-hard problem (MAX-CUT) to illustrate the effectiveness of the proposed algorithm compared to semi-definite programming (SDP), SA, and simulated CIM. Our results show that with the primal heuristics SA and CIM, our high-level tree search strategy is able to provide solutions within fewer epochs for Ising formulated combinatorial optimization problems.
Keyword:
OSCILLATORS
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.9
论文数:
28.3W
被引数:
83.5W
机构
引用论文
Neurodevelopmental outcomes after congenital heart surgery and strategies for improvement先天性心脏手术后的神经发育结果和改善策略
PREAI
分享收藏Efficient sampling of ground and low-energy Ising spin configurations with a coherent Ising machine
OAAI
OAAI分享收藏New hybrid concentrated photovoltaic/membrane distillation unit for simultaneous freshwater and electricity production.png)
Desalination
DesalinationIF0
PREAI
分享收藏Network of time-multiplexed optical parametric oscillators as a coherent Ising machineNATURE PHOTONICS
NATURE PHOTONICSIF32.9
PREAI
分享收藏Effect of stress on the behavior and 5-HT system in Sprague-Dawley and Wistar Kyoto rat strains
PREAI
分享收藏A poor man's coherent Ising machine based on opto-electronic feedback systems for solving optimization problemsNATURE COMMUNICATIONSOAAI
NATURE COMMUNICATIONSIF15.7
OAAI分享收藏
查看更多内容