提出
蒙特卡羅方法於20世紀40年代美國在第二次世界大戰中研製核子彈的“曼哈頓計畫”計畫的成員S.M.烏拉姆和J.馮·諾伊曼首先提出。數學家馮·諾伊曼用馳名世界的賭城—摩納哥的MonteCarlo—來命名這種方法,為它蒙上了一層神秘色彩。在這之前,蒙特卡羅方法就已經存在。1777年,法國數學家布豐(GeorgesLouisLecleredeBuffon,1707—1788)提出用投針實驗的方法求圓周率π。這被認為是蒙特卡羅方法的起源。概述
以機率和統計的理論、方法為基礎的一種計算方法,將所求解的問題同一定的機率模型相聯繫,用電子計算機實現統計模擬或抽樣,以獲得問題的近似解,故又稱統計模擬法或統計試驗法。
蒙特卡羅是摩納哥的一個城市,以賭博聞名於世界。蒙特卡羅法借用這一城市的名稱是為了象徵性地表明該方法的機率統計的特點。
蒙特卡羅法作為一種計算方法,是由S.M.烏拉姆和J.馮·諾伊曼在20世紀40年代中葉為研製核武器的需要而首先提出來的。在此之前,該方法的基本思想實際上早已被統計學家所採用了。例如,早在17世紀,人們就知道了依頻數來決定機率的方法。
20世紀40年代中葉,出現了電子計算機,使得用數學方法模擬大量的試驗成為可能。另外,隨著科學技術的不斷發展,出現了越來越多的複雜而困難的問題,用通常的解析方法或數值方法都很難加以解決。蒙特卡羅法就是在這些情況下,作為一種可行的而且是不可缺少的計算方法被提出和迅速發展起來的。
套用領域
蒙特卡羅方法有很強的適應性,問題的幾何形狀的複雜性對它的影響不大。該方法的收斂性是指機率意義下的收斂,因此問題維數的增加不會影響它的收斂速度,而且存貯單元也很省,這些是用該方法處理大型複雜問題時的優勢。因此,隨著電子計算機的發展和科學技術問題的日趨複雜,蒙特卡羅方法的套用也越來越廣泛。它不僅較好地解決了多重積分計算、微分方程求解、積分方程求解、特徵值計算和非線性方程組求解等高難度和複雜的數學計算問題,而且在統計物理、核物理、真空技術、系統科學、信息科學、公用事業、地質、醫學,可靠性及計算機科學等廣泛的領域都得到成功的套用。尤其在電路設計領域,蒙特卡羅方法是一項必不可少的分析工具;主流的電子電路設計自動化軟體,比如BtEDA、Ultrasim等等,都採用蒙特卡羅方法進行電路性能的機率分析。
基本思想
當所求解問題是某種隨機事件出現的機率,或者是某個隨機變數的期望值時,通過某種“實驗”的方法,以這種事件出現的頻率估計這一隨機事件的機率,或者得到這個隨機變數的某些數字特徵,並將其作為問題的解。
工作過程
蒙特卡羅方法的解題過程可以歸結為三個主要步驟:構造或描述機率過程;實現從已知機率分布抽樣;建立各種估計量。
蒙特卡羅方法解題過程的三個主要步驟:
(1)構造或描述機率過程
對於本身就具有隨機性質的問題,如粒子輸運問題,主要是正確描述和模擬這個機率過程,對於本來不是隨機性質的確定性問題,比如計算定積分,就必須事先構造一個人為的機率過程,它的某些參量正好是所要求問題的解。即要將不具有隨機性質的問題轉化為隨機性質的問題。
(2)實現從已知機率分布抽樣
構造了機率模型以後,由於各種機率模型都可以看作是由各種各樣的機率分布構成的,因此產生已知機率分布的隨機變數(或隨機向量),就成為實現蒙特卡羅方法模擬實驗的基本手段,這也是蒙特卡羅方法被稱為隨機抽樣的原因。最簡單、最基本、最重要的一個機率分布是(0,1)上的均勻分布(或稱矩形分布)。隨機數就是具有這種均勻分布的隨機變數。隨機數序列就是具有這種分布的總體的一個簡單子樣,也就是一個具有這種分布的相互獨立的隨機變數序列。產生隨機數的問題,就是從這個分布的抽樣問題。在計算機上,可以用物理方法產生隨機數,但價格昂貴,不能重複,使用不便。另一種方法是用數學遞推公式產生。這樣產生的序列,與真正的隨機數序列不同,所以稱為偽隨機數,或偽隨機數序列。不過,經過多種統計檢驗表明,它與真正的隨機數,或隨機數序列具有相近的性質,因此可把它作為真正的隨機數來使用。由已知分布隨機抽樣有各種方法,與從(0,1)上均勻分布抽樣不同,這些方法都是藉助於隨機序列來實現的,也就是說,都是以產生隨機數為前提的。由此可見,隨機數是我們實現蒙特卡羅模擬的基本工具。
(3)建立各種估計量
一般說來,構造了機率模型並能從中抽樣後,即實現模擬實驗後,我們就要確定一個隨機變數,作為所要求的問題的解,我們稱它為無偏估計。建立各種估計量,相當於對模擬實驗的結果進行考察和登記,從中得到問題的解。
數學套用
通常蒙特·卡羅方法通過構造符合一定規則的隨機數來解決數學上的各種問題。對於那些由於計算過於複雜而難以得到解析解或者根本沒有解析解的問題,蒙特·卡羅方法是一種有效的求出數值解的方法。一般蒙特·卡羅方法在數學中最常見的套用就是蒙特·卡羅積分。
工作過程
在解決實際問題的時候套用蒙特·卡羅方法主要有兩部分工作:1、用蒙特·卡羅方法模擬某一過程時,需要產生某一機率分布的隨機變數。
2、用統計方法把模型的數字特徵估計出來,從而得到實際問題的數值解。
分子模擬計算
使用蒙特·卡羅方法進行分子模擬計算是按照以下步驟進行的:1、使用隨機數發生器產生一個隨機的分子構型。
2、對此分子構型的其中粒子坐標做無規則的改變,產生一個新的分子構型。
3、計算新的分子構型的能量。
4、比較新的分子構型於改變前的分子構型的能量變化,判斷是否接受該構型。
若新的分子構型能量低於原分子構型的能量,則接受新的構型,使用這個構型重複再做下一次疊代。若新的分子構型能量高於原分子構型的能量,則計算玻爾茲曼因子,並產生一個隨機數。若這個隨機數大於所計算出的玻爾茲曼因子,則放棄這個構型,重新計算。若這個隨機數小於所計算出的玻爾茲曼因子,則接受這個構型,使用這個構型重複再做下一次疊代。
5、如此進行疊代計算,直至最後搜尋出低於所給能量條件的分子構型結束。
項目管理
項目管理中蒙特·卡羅模擬方法的一般步驟是:1、對每一項活動,輸入最小、最大和最可能估計數據,並為其選擇一種合適的先驗分布模型;
2、計算機根據上述輸入,利用給定的某種規則,快速實施充分大量的隨機抽樣
3、對隨機抽樣的數據進行必要的數學計算,求出結果
4、對求出的結果進行統計學處理,求出最小值、最大值以及數學期望值和單位標準偏差
5、根據求出的統計學處理數據,讓計算機自動生成機率分布曲線和累積機率曲線(通常是基於常態分配的機率累積S曲線)
6、依據累積機率曲線進行項目風險分析。
力學
在力學中,蒙特卡羅方法多被用來求解稀薄氣體動力學問題,其中最為成功的是澳大利亞G.A.伯德等人發展的直接模擬統計試驗法。此法通過在計算機上追蹤幾千個或更多的模擬分子的運動、碰撞及其與壁面的相互作用,以模擬真實氣體的流動。它的基本假設與玻耳茲曼方程一致,但它是通過追蹤有限個分子的空間位置和速度來代替計算真實氣體中分布函式。模擬的相似條件是流動的克努曾數(Kn)相等,即數密度與碰撞截面之積保持常數。對每個分子分配以記錄其位置和速度的單元。在模擬過程中分別考慮分子的運動和碰撞,在此平均碰撞時間間隔內,分別計算分子無碰撞的運動和典型碰撞。若空間格線取得足夠小,其中任意兩個分子都可以互相碰撞。具體決定哪兩個剛體分子相撞,是隨機取一對分子,計算它們的相對速度,根據此值與最大相對速度的比值和隨機取樣比較的結果,來決定該對分子是否入選。碰撞後分子的速度根據特定分子模型的碰撞力學和隨機取樣決定。分子與壁面碰撞後的速度,則根據特定的反射模型和隨機取樣決定。對於運動分子的位置和速度的追蹤和求矩可以得出氣體的密度、溫度、速度等一些感興趣的巨觀參量。而對於分子與壁面間的動量和能量交換的記錄則給出阻力、舉力和熱交換係數等的數學期望值。發展運用
從理論上來說,蒙特卡羅方法需要大量的實驗。實驗次數越多,所得到的結果才越精確。
從表中數據可以看到,一直到公元20世紀初期,儘管實驗次數數以千計,利用蒙特卡羅方法所得到的圓周率π值,還是達不到公元5世紀祖沖之的推算精度。這可能是傳統蒙特卡羅方法長期得不到推廣的主要原因。
計算機技術的發展,使得蒙特卡羅方法在最近10年得到快速的普及。現代的蒙特卡羅方法,已經不必親自動手做實驗,而是藉助計算機的高速運轉能力,使得原本費時費力的實驗過程,變成了快速和輕而易舉的事情。它不但用於解決許多複雜的科學方面的問題,也被項目管理人員經常使用。
藉助計算機技術,蒙特卡羅方法實現了兩大優點:
一是簡單,省卻了繁複的數學推導和演算過程,使得一般人也能夠理解和掌握
二是快速。簡單和快速,是蒙特卡羅方法在現代項目管理中獲得套用的技術基礎。