蒙特卡洛算法思想

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

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

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

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

蒙特卡洛算法實驗

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

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

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

實驗步驟：

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

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

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

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

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

（6）運行結(jié)果為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.計算函數(shù)定積分值

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

運行結(jié)果為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.計算函數(shù)極值，可避免陷入局部極值

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

運行結(jié)果發(fā)現(xiàn)極大值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)#匿名函數(shù)
 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

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

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

最新評論