Adaptive mean field approximation algorithm with critical temperature for combinatorial optimization problems
Jijun Wu, Tetsuya Harada, Takeshi Fukao · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1999
The adaptive mean field approximation method has been used by many researchers to solve combinatorial optimization problems since the 1980s. It is well known that critical phenomena occur in the annealing stage of the adaptive mean field approximation method. Research has been performed regarding determination of the critical temperature. Although the critical temperature affects the annealing schedule in the adaptive mean field approximation method, no search for a calculation method that takes it into account has been performed. In this article, the adaptive mean field approximation method with “adaptive annealing” is proposed, where the annealing schedule is changed while the critical temperature is estimated. By comparing this algorithm with other algorithms in maximum-clique problem and graph-partitioning problem experiments, it is shown that a good-quality solution can be found faster with the proposed method. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 82(4): 89–96, 1999