论文标题
混合时间和模拟退火的随机细胞自动机
Mixing time and simulated annealing for the stochastic cellular automata
论文作者
论文摘要
在图$ g =（v，e）$上找到给定哈密顿的基本状态是一个重要但困难的问题。这种问题的标准方法是依靠单旋纤维马尔可夫链蒙特卡洛方法的算法的应用，例如基于Glauber或Metropolis Dynamics的模拟退火。在本文中，我们研究了一种特定的随机细胞自动机，其中所有自旋均可同时独立更新。我们证明（i）如果温度固定得足够高，则混合时间的大多数是$ \ log | v | $，并且（ii）如果温度在时间$ n $中下降为$ 1/\ log n $，则限制度量是均匀分布在地面状态下的。我们还提供了对本文在GPU上实施的本文研究的算法的一些模拟，并显示了与常规模拟退火相比的卓越性能。
Finding a ground state of a given Hamiltonian of an Ising model on a graph $G=(V,E)$ is an important but hard problem. The standard approach for this kind of problem is the application of algorithms that rely on single-spin-flip Markov chain Monte Carlo methods, such as the simulated annealing based on Glauber or Metropolis dynamics. In this paper, we investigate a particular kind of stochastic cellular automata, in which all spins are updated independently and simultaneously. We prove that (i) if the temperature is fixed sufficiently high, then the mixing time is at most of order $\log|V|$, and that (ii) if the temperature drops in time $n$ as $1/\log n$, then the limiting measure is uniformly distributed over the ground states. We also provide some simulations of the algorithms studied in this paper implemented on a GPU and show their superior performance compared to the conventional simulated annealing.
