A new search method for combinatorial optimization problem inspired by the spin glass system

摘要

A Hopfield network is a good tool for solving combinatorial optimization problems. Since its proposal, research activity around this area has been accelerated with the help of related ideas. But some of them are just techniques to get better solutions, so no meaningful phenomena might be observed in the field of the actual spin glass. In this paper, therefore, another search method inspired from an analogy between the Hopfield network and the spin glass is proposed. It is quite a simple idea to control a threshold of the Hopfield network corresponding to a magnetic field in the spin-glass. In order to confirm its effectiveness, an N queens problem is adopted. As a result, it is found experimentally that the proposed method shows better score, e.g. a ratio of correct answer and an averaged final energy, than the conventional one.