伊辛模型的退火計算應用

Abstract

本文介紹了蒙地卡羅方法對二維伊辛模型模擬的基本概念，以及用C語言實現此模擬的過程和方法。然後再將護士排班問題套入伊辛模型中，並展示馬爾科夫蒙地卡羅方法對護士排班問題的處理結果。我會先介紹蒙地卡羅方法以及爲什麽要進行重要性抽樣，以及馬科夫過程的基本原理和馬爾科夫蒙地卡羅(MCMC)方法以及Metropolis–Hastings algorithm，然後如何用Single-spin-flip dynamics和Metropolis接受準則製造馬科夫鏈並用此方法解決2D ising model和护士排班问题。最後分析並討論得到的數據。

關鍵詞：蒙地卡羅方法，重要性抽樣，伊辛模型，馬爾科夫鏈，護士排班問題

In this paper I numerically study the two dimensional Ising model using the Monte Carlo method. Then build the Ising model to solve the Nurse Rostering Problem, and show the results of the Markov Monte Carlo method on the nurse scheduling problem. I first introduce the Monte Carlo method with the importance sampling and The basic principle of Markov process and Markov Monte Carlo (MCMC) method and Metropolis–Hastings algorithm, then I describe how to use the single-spin-flip dynamics and Metropolis–Hastings algorithm to simulate the Ising model in 2D square lattice and Nurse Rostering Problem. Finally the simulated results are analyzed and discussed.

Keywords：Monte Carlo method, Importance sampling, Ising model, Markov chain, Nurse Scheduling Problem