Focused on major national strategic needs and pressing global challenges, NUDT makes relentless efforts to pursue original and pioneering innovations.

首页 Research Research Frontier

NUDT makes essential breakthrough in combinatorial optimization of complex system


Recently, a research group led by Professor Liu Zhong in College of Systems Engineering, NUDT, collaborated with research groups from Harvard University, University of California, Los Angeles and Washington University in St. Louis to put forward a deep reinforcement learning method to search for spin glass ground states. The research is published online in Nature Communications on February 9, entitled "Searching for spin glass ground states through deep reinforcement learning", with Professor Fan Changjun from College of Systems Engineering, NUDT being the first author. 

Spin glasses are widely applied in statistical physics. Finding the ground states of spin glasses is not only essential for understanding the nature of disordered magnets and many other physical systems, but also useful to solve a broad array of hard combinatorial optimization problems across multiple disciplines. 2021 Nobel Prize in Physics has been awarded to Professor Giorgio Parisi to honor his contributions to complex system research which includes his research on ground states of two-dimensional ising spin glasses. Finding ground states of Ising spin glasses in three or higher dimensions is a non-deterministic polynomial-time (NP) hard problem, which is closely related to many other hard combinatorial optimization problems. Despite decades-long efforts, an algorithm with both high accuracy and high efficiency is still lacking. This paper introduces DIRAC, a deep reinforcement learning framework, which considers the spin glass ground state search as a Markov decision process (MDP). The researchers have designed an encoder based on graph neural networks namely SGNN (Spin Glass Neural Network), to represent states and actions. Through a pure data-driven way and without any domain-specific guidance, DIRAC smartly mimics the human intelligence in solving the spin glass ground state problem.