小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

解析Monte-Carlo算法(基本原理,理論基礎,應用實踐) - T2噬菌體 - 博客園

 zele 2011-05-18

引言

      最近在和同學討論研究Six Sigma（六西格瑪）軟件開發(fā)方法及CMMI相關問題時，遇到了需要使用Monte-Carlo算法模擬分布未知的多元一次概率密度分布問題。于是花了 幾天時間，通過查詢相關文獻資料，深入研究了一下Monte-Carlo算法，并以實際應用為背景進行了一些實驗。
      在研究和實驗過程中，發(fā)現(xiàn)Monte-Carlo算法是一個非常有用的算法，在許多實際問題中，都有用武之地。目前，這個算法已經在金融學、經濟學、工程 學、物理學、計算科學及計算機科學等多個領域廣泛應用。而且這個算法本身并不復雜，只要掌握概率論及數(shù)理統(tǒng)計的基本知識，就可以學會并加以應用。由于這種 算法與傳統(tǒng)的確定性算法在解決問題的思路方面截然不同，作為計算機科學與技術相關人員以及程序員，掌握此算法，可以開闊思維，為解決問題增加一條新的思 路。
      基于以上原因，我有了寫這篇文章的打算，一是回顧總結這幾天的研究和實驗，加深印象，二是和朋友們分享此算法以及我的一些經驗。
      這篇文章將首先從直觀的角度，介紹Monte-Carlo算法，然后介紹算法基本原理及數(shù)理基礎，最后將會和大家分享幾個基于Monte-Carlo方法的有意思的實驗。所以程序將使用C#實現(xiàn)。
      閱讀本文需要有一些概率論、數(shù)理統(tǒng)計、微積分和計算復雜性的基本知識，不過不用太擔心，我將盡量避免過多的數(shù)學描述，并在適當?shù)牡胤綄τ谟玫降臄?shù)學知識進行簡要的說明。

Monte-Carlo算法引導

      首先，我們來看一個有意思的問題：在一個1平方米的正方形木板上，隨意畫一個圈，求這個圈的面積。
      我們知道，如果圓圈是標準的，我們可以通過測量半徑r，然后用 S = pi * r^2 來求出面積?？墒?，我們畫的圈一般是不標準的，有時還特別不規(guī)則，如下圖是我畫的巨難看的圓圈。

圖1、不規(guī)則圓圈

      顯然，這個圖形不太可能有面積公式可以套用，也不太可能用解析的方法給出準確解。不過，我們可以用如下方法求這個圖形的面積：
      假設我手里有一支飛鏢，我將飛鏢擲向木板。并且，我們假定每一次都能擲在木板上，不會偏出木板，但每一次擲在木板的什么地方，是完全隨機的。即，每一次擲 飛鏢，飛鏢扎進木板的任何一點的概率的相等的。這樣，我們投擲多次，例如100次，然后我們統(tǒng)計這100次中，扎入不規(guī)則圖形內部的次數(shù)，假設為k，那 么，我們就可以用 k/100 * 1 近似估計不規(guī)則圖形的面積，例如100次有32次擲入圖形內，我們就可以估計圖形的面積為0.32平方米。

      以上這個過程，就是Monte-Carlo算法直觀應用例子。
      非形式化地說，Monte-Carlo算法泛指一類算法。在這些算法中，要求解的問題是某隨機事件的概率或某隨機變量的期望。這時，通過“實驗”方法，用頻率代替概率或得到隨機變量的某些數(shù)字特征，以此作為問題的解。
      上述問題中，如果將“投擲一次飛鏢并擲入不規(guī)則圖形內部”作為事件，那么圖形的面積在數(shù)學上等價于這個事件發(fā)生的概率（稍后證明），為了估計這個概率，我們用多次重復實驗的方法，得到事件發(fā)生的頻率 k/100 ，以此頻率估計概率，從而得到問題的解。

      從上述可以看出，Monte-Carlo算法區(qū)別于確定性算法，它的解不一定是準確或正確的，其準確或正確性依賴于概率和統(tǒng)計，但在某些問題上，當重復實 驗次數(shù)足夠大時，可以從很大概率上（這個概率是可以在數(shù)學上證明的，但依賴于具體問題）確保解的準確或正確性，所以，我們可以根據(jù)具體的概率分析，設定實 驗的次數(shù)，從而將誤差或錯誤率降到一個可容忍的程度。
      上述問題中，設總面積為S，不規(guī)則圖形面積為s，共投擲n次，其中擲在不規(guī)則圖形內部的次數(shù)為k。根據(jù)伯努利大數(shù)定理，當試驗次數(shù)增多時，k/n依概率收斂于事件的概率s/S。下面給出嚴格證明：

      上述證明從數(shù)學上說明用頻率估計不規(guī)則圖形面積的合理性，進一步可以給出誤差分析，從而選擇合適的實驗次數(shù)n，以將誤差控制在可以容忍的范圍內，此處從略。

      從上面的分析可以看出，Monte-Carlo算法雖然不能保證解一定是準確和正確，但并不是“撞大運”，其正確性和準確性依賴概率論，有嚴格的數(shù)學基礎，并且通過數(shù)學分析手段對實驗加以控制，可以將誤差和錯誤率降至可容忍范圍。

Monte-Carlo算法的數(shù)理基礎

      這一節(jié)討論Monte-Carlo算法的數(shù)理基礎。
      首先給出三個定義：優(yōu)勢，一致，偏真。這三個定義在后面會經常用到。

      1) 設p為一個實數(shù)，且0.5<p<1。如果一個Monte-Carlo方法對問題任一實例的得到正確解的概率不小于p，則該算法是p正確的，且p-0.5叫做此算法的優(yōu)勢。

      2) 如果對于同一實例，某Monte-Carlo算法不會給出不同的解，則認為該算法時一致的。

      3) 如果某個解判定問題的Monte-Carlo算法，當返回true時是一定正確的。則這個算法時偏真的。注意，這里沒有定義“偏假”，因為“偏假”和偏真是等價的。因為只要互換算法返回的true和false，“偏假”就變成偏真了。

      下面，我們討論Monte-Carlo算法的可靠性和誤差分析。
      總體來說，適用于Monte-Carlo算法的問題，比較常見的有兩類。一類是問題的解等價于某事件概率，如上述求不規(guī)則圖形面積的問題；另一類是判定問題，即判定某個命題是否為真，如主元素存在性判定和素數(shù)測試問題。

      先來分析第一類。對于這類問題，通常的方法是通過大量重復性實驗，用事件發(fā)生的頻率估計概率。之所以能這樣做的數(shù)學基礎，是伯努利大數(shù)法則：事件發(fā)生的頻 率依概率收斂于事件的概率p。這個法則從數(shù)學生嚴格描述了頻率的穩(wěn)定性，直觀意義就是當實驗次數(shù)很大時，頻率與概率偏差很大的概率非常小。此類問題的誤差 分析比較繁雜，此處從略。有興趣的朋友可以參考相關資料。

      接著，我們分析第二類問題。這里，我們只關心一致且偏真的判定問題。下面給出這類問題的正確率分析：

      由以上分析可以看到，對于一致偏真的Monte-Carlo算法，即使調用一次得到正確解的概率非常小，通過多次調用，其正確率會迅速提高，得到的結果非 ?？煽俊＠?，對一個q為0.5的問題，假設p僅為0.01，通過調用1000次，其正確率約為0.9999784，幾乎可以認為是絕對準確的。重要的 是，使用Monte-Carlo算法解判定問題，其正確率不隨問題規(guī)模而改變，這就使得僅需要損失微乎其微的正確性，就可以將算法復雜度降低一個數(shù)量級， 在后面中可以看到具體的例子。

應用實例一：使用Monte-Carlo算法計算定積分

      計算定積分是金融、經濟、工程等領域實踐中經常遇到的問題。通常，計算定積分的經典方法是使用Newton-Leibniz公式：

      這個公式雖然能方便計算出定積分的精確值，但是有一個局限就是要首先通過不定積分得到被積函數(shù)的原函數(shù)。有的時候，求原函數(shù)是非常困難的，而有的函數(shù)，如 f(x) = (sinx)/x，已經被證明不存在初等原函數(shù)，這樣，就無法用Newton-Leibniz公式，只能另想辦法。
      下面就以f(x) = (sinx)/x為例介紹使用Monte-Carlo算法計算定積分的方法。首先需要聲明，f(x) = (sinx)/x在整個實數(shù)域是可積的，但不連續(xù)，在x = 0這一點沒有定義。但是，當x趨近于0其左右極限都是1。為了嚴格起見，我們補充定義當x = 0時f(x) = 1。另外為了需要，這里不加證明地給出f(x)的一些性質：補充x = 0定義后，f(x)在負無窮到正無窮上連續(xù)、可積，并且有界，其界為1，即|f(x)| <= 1，當且僅當x = 0時f(x) = 1。

      下面開始介紹Monte-Carlo積分法。為了便于比較，在本節(jié)我們除了介紹使用Monte-Carlo方法計算定積分外，同時也探討和實現(xiàn)數(shù)值計算中常用的插值積分法，并通過實驗結果數(shù)據(jù)對兩者的效率和精確性進行比較。

1、插值積分法

      我們知道，對于連續(xù)可積函數(shù)，定積分的直觀意義就是函數(shù)曲線與x軸圍成的圖形中，y>0的面積減掉y<0的面積。那么一種直觀的數(shù)值積分方法 是通過插值方法，其中最簡單的是梯形法則：用以f(a)和f(b)為底，x軸和f(a)、f(b)連線為腰組成的梯形面積來近似估計積分。如下圖所示。

圖2、梯形插值

      如圖2所示，藍色部分是x1到x2積分的精確面積，而在梯形插值中，用橙色框所示的梯形面積近似估計積分值。
      顯然，梯形法則的效果一般，而且某些情況下偏差很大，于是，有人提出了一種改進的方法：首先將積分區(qū)間分段，然后對每段計算梯形插值再加起來，這樣精度就大大提高了。并且分段越多，精度越高。這就是復化梯形法則。

      除了梯形插值外，還有許多插值積分法，比較常見的有Sinpson法則，當然對應的也有復化Sinpson法則。下面給出四種插值積分的公式：

      下面是四種插值積分法的程序代碼，用C#編寫。

01 using System;
02 using System.Collections.Generic;
03 using System.Linq;
04 using System.Text;
05   
06 namespace MonteCarlo.Integration
07 {
08     /// <summary>
09     /// 數(shù)值法求積分
10     /// 被積函數(shù)為 f(x) = (sin x)/x
11     /// </summary>
12     public class NumericalIntegrator
13     {
14         /// <summary>
15         /// 梯形法則求積分
16         /// 積分公式為：((b - a) / 2) * [f(a) + f(b)]
17         /// </summary>
18         /// <param name="a">積分下限</param>
19         /// <param name="b">積分上限</param>
20         /// <returns>積分值</returns>
21         public static double TrapezoidalIntegrate(double a, double b)
22         {
23             return ((b - a) / 2) * (Math.Sin(a) / a + Math.Sin(b) / b);
24         }
25   
26         /// <summary>
27         /// 復化梯形法則求積分
28         /// 積分公式為：累加((xi - xi-1) / 2) * [f(xi) + f(xi-1)]  (i=1,2,...,n)
29         /// </summary>
30         /// <param name="a">積分下限</param>
31         /// <param name="b">積分上限</param>
32         /// <param name="n">分段數(shù)量</param>
33         /// <returns>積分值</returns>
34         public static double ComplexTrapezoidalIntegrate(double a, double b, int n)
35         {
36             double result = 0;
37             for (int i = 0; i < n; i++)
38             {
39                 double xa = a + i * (b - a) / n;//區(qū)間積分下限
40                 double xb = xa + (b - a) / n;//區(qū)間積分上限
41   
42                 result += ((xb - xa) / 2) * (Math.Sin(xa) / xa + Math.Sin(xb) / xb);
43             }
44   
45             return result;
46         }
47   
48         /// <summary>
49         /// Sinpson法則求積分
50         /// 積分公式為：((b - a) / 6) * [f(a) + 4 * f((a + b) / 2) + f(b)]
51         /// </summary>
52         /// <param name="a">積分下限</param>
53         /// <param name="b">積分上限</param>
54         /// <returns>積分值</returns>
55         public static double SinpsonIntegrate(double a, double b)
56         {
57             return ((b - a) / 6) * (Math.Sin(a) / a + 4 * (Math.Sin(a + b) / (2 * (a + b))) + Math.Sin(b) / b);
58         }
59   
60         /// <summary>
61         /// 復化Sinpson法則求積分
62         /// 積分公式為：累加(h / 3) * [f(x2i-2) + 4*(f(x2i-1)) + f(x2i)]  (i=1,2,...,n/2 h = (b - a) / n)
63         /// </summary>
64         /// <param name="a">積分下限</param>
65         /// <param name="b">積分上限</param>
66         /// <param name="n">分段數(shù)量(必須為偶數(shù))</param>
67         /// <returns>積分值</returns>
68         public static double ComplexSinpsonIntegrate(double a, double b, int n)
69         {
70             double result = 0;
71             for (int i = 0; i < n / 2 - 1; i++)
72             {
73                 double xa = a + 2 * i * (b - a) / n;//區(qū)間積分下限
74                 double xb = xa + (b - a) / n;//區(qū)間積分限中點
75                 double xc = xb + (b - a) / n;//區(qū)間積分上限
76                 result += ((b - a) / (3 * n) * (Math.Sin(xa) / xa + 4 * (Math.Sin(xb) / xb) + Math.Sin(xc) / xc));
77             }
78   
79             return result;
80         }
81     }
82 }

2、Monte-Carlo積分法

      我們知道，求定積分的直觀意義就是求面積，所以，用Monte-Carlo求積分的原理就是通過模擬統(tǒng)計方法求解面積。即通過向特定區(qū)域隨機產生大量點， 然后統(tǒng)計點落在函數(shù)區(qū)域內的頻率，以此頻率估計面積，從而得到積分值。下面給出Monte-Carlo求取積分的算法程序。

01 using System;
02 using System.Collections.Generic;
03 using System.Linq;
04 using System.Text;
05   
06 namespace MonteCarlo.Integration
07 {
08     /// <summary>
09     /// Monte-Carlo法求積分
10     /// 被積函數(shù)為 f(x) = (sin x)/x
11     /// </summary>
12     public class MonteCarloIntegrator
13     {
14         /// <summary>
15         /// 用Monte-Carlo法求解積分值
16         /// </summary>
17         /// <param name="a">積分下限</param>
18         /// <param name="b">積分上限</param>
19         /// <param name="N">模擬次數(shù)</param>
20         /// <returns>積分值</returns>
21         public static double MonteCarloIntegrate(int a, int b, int N)
22         {
23             Random random = new Random();
24             int positivePointCount = 0;//y >=0 區(qū)間內落入函數(shù)曲線內的點數(shù)目
25             int negativePointCount = 0;//y < 0區(qū)間內落入函數(shù)曲線內的點數(shù)目
26   
27             //統(tǒng)計y >= 0區(qū)間點分布
28             for (int i = 0; i < N; i++)
29             {
30                 double xCoordinate = random.NextDouble();//隨機產生的x坐標
31                 double yCoordinate = random.NextDouble();//隨機產生的y坐標
32                 xCoordinate = a + (b - a) * xCoordinate;//將x規(guī)格化到相應積分區(qū)間
33                 //yCoordinate = 1 * yCoordinate;//將y規(guī)格化到相應區(qū)間
34                 if (Math.Sin(xCoordinate) / xCoordinate >= yCoordinate)
35                 {
36                     positivePointCount++;
37                 }
38             }
39   
40             //統(tǒng)計y < 0區(qū)間點分布
41             for (int i = 0; i < N; i++)
42             {
43                 double xCoordinate = random.NextDouble();//隨機產生的x坐標
44                 double yCoordinate = random.NextDouble();//隨機產生的y坐標
45                 xCoordinate = a + (b - a) * xCoordinate;//將x規(guī)格化到相應積分區(qū)間
46                 yCoordinate = -1 * yCoordinate;//將y規(guī)格化到相應區(qū)間
47                 if (Math.Sin(xCoordinate) / xCoordinate <= yCoordinate)
48                 {
49                     negativePointCount++;
50                 }
51             }
52   
53             double positiveFrequency = (double)positivePointCount / (double)N;//y >= 0區(qū)間內函數(shù)內點頻率
54             double negativeFrequency = (double)negativePointCount / (double)N;//y < 0區(qū)間內函數(shù)內點頻率
55   
56             return (positiveFrequency - negativeFrequency) * (double)(b - a);
57         }
58     }
59 }

3、積分法的測試與比較

      下面對各種積分方法進行測試，對sinx/x在[1,2]區(qū)間上進行定積分。其中，我們分別對復化梯形和復化Sinpson法則做分段為 10，10000，和10000000的積分測試。另外，對Monte-Carlo法也投點數(shù)也分為10，10000，和10000000。測試結果如 下：

圖3、積分法測試結果

      為了分析偏差，我們必須給出一個精確值。但是現(xiàn)在我手頭沒有這個積分的精確值，不過1000萬次的梯形法則和Sinpson法則已經精確度很高了，所以這里就以0.65932985作為基本，進行誤差分析。下面給出分析結果：

表1、積分方法實驗結果

      首先看時間效率。當頻度較低時，各種方法沒有太多差別，但在1000萬級別上復化梯形和復化Sinpson相差不大，而Monte-Carlo算法的效率快一倍。
      而從準確率分析，當頻度較低時，幾種方法的誤差都很大，而隨著頻度提高，插值法要遠遠優(yōu)于Monte-Carlo算法，特別在1000萬級別 時，Monte-Carlo法的相對誤差是插值法的的近萬倍?？傮w來說，在數(shù)值積分方面，Monte-Carlo方法效率高，但準確率不如插值法。

應用實例二：在O(n)復雜度內判定主元素

      這次，我們看一個判定問題。問題是這樣的：在一個長度為n的數(shù)組中，如果有超過[n/2]的元素具有相同的值，那么具有這個值的元素叫做數(shù)組的主元素。現(xiàn)在要求給出一種算法，在O(n)時間內判定給定數(shù)組是否存在主元素。

      如果采用確定性算法，由于最壞情況下要搜索n/2次，而每次要比較的次數(shù)為O(n)量級，這樣，算法的復雜度就是O(n^2)，不可能在O(n)時間內完 成。所以我們只好換一種思路：不是要一個一定正確的結果，而只需要結果在很大概率上正確就行。我們可以這樣做：

圖4、Monte-Carlo法判定主元素

      上述算法，就是用Monte-Carlo思想求解主元素判定問題的過程。由于閾值N是一個給定的常數(shù)，不隨規(guī)模變化而變化，所以這個算法的時間復雜度為 O(n)，符合題設要求。但這個算法給出的解并不是100%正確的，正確率和N有關。N設得過大，影響效率，N太小，正確率太低，那么到底N設多大合適 呢。這就要對算法進行概率分析。

      首先，這個算法是一致且偏真的，證明很簡單，這里從略。所以，如果數(shù)組中不存在主元素，則結果一定正確，而如果存在，調用一次得到正確結果的概率不低于 1/2。由于偏真，在N次調用中只要返回一次True，就可以認為得到正確結果，所以，調用N此得到正確結果的概率不低于1 – (1/2)^N，可以看到，隨著N的增大，這個概率增加很快，只要調用10次，正確率就可以達到99.9%，重要的是，這個正確率和規(guī)模無關，即使數(shù)組的 元素有1千萬億，只需調用10次，正確率依然是99.9%，這就體現(xiàn)出在數(shù)組很大時，Monte-Carlo方法的優(yōu)勢。

      下面是使用Monte-Carlo算法進行主元素測試的C#程序示例。

01 using System;
02 using System.Collections.Generic;
03 using System.Linq;
04 using System.Text;
05   
06 namespace MonteCarlo.Detection
07 {
08     public class PrincipalElementDetector
09     {
10         /// <summary>
11         /// 使用Monte-Carlo發(fā)探測主元素
12         /// </summary>
13         /// <param name="elements">所有元素</param>
14         /// <param name="N">閾值</param>
15         /// <returns>是否存在主元素</returns>
16         public static bool DetectPrincipalElement(IList<int> elements,int N)
17         {
18             Random random = new Random();
19             bool result = false;
20             for (int i = 0; i <= N; i++)
21             {
22                 int index = random.Next(0, elements.Count - 1);
23                 int element = elements[index];
24                 int count = 0;
25                 for (int j = 0; j < elements.Count; j++)
26                 {
27                     if (element == elements[j])
28                     {
29                         count++;
30                     }
31                 }
32                 if (count >= elements.Count / 2)
33                 {
34                     result = true;
35                     break;
36                 }
37             }
38   
39             return result;
40         }
41     }
42 }

      程序很簡單，不做贅述。下面測試這個算法。我們分別將閾值設為1、3、10，并且在每個閾值下測試100次，看看這個算法的準確率如何。測試數(shù)組是[ 4, 5, 8, 1, 8, 4, 9, 2, 2, 2, 2, 2, 5, 7, 8, 2, 2, 2, 2, 2, 1, 0, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 4, 7, 8, 2, 2, 2, 2, 2, 0, 1, 2, 2, 2, 2, 2 ]，其中存在主元素2。下面是測試結果：

圖5、Monte-Carlo算法判定主元素實驗結果

      測試數(shù)組有49個元素，主元素2有29個，比率為59%。從測試結果可以看出，即使閾值為1，正確率也高達84%，而僅僅為3的閾值就使正確率升高到 98%，閾值為10時，100次測試全部正確。雖然理論上來說，閾值為10時有0.41^10=0.013%的概率給出錯誤判斷，但是筆者多次試驗，還沒 有在閾值為10時得到錯誤結果。所以，Monte-Carlo方法求解判定問題，不論從理論上還是實踐中，都是不錯的方法。

      另外一個與判定主元素類似的應用是素數(shù)判定問題，我們知道，對于尋找上百位的大素數(shù)，完全測試在時間效率上時不允許的。于是，結合費馬小定理使用Monte-Carlo法進行素數(shù)判定，是廣泛使用的方法。具體這里不再詳述，感興趣的朋友可以參考相關資料。

應用實例三：分布未知的概率密度函數(shù)模擬

      現(xiàn)在我們來看看Monte-Carlo算法的第三種應用：模擬。在這種應用中，不再是用Monte-Carlo算法求解問題，而是用來模擬難以解析描述的東西。問題是這樣的：

11

      這個問題是實驗室一個師兄在開發(fā)Six Sigma軟件開發(fā)過程管理工具時遇到的一個實際需求，最終Y的概率密度函數(shù)將被用來計算分位點，從而進行過程控制。其中X可能是正態(tài)分布（高斯分布）、 泊松分布、均勻分布或指數(shù)分布等。將多個不同分布的概率密度函數(shù)相加，得到的Y的分布式很難解析表示出來的，但如果是為了計算分位點，我們可以采取這樣一 個策略：對于每一個X，產生若干符合其分布的點，帶入公式就得到若干符合Y分布的點，然后分段計算頻率，從而模擬出Y的分布，這些模擬點也可以用于分位點 計算。這就是Monte-Carlo模擬的思想。

      下面我們實現(xiàn)這個算法，這里的X我們僅給出最常用的正態(tài)分布，如果要實現(xiàn)其他分布，只要編寫相應的隨機點發(fā)生器就可以了。由于C#中只能產生符合均勻分布 的隨機數(shù)，所以我們需要一種算法，將均勻分布的隨機數(shù)轉為正態(tài)分布隨機數(shù)。這種算法很多，Marc Brysbaert在1991年發(fā)表的《Algorithms for randomness in the behavioral sciences: A tutorial》一文中，共總結了5種將均勻分布隨機數(shù)轉為正態(tài)分布的隨機數(shù)的算法，這里筆者用到的是Knuth在1981年提出的一種算法。這個算法 是將符合u(0,1)均勻分布的隨機點轉換為符合N(0,1)標準正態(tài)分布的隨機點p，由概率知識可知，要轉為符合N(e,v)的一般正態(tài)分布，只需進行 p*v+e即可。下面是這個算法：

      下面是根據(jù)這個算法，使用C#編寫的正態(tài)分布隨機點發(fā)生器：

01 using System;
02 using System.Collections.Generic;
03 using System.Linq;
04 using System.Text;
05   
06 namespace MonteCarlo.DistributingSimulation
07 {
08     public class NormalDistributingGenerator
09     {
10         /// <summary>
11         /// 產生符合正態(tài)分布的隨機數(shù)
12         /// 正態(tài)分布的期望為expectation,方差為variance
13         /// </summary>
14         /// <param name="expectation">期望</param>
15         /// <param name="variance">方差</param>
16         /// <param name="N">產生的數(shù)量</param>
17         /// <returns>隨機數(shù)序列</returns>
18         public static IList<double> GenerateNDRNumber(double expectation, double variance, int N)
19         {
20             Random random = new Random();
21             IList<double> randomList = new List<double>();
22             for (int i = 0; i < N; i++)
23             {
24                 double u1, u2, v, z, a;
25                 do
26                 {
27                     u1 = random.NextDouble();
28                     u2 = random.NextDouble();
29                     v = 0.8578 * (2 * u2 - 1);
30                     z = v / u1;
31                     a = 0.25 * Math.Exp(2);
32   
33                     if (a < 1 - u1)
34                     {
35                         break;
36                     }
37   
38                 } while (a > 0.295 / u1 + 0.35 || a > -Math.Log(u1, Math.E));
39   
40                 randomList.Add(z * Math.Sqrt(variance) + expectation);
41             }
42   
43             return randomList;
44         }
45     }
46 }

      接著是利用這個正態(tài)分布發(fā)生器獲得X的隨機值，并計算出Y的隨機值的代碼。也就是Y的隨機點發(fā)生器：

01 using System;
02 using System.Collections.Generic;
03 using System.Linq;
04 using System.Text;
05   
06 namespace MonteCarlo.DistributingSimulation
07 {
08     public class DistributingSimulator
09     {
10         /// <summary>
11         /// 模擬多個正態(tài)分布之和的分布情況，產生符合復合分布的隨機點
12         /// y = a0 + a1*N(e1,v1) + ... + an*N(en,vn)
13         /// N(e,v)表示期望為e，方差為v的正態(tài)分布
14         /// </summary>
15         /// <param name="a">常數(shù)列</param>
16         /// <param name="e">期望列</param>
17         /// <param name="v">方差列</param>
18         /// <param name="N">產生模擬點的個數(shù)</param>
19         /// <returns>模擬點序列</returns>
20         public static IList<double> Simulate(IList<double> a,IList<double> e,IList<double> v,int N)
21         {
22             IList<double> result = new List<double>();
23             IList<IList<double>> randomLists = new List<IList<double>>();
24             int count = a.Count - 1;
25   
26             //產生各個自變量的隨機序列
27             for (int i = 1; i <= count; i++)
28             {
29                 randomLists.Add(NormalDistributingGenerator.GenerateNDRNumber(e[i], v[i], N));
30             }
31   
32             //帶入公式
33             for (int j = 0; j < N; j++)
34             {
35                 double y = 0;
36                 for (int k = 1; k <= count; k++)
37                 {
38                     y += a[k] * randomLists[k - 1][j];
39                 }
40                 y += a[0];
41                 result.Add(y);
42             }
43   
44             return result;
45         }
46     }
47 }

      這樣，我們就可以產生任意多個符合Y分布的隨機點，從而借此模擬Y的概率密度分布。

      接著，我們測試一下這個模擬程序的效果，首先我們將初始值設為僅有一個符合標準正態(tài)分布的X，這樣Y=X，我們看看直接模擬一個標準正態(tài)分布的效果。這里，我們產生100萬個隨機點。

圖6、使用Monte-Carlo算法模擬標準正態(tài)分布

      可以看到，模擬效果基本令人滿意。接下來，我們實際應用這個程序模擬一個分布未知的Y，其中Y = 15 + 2*N(2,8) + 5*N(-10,9) + 7*N(0,0.5)。模擬結果如下：

圖7、使用Monte-Carlo算法模擬未知分布

      有了符合Y分布的大量隨機點以及頻率統(tǒng)計，就可以隨心所欲繪出分布模擬圖，并進行分位點計算。這樣就用Monte-Carlo算法解決了本節(jié)開頭提到的問題。

總結

      本文首先通過一個不規(guī)則圖形面積計算的例子直觀介紹了Monte-Carlo算法，然后給出了Monte-Carlo算法在應用過程中需要了解的數(shù)理基礎。然后大篇幅介紹了三個應用：計算、判定和模擬。
      總體來說，當需要求解的問題依賴概率時，Monte-Carlo方法是一個不錯的選擇。但這個算法畢竟不是確定性算法，在應用過程中需要冒一定“風險”， 這就要求不能濫用這個算法，在應用過程中，需要對其準確率或正確率進行數(shù)理分析，合理設計實驗，從而得到良好的結果，并將風險控制在可容忍的范圍內。
      其實，不確定性算法不只Monte-Carlo一種，Sherwood算法、Las Vegas算法和遺傳算法等也是經典的不確定算法。在很多問題上，不確定性算法具有很好大的應用價值。有興趣的朋友可以參考相關資料。

參考文獻

      [1] 孫海燕，周夢等 著，應用數(shù)理統(tǒng)計。北京航空航天大學出版社，2008.8
      [2] 盛驟，謝式千，潘承毅 著，概率論與數(shù)理統(tǒng)計。高等教育出版社，2006.12
      [3] David Kincaid，WardCheney 著，王國榮等 譯，數(shù)值分析(原書第三版)。機械工業(yè)出版社，2005.9
      [4] Thomas H. Cormen等 著，算法導論(第二版，影印版)。高等教育出版社，2002.5
      [5] 王曉東 著，計算機算法設計與分析。電子工業(yè)出版社，2001.1
      [6] Marc Brysbaert，Algorithms for randomness in the behavioral sciences: A tutorial。Behavior Research Methods, Instruments, & Computers 1991, 23 (1) 45-60
      [7] Patrick Smacchia 著，施凡等 譯，C#和.NET2.0 平臺、語言與框架。2008.1
      [8] Google。www.google.com
      [9] Wikipedia。www.

    本站是提供個人知識管理的網絡存儲空間，所有內容均由用戶發(fā)布，不代表本站觀點。請注意甄別內容中的聯(lián)系方式、誘導購買等信息，謹防詐騙。如發(fā)現(xiàn)有害或侵權內容，請點擊一鍵舉報。
    轉藏 分享 獻花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多