蒙特卡洛介紹

1、王健華 交通運輸工程 蒙特卡洛 Monte Carlo蒙特卡洛的基本思想及產(chǎn)生蒙特卡洛的方法基礎(chǔ)用蒙特卡洛方法解用蒙特卡洛方法解決食堂排隊問題目 錄蒙特卡洛方法的優(yōu)缺點及發(fā)展蒙特卡洛的基本思想及產(chǎn)生 MC方法亦稱為隨機模擬方法，有時方法亦稱為隨機模擬方法，有時也稱為隨機抽樣實驗方法。他的基本思也稱為隨機抽樣實驗方法。他的基本思想是，為了求解數(shù)學(xué)、物理、工程技術(shù)想是，為了求解數(shù)學(xué)、物理、工程技術(shù)以及生產(chǎn)管理方面的問題，首先建立一以及生產(chǎn)管理方面的問題，首先建立一個概率模型或隨機過程，使它的參數(shù)等個概率模型或隨機過程，使它的參數(shù)等于隨機問題的解；然后通過對模型或者于隨機問題的解；然后通過對模型或者

2、過程的觀察或抽樣實驗來計算所求參數(shù)過程的觀察或抽樣實驗來計算所求參數(shù)的統(tǒng)計特征，最后給出所求解的近似值。的統(tǒng)計特征，最后給出所求解的近似值。蒙特卡洛的基本思想及產(chǎn)生 假設(shè)所要求的假設(shè)所要求的x是隨機變量是隨機變量 的數(shù)學(xué)期望的數(shù)學(xué)期望 ，那么近似確定那么近似確定x的方法是對的方法是對 進行進行N次重復(fù)抽樣，產(chǎn)生次重復(fù)抽樣，產(chǎn)生相互獨立的相互獨立的 值的序列值的序列 ，并計算其算術(shù)，并計算其算術(shù)平均值：平均值：根據(jù)克爾莫格羅夫加強大數(shù)定理有：根據(jù)克爾莫格羅夫加強大數(shù)定理有：因此，當因此，當N充分大時，充分大時，成立的概率為成立的概率為1，亦即可以用，亦即可以用 作為所求量作為所求量x的估計的估計

3、值。值。蒙特卡洛的基本思想及產(chǎn)生 MC MC理論依據(jù)理論依據(jù): : 均勻分布的算術(shù)平均收斂于真值均勻分布的算術(shù)平均收斂于真值 ( (大數(shù)法則大數(shù)法則) ) 置信水平下的統(tǒng)計誤差置信水平下的統(tǒng)計誤差 ( (中心極限中心極限) ) MC MC方法可以解決的問題：方法可以解決的問題： 確定性的數(shù)學(xué)問題，如計算多重積分，求逆矩，確定性的數(shù)學(xué)問題，如計算多重積分，求逆矩，解線性方程組等。解線性方程組等。隨機性問題，如中子在介質(zhì)中的擴散等。隨機性問題，如中子在介質(zhì)中的擴散等。蒙特卡洛的基本思想及產(chǎn)生 MC方法的定名和系統(tǒng)的發(fā)展約始于二十世紀方法的定名和系統(tǒng)的發(fā)展約始于二十世紀四十年代，它的名字來源于摩納哥

4、蒙特卡洛城市四十年代，它的名字來源于摩納哥蒙特卡洛城市的名字，但如果從方法特征的角度來說，可以一的名字，但如果從方法特征的角度來說，可以一直追溯到十九世紀后半葉的直追溯到十九世紀后半葉的蒲豐隨機投針實驗蒲豐隨機投針實驗，即所謂的即所謂的蒲豐問題蒲豐問題。蒙特卡洛的方法基礎(chǔ)進行計算機模進行計算機模擬需要大樣本擬需要大樣本的均勻分布隨的均勻分布隨機數(shù)數(shù)列，如機數(shù)數(shù)列，如何獲得？何獲得？偽隨機數(shù)的產(chǎn)生偽隨機數(shù)的產(chǎn)生真隨機數(shù)：真隨機數(shù)：由隨機物理過程來產(chǎn)生，例如：放射性衰變、電子設(shè)備的熱噪 音、宇宙射線的觸發(fā)時間等等 偽隨機數(shù)偽隨機數(shù)：由計算機按遞推公式大量產(chǎn)生蒙特卡洛的方法基礎(chǔ) 設(shè) 為2s個數(shù)碼，自

5、乘后，去頭截尾，然后相應(yīng)的除以 或 ，作為0,1上的偽隨機數(shù)，如此重復(fù)這一過程，直至或者為0，或者與已出現(xiàn)的數(shù)字重復(fù)（周期性）時為止。公式表示如下：偽隨機數(shù)的產(chǎn)生偽隨機數(shù)的產(chǎn)生x 表示不超過x的最大整數(shù)X=a (mod M) 表示x等于a被M除的余數(shù)蒙特卡洛的方法基礎(chǔ)例：十進制2s=4,并取 =6406， 則 =6406， =41036836， 而 即為410368/ 的余數(shù)， 所以， 如此重復(fù)，則有 偽隨機數(shù)的產(chǎn)生偽隨機數(shù)的產(chǎn)生 蒙特卡洛的方法基礎(chǔ)蒙特卡洛的方法基礎(chǔ)偽隨機數(shù)的產(chǎn)生偽隨機數(shù)的產(chǎn)生自 開始出現(xiàn)周期，故序列長度（從初值到發(fā)生周期或退化前，序列中的偽隨機數(shù)的個數(shù)）為20。結(jié)論結(jié)論蒙特

6、卡洛的方法基礎(chǔ)偽隨機數(shù)的檢驗偽隨機數(shù)的檢驗均勻性檢驗均勻性檢驗: :0,1分成k個相等子區(qū)間，進行N次抽樣，投入各子區(qū)間如均勻,則各區(qū)間落入數(shù)Ni應(yīng)為 12kiiiNNNNkNi可視為(，)的一組無關(guān)樣本測量，服從則(k)蒙特卡洛的方法基礎(chǔ)獨立性檢驗獨立性檢驗: : 即xi與xi+1的前后無關(guān)性0,1上進行2N次抽樣，分成兩個序列132121:,.,.,iNXx xxx2422:,.,.,iNYx xxx在XY平面內(nèi)劃分kk方格，如獨立, 則各格內(nèi)落入數(shù)應(yīng)為,12222kiji jijNnNnk則服從c2分布滿足以上統(tǒng)計性檢驗的遞推抽樣序列，可視為滿足以上統(tǒng)計性檢驗的遞推抽樣序列，可視為0,1

7、0,1均勻分布偽隨機數(shù)均勻分布偽隨機數(shù)蒙特卡洛的方法基礎(chǔ)隨機變量的抽樣隨機變量的抽樣直接抽樣法直接抽樣法：求分布函數(shù) ) )01xF xf x dx則令 )xF )x1 F例例 對指數(shù)分布的直接抽樣 )., 00, 0,其它xexfx蒙特卡洛的方法基礎(chǔ)例例 對指數(shù)分布的直接抽樣 )., 00, 0,其它xexfx積分得到分布函數(shù) ) )xxtxedtedttfxF10令 )xeF1則指數(shù)分布的隨機變量抽樣為蒙特卡洛方法與Matlab結(jié)合蒙特卡洛方法與Visual Basic結(jié)合蒙特卡洛方法與Excel結(jié)合蒙特卡洛方法解蒲豐投針試驗蒲豐投針試驗 1777年年,法國科學(xué)家蒲豐法國科學(xué)家蒲豐(Buf

8、fon)提出了投針提出了投針試驗問題試驗問題.平面上畫有等距離為平面上畫有等距離為a(a0)的一些平行直的一些平行直線線,現(xiàn)向此平面任意投擲一根長為現(xiàn)向此平面任意投擲一根長為( ba )的針的針,試求試求針與某一平行直線相交的概率針與某一平行直線相交的概率.解解,直直線線的的距距離離到到最最近近的的一一條條平平行行針針的的中中點點表表示示針針投投到到平平面面上上時時以以Mxax M.夾夾角角表表示示針針與與該該平平行行直直線線的的 .),(完完全全確確定定置置可可由由那那么么針針落落在在平平面面上上的的位位 xax M矩形區(qū)域矩形區(qū)域果與果與投針試驗的所有可能結(jié)投針試驗的所有可能結(jié)0 ,20)

9、,( axxS.中中的的所所有有點點一一一一對對應(yīng)應(yīng)由投擲的任意性可知由投擲的任意性可知這是一個幾何概型問題這是一個幾何概型問題. .中中的的點點滿滿足足發(fā)發(fā)生生的的充充分分必必要要條條件件為為針針與與某某一一平平行行直直線線相相交交所所關(guān)關(guān)心心的的事事件件SA .0,sin20 bxo的面積的面積的面積的面積SGSGAP )()()(2dsin20 ab .22abab o蒲豐投針試驗的應(yīng)用及意義蒲豐投針試驗的應(yīng)用及意義2)(abAP 那么那么的近似值代入上式的近似值代入上式作為作為即可即可則頻率值則頻率值的次數(shù)的次數(shù)測出針與平行直線相交測出針與平行直線相交很大時很大時當投針試驗次數(shù)當投針試

10、驗次數(shù)根據(jù)頻率的穩(wěn)定性根據(jù)頻率的穩(wěn)定性,)(,APnmmn2abnm .2ambn . 的的近近似似值值利利用用上上式式可可計計算算圓圓周周率率蒙特卡洛方法解a=1; % 設(shè)置兩條平行線之間的距離b=0.6; % 投針的長度counter=0; % 針與平行線相交的次數(shù)n=10000000; % 投擲的次數(shù)x=unifrnd(0,a/2,1,n); %產(chǎn)生n個（0，a/2）之間均勻分布的隨機數(shù)，這里a/2是投針的中點到最近的平行線的距離phi=unifrnd(0,pi,1,n); % 產(chǎn)生n個（0，pi）之間均勻分布的隨機數(shù)，這里pi是投針到最近的平行線的角度for i=1:nif x(i)b

11、*sin(phi(i)/2 % 只要x小于b*sin（phi（i）/2,則相交counter=counter+1;endendfrequency=counter/n; % 計算相交的頻率，即相交次數(shù)與總次數(shù)比Pi=2*b/(a*frequency) % 從相交的頻率求pi使用使用蒙特卡洛法與蒙特卡洛法與Matlab結(jié)合結(jié)合求求的近似值的近似值蒙特卡洛方法解蒙特卡洛方法解 利用求單位正方形與內(nèi)接圓面積的比例關(guān)系來求得的近似值 。單位圓的1/4面積是一個扇形，它是邊長為1單位正方形的一部分。 如果能求出扇形面積s1在正方形面積s中占的比例k=s1/s，它的值也等于/4，從而就計算得到的值。 怎樣求

12、出扇形面積在正方形面積中占的比例k呢？蒙特卡洛法是在正方形中隨機投入很多點，使所投的點落在正方形中每一個位置的機會相等。有些點將落在扇形內(nèi)，而另一些點將會落在扇形外，落在扇形內(nèi)的點數(shù)m與所投點的總數(shù)n之間比m/n即為k的近似值。使用使用蒙特卡洛法與蒙特卡洛法與VB結(jié)合結(jié)合求求的近似值的近似值蒙特卡洛方法解Private Sub Command1_Click() Dim Pi As Double, x As Double, y As Double Dim m As Long, n As Long Randomize Timer 隨機數(shù)初始化 n = Val(Text1.Text) 讀入投放次數(shù)n

13、 If n = 0 Then MsgBox 請輸入投放次數(shù)n Exit Sub End If m = 0 For I = 1 To n x = Rnd() y = Rnd() If x 2 + y 2 = 1 Then m = m + 1 判斷是否在扇形內(nèi) Next I Pi = 4 * m / n 計算出的近似值 Text2.Text = Str(Pi)End Sub蒙特卡洛方法解蒙特卡洛方法解使用使用蒙特卡洛法與蒙特卡洛法與Excel結(jié)合結(jié)合求求的近似值的近似值原理：面積為原理：面積為1的正方形內(nèi)一內(nèi)切圓。隨機扔一點在圓的正方形內(nèi)一內(nèi)切圓。隨機扔一點在圓內(nèi)的概率為內(nèi)的概率為/4。那么用。那

14、么用Monte Carlo求出概率使之等于求出概率使之等于/4，則可以計算出，則可以計算出。方法：使用方法：使用excel的的rand（）函數(shù)取隨機數(shù)，以及二維坐標圓的公式（）函數(shù)取隨機數(shù)，以及二維坐標圓的公式 x2+y2=A2。第一步：第一步：A1代表扔一點后距正方形右邊距離，代表扔一點后距正方形右邊距離，B1代表扔一點后距正方形底代表扔一點后距正方形底邊距離，在邊距離，在A1輸入輸入 =rand（），在（），在B1輸入輸入=rand（），在（），在C1輸入輸入=IF(A1-0.5)2+(B1-0.5)20.52,4,0)第二步：用第二步：用excel拖動填充功能，向下拖單元格，想做多少次拖

15、動填充功能，向下拖單元格，想做多少次montecarlo模擬，就拖多少行，越多越準確。假設(shè)拖模擬，就拖多少行，越多越準確。假設(shè)拖100行。行。第三部：在第三部：在C101輸入輸入=average（C1：C100),所得結(jié)果即為所得結(jié)果即為。蒙特卡洛方法解用蒙特卡洛方法解決食堂排隊問題 用蒙特卡洛法在用蒙特卡洛法在Excel上對大學(xué)食堂的窗口服務(wù)狀上對大學(xué)食堂的窗口服務(wù)狀態(tài)和排隊等待問題進行模擬，態(tài)和排隊等待問題進行模擬，分別模擬了食堂在開設(shè)一個分別模擬了食堂在開設(shè)一個窗口和兩個窗口的情況下學(xué)窗口和兩個窗口的情況下學(xué)生的排隊問題，通過生的排隊問題，通過500次次模擬的統(tǒng)計分析得出，該方模擬的統(tǒng)計

16、分析得出，該方法具有簡便、易行、實用性法具有簡便、易行、實用性強的特點，為決策者提供了強的特點，為決策者提供了參考依據(jù)。參考依據(jù)。我要我要吃吃 飯飯用蒙特卡洛方法解決食堂排隊問題 學(xué)生食堂的排隊問題是一個學(xué)生們十分關(guān)心的問題，學(xué)生食堂的排隊問題是一個學(xué)生們十分關(guān)心的問題，學(xué)生希望增加窗口數(shù)，減少排隊等待時間。然而就食堂的學(xué)生希望增加窗口數(shù)，減少排隊等待時間。然而就食堂的角度來說，雖說增加窗口數(shù)量可以減少排隊等待時間，提角度來說，雖說增加窗口數(shù)量可以減少排隊等待時間，提高學(xué)生對該食堂的滿意度，從而讓更多的學(xué)生到該食堂就高學(xué)生對該食堂的滿意度，從而讓更多的學(xué)生到該食堂就餐，但是同時也會增加食堂的運

17、營成本，因此如何在這兩餐，但是同時也會增加食堂的運營成本，因此如何在這兩者之間進行權(quán)衡，找到最佳的窗口數(shù)量，對學(xué)生和食堂雙者之間進行權(quán)衡，找到最佳的窗口數(shù)量，對學(xué)生和食堂雙方來說都是很重要的。蒙特卡羅方法，或稱計算機隨機模方來說都是很重要的。蒙特卡羅方法，或稱計算機隨機模擬方法，是一種基于擬方法，是一種基于“隨機數(shù)隨機數(shù)”的計算方法，通過建立動的計算方法，通過建立動態(tài)模型，模擬食堂窗口的排隊問題，當只有一個窗口服務(wù)態(tài)模型，模擬食堂窗口的排隊問題，當只有一個窗口服務(wù)的情況下，前一個學(xué)生未被服務(wù)完畢的時候，后一個學(xué)生的情況下，前一個學(xué)生未被服務(wù)完畢的時候，后一個學(xué)生必須等待，直到前一個學(xué)生離開服務(wù)

18、臺，后一個學(xué)生才能必須等待，直到前一個學(xué)生離開服務(wù)臺，后一個學(xué)生才能被服務(wù)。而如果有兩個窗口服務(wù)的時候，則可以節(jié)省等待被服務(wù)。而如果有兩個窗口服務(wù)的時候，則可以節(jié)省等待時間。時間。用蒙特卡洛方法解決食堂排隊問題 在Excel下建立模擬模型，分別模擬單一窗口W1和兩個窗口W2的模擬量變化情況。通過對比兩個窗口的平均等待時間T等模擬量，做出決策是否增加窗口： 其中， 為第i個學(xué)生的等待時間。1、模型建立、模型建立用蒙特卡洛方法解決食堂排隊問題 令 為第i個學(xué)生的到達時刻； 為第i個學(xué)生的到達間隔，它通常是一個隨機數(shù)； 為第i個學(xué)生的服務(wù)開始時刻； 為第i個學(xué)生的服務(wù)完成時刻； 為第i個學(xué)生的服務(wù)時

19、間，它通常是一個隨機數(shù)； 為第i個學(xué)生的等待時間； 為第i個學(xué)生的逗留時間時間。(1)學(xué)生到達間隔，服務(wù)時間學(xué)生到達間隔及服務(wù)時 間為不可控變量，用蒙特卡洛法產(chǎn)生隨機數(shù)。(2)到達時刻 (3)開始服務(wù)時刻用蒙特卡洛方法解決食堂排隊問題(4)等待時間(5)完成時刻(6)總逗留時間用蒙特卡洛方法解決食堂排隊問題2、認識幾個、認識幾個Excel常用函數(shù)常用函數(shù)(1)產(chǎn)生按歷史數(shù)據(jù)統(tǒng)計規(guī)律分布的隨機數(shù)公式：=VLOOKUP(RAND()，表左上角地址：表右下角地址，變量所在列)公式中的表為隨機數(shù)區(qū)間表。(2)IF條件函數(shù):=IF(logical_test，value_if_true，value_if_

20、false)公式中第一項為邏輯判斷語句，隨后分別為正確時的返回值和錯誤時的返回值。用蒙特卡洛方法解決食堂排隊問題(3)COUNTIF函數(shù):=COUNTIF(rang,criteria)該公式用于統(tǒng)計在一定判斷標準下滿足條件的個數(shù)，其中公式中第一項為數(shù)據(jù)所在范圍；第二項為判斷標準；既滿足第二項條件的第一項數(shù)據(jù)的個數(shù)。(4)其他常用函數(shù)：MAX:返回樣本的最大值；MIN:返回樣本的最小值；AVERAGE:返回樣本的均值；STDEV:返回樣本的標準方差；SUM:返回樣本的代數(shù)和。用蒙特卡洛方法解決食堂排隊問題學(xué)生序號到達間隔達到時刻服務(wù)時刻等待時間服務(wù)時間完成時間總逗留時間10.000.30100.

21、000.122020.300.55300.120.422530.550.73500.420.803040.730.85700.800.963550.850.94900.961.004060.941.00110學(xué)生到達時間間隔的分布統(tǒng)計學(xué)生到達時間間隔的分布統(tǒng)計用蒙特卡洛方法解決食堂排隊問題單一窗口模型仿真結(jié)果單一窗口模型仿真結(jié)果用蒙特卡洛方法解決食堂排隊問題兩個窗口模擬模型兩個窗口模擬模型 兩個窗口和單個窗口相比，其余各變量不變，只有開始服務(wù)時刻有所變化。在兩個窗口的情況下，判斷何時能夠開始服務(wù)要看兩個窗口的狀態(tài)。當學(xué)生到達時刻比兩個窗口的開始空閑時刻都早時，學(xué)生得排隊等待，直到至少有一個窗口

22、達到空閑狀態(tài)才開始接受服務(wù)，所以這時的“開始服務(wù)時刻”應(yīng)等于先進人空閑狀態(tài)的那個窗口的“開始空閑時刻”(即最早開始空閑時刻)；當學(xué)生到達時刻比任意一個窗口的開始空閑時刻晚時，窗口可以立刻開始服務(wù)，所以這時的“開始服務(wù)時刻”應(yīng)等于學(xué)生到達時刻。綜上所述，在兩個窗口的模擬問題中，我們需要在Excel中新增兩列，分別為“窗口一的空閑時刻”和“窗口二的空閑時刻”，并且“開始服務(wù)時刻”的公式也要有所改變。用蒙特卡洛方法解決食堂排隊問題窗口一的空閑時刻窗口一的空閑時刻： 在第一個學(xué)生被服務(wù)時，窗口二保持空閑。所以窗口一的空閑時刻等于第一個學(xué)生的完成時刻。當學(xué)生陸續(xù)到達后，如果窗口一早于窗口二到達空閑狀態(tài)，則學(xué)生來到窗口一，這時窗口一的下一個開始空閑時刻等于該學(xué)生的服務(wù)完成時刻，窗口二的開始空閑時刻不變;如