斯溫森-王算法

斯溫森-王算法(英語:Swendsen–Wang algorithm)由物理學家羅伯特·斯溫森英語Robert Swendsen王建生於1987年提出,是首個非局域的蒙特卡洛算法,用以解決臨界點附近效率變低的臨界慢化問題。

斯溫森-王算法最初用於易辛模型玻茨模型,後來被推廣到其他模型之中。該算法的關鍵是按照Fortuin與Kasteleyn的理論將玻茨模型變換為滲流理論的模型,相鄰自旋間按概率成鍵。之後再通過霍森-科佩爾曼算法標識聯鍵的集團(cluster),並將每個集團內的所有自旋賦以相同的隨機值。由於該算法可以一次改變整個集團的自旋,因而在臨界點附近能夠顯著提高效率,以解決臨界慢化問題。

2005年,加州大學洛杉磯分校教授朱松純與其博士生阿德里安·巴爾布(Adrian Barbu)推廣了斯溫森-王算法,將其看作是一個梅特羅波利斯-黑斯廷斯算法並計算了相應的接受概率,使其適用於任意後驗概率的採樣。

參考文獻

編輯
  • Swendsen, R. H., and Wang, J.-S. (1987), Nonuniversal critical dynamics in Monte Carlo simulations, Phys. Rev. Lett., 58(2):86–88.
  • Kasteleyn P. W. and Fortuin (1969) J. Phys. Soc. Jpn. Suppl. 26s:11; Fortuin C. M. and Kasteleyn P.W. (1972), Physica (Utrecht) 57:536.
  • Wang J.-S. and Swendsen, R. H. (1990),Cluster Monte Carlo algorithms, Physica A 167:565.
  • Barbu, A., Zhu, S. C. (2005), Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities, IEEE Trans Patt. Anal. Mach. Intell., 27(8):1239-1253.