蒙特卡羅(Monte Carlo)方法簡介

出自科學網    原文地址：http://blog.sciencenet.cn/blog-324394-292355.html

蒙特卡羅(Monte Carlo)方法，也稱為計算機隨機模擬方法，是一種基於"隨機數"的計算方法。
    
    一 起源

    這一方法源於美國在第二次世界大戰進研製原子彈的"曼哈頓計劃"。Monte Carlo方法創始人主要是這四位：Stanislaw Marcin Ulam, Enrico Fermi, John von Neumann（學計算機的肯定都認識這個牛人吧）和 Nicholas Metropolis。

    Stanislaw Marcin Ulam是波蘭裔美籍數學家，早年是研究拓撲的，後因參與曼哈頓工程，興趣遂轉向應用數學，他首先提出用Monte Carlo方法解決計算數學中的一些問題，然後又將其應用到解決鏈式反應的理論中去，可以說是MC方法的奠基人；Enrico Fermi是個物理大牛，理論和實驗同時都是大牛，這在物理界很少見，在「物理大牛的八卦」那篇文章裡提到這個人很多次，對於這麼牛的人只能是英年早逝了（別說我嘴損啊，上帝都嫉妒！）；John von Neumann可以說是計算機界的牛頓吧，太牛了，結果和Fermi一樣，被上帝嫉妒了；Nicholas Metropolis，希臘裔美籍數學家，物理學家，計算機科學家，這個人對Monte Carlo方法做的貢獻相當大，正式由於他提出的一種什麼算法（名字忘了），才使得Monte Carlo方法能夠得到如此廣泛的應用，這人現在還活著，與前幾位牛人不同，Metropolis很專一，他一生主要的貢獻就是Monte Carlo方法。

    蒙特卡羅方法的名字來源於摩納哥的一個城市蒙地卡羅，該城市以賭博業聞名，而蒙特·羅方法正是以概率為基礎的方法。與它對應的是確定性算法。

    二 解決問題的基本思路

    Monte Carlo方法的基本思想很早以前就被人們所發現和利用。早在17世紀，人們就知道用事件發生的"頻率"來決定事件的"概率"。19世紀人們用投針試驗的方法來決定圓周率π。本世紀40年代電子計算機的出現，特別是近年來高速電子計算機的出現，使得用數學方法在計算機上大量、快速地模擬這樣的試驗成為可能。 
    
    為了說明Monte Carlo方法的基本思想，讓我們先來看一個簡單的例子，從此例中你可以感受如何用Monte Carlo方法考慮問題。

        例1:比如y=x^2(對x)從0積到1。結果就是下圖紅色部分的面積：

    注意到函數在(1,1)點的取值為1，所以整個紅色區域在一個面積為1的正方形裡面。所以所求區域的面積即為 在正方形區域內任取點，點落在所求區域的概率。這個限制條件是y<x^2。用matlab模擬，做一百萬次(即共取1000000個點)，結果為0.3328。

    1）總結Monte Carlo方法的基本思想：所求解問題是某隨機事件A出現的概率（或者是某隨機變量B的期望值）。通過某種「實驗」的方法，得出A事件出現的頻率，以此估計出A事件出現的概率（或者得到隨機變量B的某些數字特徵，得出B的期望值）。 
　　
    2）工作過程

　　
　　在解決實際問題的時候應用蒙特卡羅方法主要有兩部分工作：
　　用蒙特卡羅方法模擬某一過程時，需要產生各種概率分布的隨機變量。 
　　用統計方法把模型的數字特徵估計出來，從而得到實際問題的數值解。

　　
    3）蒙特卡羅解題三個主要步驟：

　　 
　　 （1）構造或描述概率過程： 對於本身就具有隨機性質的問題，如粒子輸運問題，主要是正確描述和模擬這個概率過程，對於本來不是隨機性質的確定性問題，比如計算定積分，就必須事先構造一個人為的概率過程，它的某些參量正好是所要求問題的解。即要將不具有隨機性質的問題轉化為隨機性質的問題。 
　　 （2）實現從已知概率分布抽樣： 構造了概率模型以後，由於各種概率模型都可以看作是由各種各樣的概率分布構成的，因此產生已知概率分布的隨機變量（或隨機向量），就成為實現蒙特卡羅方法模擬實驗的基本手段，這也是蒙特卡羅方法被稱為隨機抽樣的原因。最簡單、最基本、最重要的一個概率分布是(0,1)上的均勻分布（或稱矩形分布）。隨機數就是具有這種均勻分布的隨機變量。隨機數序列就是具有這種分布的總體的一個簡單子樣，也就是一個具有這種分布的相互獨立的隨機變數序列。產生隨機數的問題，就是從這個分布的抽樣問題。在計算機上，可以用物理方法產生隨機數，但價格昂貴，不能重複，使用不便。另一種方法是用數學遞推公式產生。這樣產生的序列，與真正的隨機數序列不同，所以稱為偽隨機數，或偽隨機數序列。不過，經過多種統計檢驗表明，它與真正的隨機數，或隨機數序列具有相近的性質，因此可把它作為真正的隨機數來使用。由已知分布隨機抽樣有各種方法，與從(0,1)上均勻分布抽樣不同，這些方法都是藉助於隨機序列來實現的，也就是說，都是以產生隨機數為前提的。由此可見，隨機數是我們實現蒙特卡羅模擬的基本工具。 建立各種估計量： 一般說來，構造了概率模型並能從中抽樣後，即實現模擬實驗後，我們就要確定一個隨機變量，作為所要求的問題的解，我們稱它為無偏估計。 
　　 （3）建立各種估計量，相當於對模擬實驗的結果進行考察和登記，從中得到問題的解。 例如：檢驗產品的正品率問題，我們可以用1表示正品，0表示次品，於是對每個產品檢驗可以定義如下的隨機變數Ti，作為正品率的估計量： 於是，在N次實驗後，正品個數為： 顯然，正品率p為： 不難看出，Ti為無偏估計。當然，還可以引入其它類型的估計，如最大似然估計，漸進有偏估計等。但是，在蒙特卡羅計算中，使用最多的是無偏估計。 用比較抽象的概率語言描述蒙特卡羅方法解題的手續如下：構造一個概率空間(W ,A,P)，其中，W 是一個事件集合，A是集合W 的子集的s 體，P是在A上建立的某個概率測度；在這個概率空間中，選取一個隨機變量q (w ),w &Icirc; W ,使得這個隨機變量的期望值 正好是所要求的解Q ，然後用q (w )的簡單子樣的算術平均值作為Q 的近似值。 
　　
    三 本方法特點

　　
　　直接追蹤粒子，物理思路清晰，易於理解。 
　　· 採用隨機抽樣的方法，較真切的模擬粒子輸運的過程，反映了統計漲落的規律。
　　· 不受系統多維、多因素等複雜性的限制，是解決複雜系統粒子輸運問題的好方法。 
　　· MC程序結構清晰簡單。
　　· 研究人員採用MC方法編寫程序來解決粒子輸運問題，比較容易得到自己想得到的任意中間結果，應用靈活性強。
　　· MC方法主要弱點是收斂速度較慢和誤差的概率性質，其概率誤差正比於，如果單純以增大抽樣粒子個數N來減小誤差，就要增加很大的計算量。

    另一類形式與Monte Carlo方法相似，但理論基礎不同的方法-"擬蒙特卡羅方法"(Quasi-Monte Carlo方法)-近年來也獲得迅速發展。我國數學家華羅庚、王元提出的"華-王"方法即是其中的一例。這種方法的基本思想是"用確定性的超均勻分布序列(數學上稱為Low Discrepancy Sequences)代替Monte Carlo方法中的隨機數序列。對某些問題該方法的實際速度一般可比Monte Carlo方法提出高數百倍，並可計算精確度。

    蒙特卡羅方法在金融工程學，宏觀經濟學，計算物理學(如粒子輸運計算、量子熱力學計算、空氣動力學計算)等領域應用廣泛。
　　
    四 Monte Carlo方法的計算程序

　　
　　關於蒙特卡羅方法的計算程序已經有很多，如：EGS4、FLUKA、ETRAN、ITS、MCNP、GEANT等。這些程序大多經過了多年的發展，花費了幾百人年的工作量。除歐洲核子研究中心（CERN）發行的GEANT主要用於高能物理探測器響應和粒子徑跡的模擬外，其它程序都深入到低能領域，並被廣泛應用。就電子和光子輸運的模擬而言，這些程序可被分為兩個系列：
　　1．EGS4、FLUKA、GRANT 
　　2．ETRAN、ITS、MCNP 這兩個系列的區別在於：對於電子輸運過程的模擬根據不同的理論採用了不同的算法。 
　　EGS4和ETRAN分別為兩個系列的基礎，其它程序都採用了它們的核心算法。 
　　ETRAN(for Electron Transport)由美國國家標準局輻射研究中心開發，主要模擬光子和電子，能量範圍可從1KeV到1GeV。 
　　ITS(The integrated TIGER Series of Coupled Electron/Photon Monte Carlo Transport Codes )是由美國聖地牙哥（Sandia）國家實驗室在ETRAN的基礎上開發的一系列模擬計算程序，包括TIGER 、CYLTRAN 、ACCEPT等，它們的主要差別在於幾何模型的不同。
　　TIGER研究的是一維多層的問題，CYLTRAN研究的是粒子在圓柱形介質中的輸運問題，ACCEPT是解決粒子在三維空間輸運的通用程序。 
　　NCNP(Monte Carlo Neutron and Photo Transport Code)由美國橡樹林國家實驗室(Oak Ridge National Laboratory)開發的一套模擬中子、光子和電子在物質中輸運過程的通用MC 計算程序，在它早期的版本中並不包含對電子輸運過程的模擬，只模擬中子和光子，較新的版本（如MCNP4A）則引進了ETRAN，加入了對電子的模擬。 
　　FLUKA 是一個可以模擬包括中子、電子、光子和質子等30餘種粒子的大型MC計算程序，它把EGS4容納進來以完成對光子和電子輸運過程的模擬，並且對低能電子的輸運算法進行了改進。

    五 Monte Carlo方法相關的一些資料

     一個網站：http://csep1.phy.ornl.gov/mc/mc.html
    《蒙特卡羅方法》 徐鍾濟著 上海科學技術出版社
    《科學計算中的蒙特卡羅策略》(當代科學前沿論叢)(Monte Carlo Strategies in Scientific Computing) 作者:劉軍  譯者:唐年勝 周勇 徐亮  
     統計物理學中的蒙特卡羅模擬方法  ( 德) 賓德(Binder,K.),赫爾曼(Heermann,D.W.) 著  北京大學出版社  1994.2 
     小尺寸半導體器件的蒙特卡羅模擬  葉良修編著  科學出版社  1997.2 
     蒙特卡羅方法及其在粒子輸運問題中的應用  裴鹿成, 張孝澤著  科學出版社  1980.10   
     統計試驗法:( 蒙特卡羅法) 及其在電子數字計算機上的實現  (蘇) 布斯連科( Н. П. Бусленко), (蘇) 施  上海科學技術出版社  
     若干本書：人大經濟論壇http://www.pinggu.org/bbs/thread-445802-1-1.html
     高分子科學中的Monte Carlo方法  楊玉良  復旦大學出版社  1993.12  7-309-01361-1 
     Monte Carlo simulation of semiconductor devices  C. Moglestue.  Chapman & Hall，  1993.  041247770X 
     Monte Carlo methods in statistical physics  with contributions by K. Binder ... [et al.] ; edi  Springer-Verlag,  1979.  
     guide to Monte Carlo simulations in statistical physics  David P. Landau, Kurt Binder.  Cambridge University Press,  c2000.  
     Monte Carlo methods in statistical physics  edited by K. Binder ; with contributions by K. Bin  Springer-Verlag,  c1986. 
     Applications of the Monte Carlo method in statistical physics  edited by K. Binder.  Springer,  1984.  
     Monte Carlo Device Simulation  Karl Hess  Kluwer Acadmic 

 

參考資料：1、http://baike.baidu.com/view/1675475.htm?fr=ala0_1
                     2、http://baike.baidu.com/view/42460.htm?fr=ala0_1_1
                     3、http://gorilla.blogbus.com/logs/4669.html
                     4、http://blog.sina.com.cn/s/blog_5e8154170100cgc4.html
                     5、http://www.charlesgao.com/?p=121

熱經典文章推薦：

回復以下關鍵字獲取相關文章：

數據挖掘 | 機器學習 | 數學之美 | 遊戲算法 | 生活數學 | 排名算法|大型網站技術演進 | 數學名人 | 學科概述 | 計算機科學 | 搜尋引擎

據說好多人都不知道長按圖片也能關注，你知道嗎？