蒙特卡罗算法

**蒙地卡羅方法**（英語：Monte Carlo method），也稱**統計類比方法**，是 1940 年代中期由於科學技術的發展和電腦的發明，而提出的一種以機率統計理論為指導的數值計算方法。是指使用亂數（或更常見的偽亂數）來解決很多計算問題的方法。

20 世紀 40 年代，在科學家馮・紐曼、斯塔尼斯拉夫・烏拉姆和尼古拉斯・梅特羅波利斯於洛斯阿拉莫斯國家實驗室為核武器計劃工作時，發明了蒙地卡羅方法。因為烏拉姆的叔叔經常在摩納哥的蒙地卡羅賭場輸錢得名，而蒙地卡羅方法正是以機率為基礎的方法。

與它對應的是確定性演算法。

蒙地卡羅方法在金融工程學、總體經濟學、生物醫學、計算物理學（如粒子輸運計算、量子熱力學計算、空氣動力學計算）、機器學習等領域應用廣泛。

## 基本概念

通常蒙地卡羅方法可以粗略地分成兩類：一類是所求解的問題本身具有內在的隨機性，藉助電腦的運算能力可以直接類比這種隨機的過程。例如在核物理研究中，分析中子在反應爐中的傳輸過程。中子與原子核作用受到量子力學規律的制約，人們只能知道它們相互作用發生的機率，卻無法準確獲得中子與原子核作用時的位置以及裂變產生的新中子的行進速率和方向。科學家依據其機率進行隨機抽樣得到裂變位置、速度和方向，這樣類比大量中子的行為後，經過統計就能獲得中子傳輸的範圍，作為反應爐設計的依據。 

另一種類型是所求解問題可以轉化為某種隨機分布的特徵數，比如隨機事件出現的機率，或者隨機變數的期望值。通過隨機抽樣的方法，以隨機事件出現的頻率估計其機率，或者以抽樣的數字特徵估算隨機變數的數字特徵，並將其作為問題的解。這種方法多用於求解複雜的多維積分問題。 

假設我們要計算一個不規則圖形的面積，那麼圖形的不規則程度和分析性計算（比如，積分）的複雜程度是成正比的。蒙地卡羅方法基於這樣的想法：假設你有一袋豆子，把豆子均勻地朝這個圖形上撒，然後數這個圖形之中有多少顆豆子，這個豆子的數目就是圖形的面積。當你的豆子越小，撒的越多的時候，結果就越精確。藉助電腦程式可以生成大量均勻分布坐標點，然後統計出圖形內的點數，透過它們占總點數的比例和坐標點生成範圍的面積就可以求出圖形面積。

## 工作過程

在解決實際問題的時候應用蒙地卡羅方法主要有兩部分工作：

1. 用蒙地卡羅方法類比某一過程時，需要產生各種機率分布的隨機變數。
2. 用統計方法把模型的數字特徵估計出來，從而得到實際問題的數值解。

## 分子類比計算的步驟

使用蒙地卡羅方法進行分子類比計算是按照以下步驟進行的：

1. 使用亂數生成器產生一個隨機的分子構型。
2. 對此分子構型的其中粒子坐標做無規則的改變，產生一個新的分子構型。
3. 計算新的分子構型的能量。
4. 比較新的分子構型與改變前的分子構型的能量變化，判斷是否接受該構型。
  * 若新的分子構型能量低於原分子構型的能量，則接受新的構型，使用這個構型重複再做下一次迭代。
  * 若新的分子構型能量高於原分子構型的能量，則計算玻爾茲曼因子，並產生一個亂數。
    * 若這個亂數大於所計算出的玻爾茲曼因子，則放棄這個構型，重新計算。
    * 若這個亂數小於所計算出的玻爾茲曼因子，則接受這個構型，使用這個構型重複再做下一次迭代。
5. 如此進行迭代計算，直至最後搜尋出低於所給能量條件的分子構型結束。

## 在數學中的應用

通常蒙地卡羅方法透過構造符合一定規則的亂數來解決數學上的各種問題。對於那些由於計算過於複雜而難以得到解析解或者根本沒有解析解的問題，蒙地卡羅方法是一種有效的求出數值解的方法。一般蒙地卡羅方法在數學中最常見的應用就是蒙特卡羅積分。下面是蒙地卡羅方法的兩個簡單應用：

### 積分

非權重蒙特卡羅積分，也稱確定性抽樣，是對被積函數變數區間進行隨機均勻抽樣，然後對抽樣點的函數值求平均，從而可以得到函數積分的近似值。此種方法的正確性是基於機率論的中央極限定理。當抽樣點數為 m 時，使用此種方法所得近似解的統計誤差只與 m 有關（與 ${\begin{smallmatrix}{\frac {1}{\sqrt[{}]{m}}}\end{smallmatrix}}$ 正相關），不隨積分維數的改變而改變。因此當積分維度較高時，蒙地卡羅方法相對於其他數值解法更優。

### 圓周率

蒙地卡羅方法可用於近似計算圓周率：讓電腦每次隨機生成兩個 0 到 1 之間的數，看以這兩個實數為橫縱坐標的點是否在單位圓內。生成一系列隨機點，統計單位圓內的點數與總點數，（圓面積和正方形面積之比為 PI:4，PI 為圓周率），當隨機點取得越多時，其結果越接近於圓周率（然而準確度仍有爭議：即使取 10 的 9 次方個隨機點時，其結果也僅在前 4 位元與圓周率吻合）。用蒙地卡羅方法近似計算圓周率的先天不足是：第一，電腦產生的亂數是受到儲存格式的限制的，是離散的，並不能產生連續的任意實數；上述做法將平面分割成一個個網格，在空間也不是連續的，由此計算出來的面積當然與圓或多或少有差距。

## 在機器學習中的應用

蒙地卡羅演算法也常用於機器學習，特別是強化學習的演算法中。一般情況下，針對得到的樣本資料集建立相對模糊的模型，透過蒙地卡羅方法對於模型中的參數進行選取，使之於原始資料的殘差儘可能的小。從而達到建立模型擬合樣本的目的。

## 參見

* 遺傳演算法
* 粒子濾波器
* 擬蒙地卡羅方法

## 注釋

## 參考

* Anderson, Herbert L. Metropolis, Monte Carlo and the MANIAC (PDF). Los Alamos Science. 1986, **14**: 96–108 [2018-04-29]. （原始內容 (PDF) 存檔於 2017-07-02）.
* Benov, Dobriyan M. The Manhattan Project, the first electronic computer and the Monte Carlo method. Monte Carlo Methods and Applications. 2016, **22** (1): 73–79 [2018-04-29]. doi:10.1515/mcma-2016-0102. （原始內容存檔於 2019-06-03）.
* Baeurle, Stephan A. Multiscale modeling of polymer materials using field-theoretic methodologies: A survey about recent developments. Journal of Mathematical Chemistry. 2009, **46** (2): 363–426. doi:10.1007/s10910-008-9467-3.
* Berg, Bernd A. Markov Chain Monte Carlo Simulations and Their Statistical Analysis (With Web-Based Fortran Code). Hackensack, NJ: World Scientific. 2004. ISBN 981-238-935-0.
* Binder, Kurt. The Monte Carlo Method in Condensed Matter Physics. New York: Springer. 1995. ISBN 0-387-54369-4.
* Caflisch, R. E. Monte Carlo and quasi-Monte Carlo methods. Acta Numerica **7**. Cambridge University Press. 1998: 1–49.
* Davenport, J. H. Primality testing revisited. Proceeding ISSAC '92 Papers from the international symposium on Symbolic and algebraic computation. 1992: 123 129. ISBN 0-89791-489-9. doi:10.1145/143242.143290.
* Doucet, Arnaud; Freitas, Nando de; Gordon, Neil. Sequential Monte Carlo methods in practice. New York: Springer. 2001. ISBN 0-387-95146-6.
* Eckhardt, Roger. Stan Ulam, John von Neumann, and the Monte Carlo method (PDF). Los Alamos Science, Special Issue. 1987, (15): 131–137 [2018-04-29]. （原始內容 (PDF) 存檔於 2014-09-09）.
* Fishman, G. S. Monte Carlo: Concepts, Algorithms, and Applications. New York: Springer. 1995. ISBN 0-387-94527-X.
* C. Forastero and L. Zamora and D. Guirado and A. Lallena. A Monte Carlo tool to simulate breast cancer screening programmes. Phys. In Med. And Biol. 2010, **55** (17): 5213–5229. Bibcode:2010PMB....55.5213F. doi:10.1088/0031-9155/55/17/021.
* Golden, Leslie M. The Effect of Surface Roughness on the Transmission of Microwave Radiation Through a Planetary Surface. 伊卡洛斯 (期刊). 1979, **38** (3): 451–455. Bibcode:1979Icar...38..451G. doi:10.1016/0019-1035(79)90199-4.
* Gould, Harvey; Tobochnik, Jan. An Introduction to Computer Simulation Methods, Part 2, Applications to Physical Systems. Reading: Addison-Wesley. 1988. ISBN 0-201-16504-X.
* Grinstead, Charles; Snell, J. Laurie. Introduction to Probability. 美國數學學會. 1997: 10–11.
* Hammersley, J. M.; Handscomb, D. C. Monte Carlo Methods. London: Methuen. 1975. ISBN 0-416-52340-4.
* Hartmann, A.K. Practical Guide to Computer Simulations. World Scientific. 2009 [2018-04-29]. ISBN978-981-283-415-7. （原始內容存檔於 2009-02-11）.
* Hubbard, Douglas. How to Measure Anything: Finding the Value of Intangibles in Business. John Wiley & Sons. 2007: 46.
* Hubbard, Douglas. The Failure of Risk Management: Why It's Broken and How to Fix It. John Wiley & Sons. 2009.
* Kahneman, D.; Tversky, A. Judgement under Uncertainty: Heuristics and Biases. Cambridge University Press. 1982.
* Kalos, Malvin H.; Whitlock, Paula A. Monte Carlo Methods. Wiley-VCH. 2008. ISBN 978-3-527-40760-6.
* Kroese, D. P.; Taimre, T.; Botev, Z.I. Handbook of Monte Carlo Methods. New York: John Wiley & Sons. 2011: 772. ISBN 0-470-17793-4.
* MacGillivray, H. T.; Dodd, R. J. Monte-Carlo simulations of galaxy systems (PDF). Astrophysics and Space Science (施普林格科學 + 商業媒體). 1982, **86** (2).
* MacKeown, P. Kevin. Stochastic Simulation in Physics. New York: Springer. 1997. ISBN 981-3083-26-3.
* Metropolis, N. The beginning of the Monte Carlo method (PDF). Los Alamos Science. 1987, (1987 Special Issue dedicated to Stanislaw Ulam): 125–130.
* Metropolis, Nicholas; Rosenbluth, Arianna W.; Rosenbluth, Marshall N.; Teller, Augusta H.; Teller, Edward. Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics. 1953, **21** (6): 1087. Bibcode:1953JChPh..21.1087M. doi:10.1063/1.1699114.
* Metropolis, N.; Ulam, S. The Monte Carlo Method. Journal of the American Statistical Association (American Statistical Association). 1949, **44** (247): 335–341. JSTOR 2280232. PMID 18139350. doi:10.2307/2280232.
* M. Milik and J. Skolnick. Insertion of peptide chains into lipid membranes: an off-lattice Monte Carlo dynamics model. Proteins. Jan 1993, **15** (1): 10–25. PMID 8451235. doi:10.1002/prot.340150104.
* Mosegaard, Klaus; Tarantola, Albert. Monte Carlo sampling of solutions to inverse problems (PDF). J. Geophys. Res. 1995, **100** (B7): 12431–12447 [2018-04-29]. Bibcode:1995JGR...10012431M. doi:10.1029/94JB03097. （原始內容 (PDF) 存檔於 2021-03-10）.
* P. Ojeda and M. Garcia and A. Londono and N.Y. Chen. Monte Carlo Simulations of Proteins in Cages: Influence of Confinement on the Stability of Intermediate States. Biophys. J. (Biophysical Society). Feb 2009, **96** (3): 1076–1082. Bibcode:2009BpJ....96.1076O. doi:10.1529/biophysj.107.125369.
* Int Panis, L; De Nocker, L; De Vlieger, I; Torfs, R. Trends and uncertainty in air pollution impacts and external costs of Belgian passenger car traffic International. Journal of Vehicle Design. 2001, **27** (1–4): 183–194. doi:10.1504/IJVD.2001.001963.
* Int Panis, L; Rabl, A; De Nocker, L; Torfs, R. P. Sturm , 編. Diesel or Petrol ? An environmental comparison hampered by uncertainty. Mitteilungen Institut für Verbrennungskraftmaschinen und Thermodynamik (Technische Universität Graz Austria). 2002,. Heft 81 Vol 1: 48–54.
* Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. Numerical Recipes in Fortran 77: The Art of Scientific Computing. Fortran Numerical Recipes **1** Second. 劍橋大學出版社. 1996 [1986]. ISBN 0-521-43064-X.
* Ripley, B. D. Stochastic Simulation. 約翰威立. 1987.
* Robert, C. P.; Casella, G. Monte Carlo Statistical Methods 2nd. New York: Springer. 2004. ISBN 0-387-21239-6.
* Rubinstein, R. Y.; Kroese, D. P. Simulation and the Monte Carlo Method 2nd. New York: John Wiley & Sons. 2007. ISBN 978-0-470-17793-8.
* Savvides, Savvakis C. Risk Analysis in Investment Appraisal. Project Appraisal Journal. 1994, **9** (1). doi:10.2139/ssrn.265905.
* Sawilowsky, Shlomo S.; Fahoome, Gail C. Statistics via Monte Carlo Simulation with Fortran. Rochester Hills, MI: JMASM. 2003. ISBN 0-9740236-0-4.
* Sawilowsky, Shlomo S. You think you've got trivials? (PDF). Journal of Modern Applied Statistical Methods. 2003, **2** (1): 218–225.
* Silver, David; Veness, Joel. Monte-Carlo Planning in Large POMDPs (PDF). Lafferty, J.; Williams, C. K. I.; Shawe-Taylor, J.; Zemel, R. S.; Culotta, A. (編). Advances in Neural Information Processing Systems 23. Neural Information Processing Systems Foundation. 2010 [2018-04-29]. （原始內容 (PDF) 存檔於 2012-05-25）.
* Szirmay-Kalos, László. Monte Carlo Methods in Global Illumination - Photo-realistic Rendering with Randomization. VDM Verlag Dr. Mueller e.K. 2008. ISBN 978-3-8364-7919-6.
* Tarantola, Albert. Inverse Problem Theory. Philadelphia: Society for Industrial and Applied Mathematics. 2005 [2018-04-29]. ISBN0-89871-572-5. （原始內容存檔於 2021-02-25）.
* Vose, David. Risk Analysis, A Quantitative Guide Third. John Wiley & Sons. 2008.