蒙特卡洛算法思想

蒙特卡洛（Monte Carlo）法是一類隨機算法的統稱，提出者是大名鼎鼎的數學家馮?諾伊曼，他在20世紀40年代中期用馳名世界的賭城―摩納哥的蒙特卡洛來命名這種方法。

通俗的解釋一下蒙特卡洛算法的思想。假如籃子里有1000個蘋果，讓你每次閉著眼睛拿1個，挑出最大的。于是你閉著眼睛隨機拿了一個，然后再隨機拿一個與第一個比，留下大的，再隨機拿一個，與前次留下的比較，又可以留下大的……你每拿一次，留下的蘋果至少是當前最大的，循環往復這樣，拿的次數越多，挑出最大蘋果的可能性也就越大，但除非你把1000個蘋果都挑一遍，否則你無法肯定最終挑出來的就是最大的一個。也就是說，蒙特卡洛算法是樣本越多，越能找到最佳的解決辦法，但只是盡量找最好的，不保證一定是最好的。

與它形成對比的是拉斯維加斯算法思想。假如有一把鎖，有1000把鑰匙進行選擇，但只有1把是對的。于是你每次隨機拿1把鑰匙去試，打不開就再換1把。你試的次數越多，打開最優解的機會就越大，但在打開之前，那些錯的鑰匙都是沒有用的。所以拉斯維加斯算法就是盡量找最好的解決辦法，但是不保證能找到。假設試了999次后沒有任何一把鑰匙能打開鎖，真正的鑰匙是第1000把，但是樣本并沒有第1000次選擇，那么拉斯維加斯算法就不能找到打開鎖的鑰匙。

蒙特卡洛和拉斯維加斯本身是兩座著名賭城，因為賭博中體現了許多隨機算法，所以借此命名。它們只是概括了隨機算法的特性，算法本身可能復雜，也可能簡單，在這兩類隨機算法之間的選擇，往往受到問題的局限。如果問題要求在有限采樣內，必須給出一個解，但不要求是最優解，那就要用蒙特卡羅算法。反之，如果問題要求必須給出最優解，但對采樣沒有限制，那就要用拉斯維加斯算法。

蒙特卡洛算法實驗

這么看來蒙特卡洛方法的理論支撐其實是概率論或統計學中的大數定律?；驹砗唵蚊枋鍪窍却罅磕M，然后計算一個事件發生的次數，再通過這個發生次數除以總模擬次數，得到想要的結果。下面我們以三個經典的小實驗來學習下蒙特卡洛算法思想。

1.計算圓周率pi（π）值

實驗原理：在正方形內部有一個相切的圓，圓面積/正方形面積之比是(PixRxR)/(2Rx2R)= Pi/4。在這個正方形內隨機產生n個點，假設點落在圓內的概率為P，那么P=圓面積/正方形面積，則P= Pi/4。如何計算點落在圓內的概率P？可以計算點與中心點的距離，判斷是否落在圓的內部，若這些點均勻分布，用M表示落到圓內投點數 ， N表示總的投點數，則圓周率Pi=4P=4xM/N。

實驗步驟：

（1）將圓心設在原點（0，0），以R為半徑形成圓，則圓面積為PixRxR

（2）將該圓外接正方形, 坐標為（-R，-R）（R，-R）（R， R）（-R，R），則該正方形面積為R*R

（3）隨即取點（X，Y），使得-R <=X<=R并且-R <=Y<=R，即點在正方形內

（4）通過公式 XxX+YxY<= RxR判斷點是否在圓周內（直角三角形邊長公式）。

（5）設所有點（也就是實驗次數）的個數為N，落在圓內的點（滿足步驟4的點）的個數為M，則P=M/N，于是Pi=4xM/N。

（6）運行結果為3.143052

            
def cal_pai_mc(n=1000000):
 r = 1.0
 a, b = (0.0, 0.0)
 x_neg, x_pos = a - r, a + r
 y_neg, y_pos = b - r, b + r
 m = 0
 for i in range(0, n+1):
 x = random.uniform(x_neg, x_pos)
 y = random.uniform(y_neg, y_pos)
 if x**2 + y**2 <= 1.0:
 m += 1
 return (m / float(n)) * 4
          

2.計算函數定積分值

實驗原理：若要求函數f(x)從a到b的定積分，我們可以用一個比較容易算得面積的矩型包圍在函數的積分區間上（假設其面積為Area），定積分值其實就是求曲線下方的面積。隨機地向這個矩形框里面投點，統計落在函數f(x)下方的點數量占所有點數量的比例為P，那么就可以據此估算出函數f(x)從a到b的定積分為Area×P。此處我們將a和b設為0和1，函數f(x)=x2。

運行結果為0.333749

            
def cal_integral_mc(n = 1000000):
 x_min, x_max = 0.0, 1.0
 y_min, y_max = 0.0, 1.0
 m = 0
 for i in range(0, n+1):
 x = random.uniform(x_min, x_max)
 y = random.uniform(y_min, y_max)
 # x*x > y 表示該點位于曲線的下面。
 if x*x > y:
 m += 1
 #所求的積分值即為曲線下方的面積與正方形面積的比
 return m / float(n)
          

3.計算函數極值，可避免陷入局部極值

實驗原理：極值是“極大值” 和 “極小值”的統稱。如果一個函數在某點的一個鄰域內處處都有確定的值，函數在該點的值大于或等于在該點附近任何其他點的函數值，則稱函數在該點的值為函數的“極大值”。如果函數在該點的值小于或等于在該點附近任何其他點的函數值，則稱函數在該點 的值為函數的“極小值”。此處在區間[-2,2]上隨機生成一個數，求出其對應的y，找出其中最大值認為是函數在[-2,2]上的極大值。

運行結果發現極大值185.1204262706596, 極大值點為1.5144491499169481

            
def cal_extremum_mc(n = 1000000):
 y_max = 0.0
 x_min, x_max = -2.0, 2.0
 y = lambda x:200*np.sin(x)*np.exp(-0.05*x)#匿名函數
 for i in range(0, n+1):
 x0 = random.uniform(x_min, x_max)
 if y(x0) > y_max:
 y_max = y(x0)
 x_max = x0
 return y_max, x_max
          

以上三個例子也稱為基于蒙特卡洛的投點法，由此得出的值并不是一個精確值，而是一個近似值。當投點的數量越來越大時，這個近似值也越接近真實值。

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。