蒙地卡羅方法

一类依赖于重复随机抽样的算法

蒙地卡羅方法(英語:Monte Carlo method),也稱統計模擬方法,是1940年代中期由於科學技術的發展和電腦的發明,而提出的一種以概率統計理論為指導的數值計算方法。是指使用亂數(或更常見的偽亂數)來解決很多計算問題的方法。

20世紀40年代,在科學家馮·諾伊曼斯塔尼斯拉夫·烏拉姆尼古拉斯·梅特羅波利斯洛斯阿拉莫斯國家實驗室為核武器計劃工作時,發明了蒙地卡羅方法。因為烏拉姆的叔叔經常在摩納哥蒙地卡羅賭場輸錢得名,而蒙地卡羅方法正是以概率為基礎的方法。

與它對應的是確定性演算法

蒙地卡羅方法在金融工程學宏觀經濟學生物醫學計算物理學(如粒子輸運計算、量子熱力學計算、空氣動力學計算)、機器學習等領域應用廣泛。[1]

基本概念

通常蒙地卡羅方法可以粗略地分成兩類:一類是所求解的問題本身具有內在的隨機性,藉助電腦的運算能力可以直接模擬這種隨機的過程。例如在核物理研究中,分析中子在反應堆中的傳輸過程。中子與原子核作用受到量子力學規律的制約,人們只能知道它們相互作用發生的概率,卻無法準確獲得中子與原子核作用時的位置以及裂變產生的新中子的行進速率和方向。科學家依據其概率進行隨機抽樣得到裂變位置、速度和方向,這樣模擬大量中子的行為後,經過統計就能獲得中子傳輸的範圍,作為反應堆設計的依據。

另一種類型是所求解問題可以轉化為某種隨機分佈的特徵數,比如隨機事件出現的概率,或者隨機變量期望值。通過隨機抽樣的方法,以隨機事件出現的頻率估計其概率,或者以抽樣數字特徵估算隨機變量數字特徵,並將其作為問題的解。這種方法多用於求解複雜的多維積分問題。

假設我們要計算一個不規則圖形的面積,那麼圖形的不規則程度和分析性計算(比如,積分)的複雜程度是成正比的。蒙地卡羅方法基於這樣的想法:假設你有一袋豆子,把豆子均勻地朝這個圖形上撒,然後數這個圖形之中有多少顆豆子,這個豆子的數目就是圖形的面積。當你的豆子越小,撒的越多的時候,結果就越精確。藉助電腦程式可以生成大量均勻分佈坐標點,然後統計出圖形內的點數,透過它們佔總點數的比例和坐標點生成範圍的面積就可以求出圖形面積。

工作過程

 
使用蒙地卡羅方法估算π值. 放置30000個隨機點後,π的估算值與真實值相差0.07%.

在解決實際問題的時候應用蒙地卡羅方法主要有兩部分工作:

  1. 用蒙地卡羅方法模擬某一過程時,需要產生各種概率分佈隨機變量
  2. 用統計方法把模型的數字特徵估計出來,從而得到實際問題的數值解。

分子模擬計算的步驟

使用蒙地卡羅方法進行分子模擬計算是按照以下步驟進行的:

  1. 使用亂數生成器產生一個隨機的分子構型
  2. 對此分子構型的其中粒子坐標做無規則的改變,產生一個新的分子構型。
  3. 計算新的分子構型的能量。
  4. 比較新的分子構型與改變前的分子構型的能量變化,判斷是否接受該構型。
    • 若新的分子構型能量低於原分子構型的能量,則接受新的構型,使用這個構型重複再做下一次迭代
    • 若新的分子構型能量高於原分子構型的能量,則計算玻爾茲曼因子,並產生一個亂數。
      • 若這個亂數大於所計算出的玻爾茲曼因子,則放棄這個構型,重新計算。
      • 若這個亂數小於所計算出的玻爾茲曼因子,則接受這個構型,使用這個構型重複再做下一次迭代。
  5. 如此進行迭代計算,直至最後搜尋出低於所給能量條件的分子構型結束。

在數學中的應用

通常蒙地卡羅方法透過構造符合一定規則的亂數來解決數學上的各種問題。對於那些由於計算過於複雜而難以得到解析解或者根本沒有解析解的問題,蒙地卡羅方法是一種有效的求出數值解的方法。一般蒙地卡羅方法在數學中最常見的應用就是蒙特卡羅積分。下面是蒙地卡羅方法的兩個簡單應用:

積分

非權重蒙特卡羅積分,也稱確定性抽樣,是對被積函數變數區間進行隨機均勻抽樣,然後對抽樣點的函數值求平均,從而可以得到函數積分的近似值。此種方法的正確性是基於概率論中心極限定理。當抽樣點數為m時,使用此種方法所得近似解的統計誤差只與m有關(與 正相關),不隨積分維數的改變而改變。因此當積分維度較高時,蒙地卡羅方法相對於其他數值解法更優。

圓周率

蒙地卡羅方法可用於近似計算圓周率:讓電腦每次隨機生成兩個0到1之間的數,看以這兩個實數為橫縱坐標的點是否在單位圓內。生成一系列隨機點,統計單位圓內的點數與總點數,(圓面積和正方形面積之比為PI:4,PI為圓周率),當隨機點取得越多時,其結果越接近於圓周率(然而準確度仍有爭議:即使取10的9次方個隨機點時,其結果也僅在前4位元與圓周率吻合[來源請求],以下Python程式碼可提供測試)。用蒙地卡羅方法近似計算圓周率的先天不足是:電腦產生的亂數是受到儲存格式的限制的,是離散的,並不能產生連續的任意實數;上述做法將平面分割成一個個網格,在空間也不是連續的,由此計算出來的面積當然與圓或多或少有差距。

import numpy as np

# 生成10的9次方個隨機點
num_points = 10**9
points = np.random.rand(num_points, 2)

# 計算點到原點的距離
distances = np.sqrt(points[:,0]**2 + points[:,1]**2)

# 計算落在單位圓內的點的數量
points_inside_circle = np.sum(distances <= 1)

# 蒙地卡羅方法計算圓周率
pi_estimate = 4 * points_inside_circle / num_points

print(pi_estimate)

在機器學習中的應用

蒙地卡羅方法也常用於機器學習,特別是強化學習的演算法中。一般情況下,針對得到的樣本數據集建立相對模糊的模型,透過蒙地卡羅方法對於模型中的參數進行選取,使之於原始數據的殘差儘可能的小。從而達到建立模型擬合樣本的目的。

參見

註釋

  1. ^ Kroese, D. P.; Brereton, T.; Taimre, T.; Botev, Z. I. Why the Monte Carlo method is so important today. WIREs Comput Stat. 2014, 6: 386–392. doi:10.1002/wics.1314. 

參考