蒙地卡羅方法

2018-12-19 18:55:32
蒙特卡罗方法英语:Monte Carlo method),也称统计模拟方法,是1940年代中期由于科学技术的发展和电子计算机的发明,而提出的一种以概率统计理论为指导的数值计算方法。是指使用随机数(或更常见的伪随机数)来解决很多计算问题的方法。 20世纪40年代,在冯·诺伊曼,斯塔尼斯拉夫·烏拉姆和尼古拉斯·梅特罗波利斯在洛斯阿拉莫斯国家实验室为核武器计划工作时,发明了蒙特卡罗方法。因为烏拉姆的叔叔经常在摩納哥的蒙特卡洛赌场输钱得名,而蒙特卡罗方法正是以概率为基础的方法。 与它对应的是确定性算法。 蒙特卡罗方法在金融工程学、宏观经济学、生物医学、计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)机器学习等领域应用广泛。[1]

目录

  • 1 蒙特卡罗方法的基本思想
  • 2 蒙特卡罗方法的工作过程
  • 3 蒙特卡罗方法分子模拟计算的步骤
  • 4 蒙特卡罗方法在数学中的应用
    • 4.1 积分
    • 4.2 圆周率
  • 5 蒙特卡洛方法在机器学习中的应用
  • 6 注释
  • 7 参考

蒙特卡罗方法的基本思想[编辑]

通常蒙特卡罗方法可以粗略地分成两类:一类是所求解的问题本身具有内在的随机性,借助计算机的运算能力可以直接模拟这种随机的过程。例如在核物理研究中,分析中子在反应堆中的传输过程。中子与原子核作用受到量子力学规律的制约,人们只能知道它们相互作用发生的概率,却无法准确获得中子与原子核作用时的位置以及裂变产生的新中子的行进速率和方向。科学家依据其概率进行随机抽样得到裂变位置、速度和方向,这样模拟大量中子的行为后,经过统计就能获得中子传输的范围,作为反应堆设计的依据。
另一种类型是所求解问题可以转化为某种随机分布的特征数,比如随机事件出现的概率,或者随机变量的期望值。通过随机抽样的方法,以随机事件出现的频率估计其概率,或者以抽样的数字特征估算随机变量的数字特征,并将其作为问题的解。这种方法多用于求解复杂的多维积分问题。
假设我们要计算一个不规则图形的面积,那么图形的不规则程度和分析性计算(比如,积分)的复杂程度是成正比的。蒙特卡罗方法基于这样的思想:假想你有一袋豆子,把豆子均匀地朝这个图形上撒,然后数这个图形之中有多少颗豆子,这个豆子的数目就是图形的面积。当你的豆子越小,撒的越多的时候,结果就越精确。借助计算机程序可以生成大量均匀分布坐标点,然后统计出图形内的点数,通过它们占总点数的比例和坐标点生成范围的面积就可以求出图形面积。

蒙特卡罗方法的工作过程[编辑]

使用蒙特卡罗方法估算π值. 放置30000个随机点后,π的估算值与真实值相差0.07%.
在解决实际问题的时候应用蒙特卡罗方法主要有两部分工作:
  1. 用蒙特卡罗方法模拟某一过程时,需要产生各种概率分布的随机变量。
  2. 用统计方法把模型的数字特征估计出来,从而得到实际问题的数值解。

蒙特卡罗方法分子模拟计算的步骤[编辑]

使用蒙特卡罗方法进行分子模拟计算是按照以下步骤进行的:
  1. 使用随机数生成器产生一个随机的分子构型。
  2. 对此分子构型的其中粒子坐标做无规则的改变,产生一个新的分子构型。
  3. 计算新的分子构型的能量。
  4. 比较新的分子构型与改变前的分子构型的能量变化,判断是否接受该构型。
    • 若新的分子构型能量低于原分子构型的能量,则接受新的构型,使用这个构型重复再做下一次迭代。
    • 若新的分子构型能量高于原分子构型的能量,则計算玻尔兹曼因子,并产生一个随机数。
      • 若这个随机数大于所计算出的玻尔兹曼因子,则放弃这个构型,重新计算。
      • 若这个随机数小于所计算出的玻尔兹曼因子,则接受这个构型,使用这个构型重复再做下一次迭代。
  5. 如此进行迭代计算,直至最后搜索出低于所给能量条件的分子构型结束。

蒙特卡罗方法在数学中的应用[编辑]

通常蒙特卡罗方法通过构造符合一定规则的随机数来解决数学上的各种问题。对于那些由于计算过于复杂而难以得到解析解或者根本没有解析解的问题,蒙特卡罗方法是一种有效的求出数值解的方法。一般蒙特卡罗方法在数学中最常见的应用就是蒙特卡罗积分。下面是蒙特卡罗方法的两个简单应用:

积分[编辑]

非权重蒙特卡罗积分,也称确定性抽样,是对被积函数变量区间进行随机均匀抽样,然后对抽样点的函数值求平均,从而可以得到函数积分的近似值。此种方法的正确性是基于概率论的中心极限定理。当抽样点数为m时,使用此种方法所得近似解的统计误差只与m有关(与正相关),不随积分维数的改变而改变。因此当积分维度较高时,蒙特卡罗方法相对于其他数值解法更优。

圆周率[编辑]

蒙特卡罗方法可用于近似计算圆周率:让计算机每次随机生成两个0到1之间的数,看以这两个实数为横纵坐标的点是否在单位圆内。生成一系列随机点,统计单位圆内的点数与总点数,(圓面積和正方形面積之比為PI:4,PI為圓周率),当随机点取得越多时,其结果越接近于圆周率(然而準確度仍有爭議:即使取10的9次方个随机点时,其结果也仅在前4位与圆周率吻合)。用蒙特卡罗方法近似计算圆周率的先天不足是:第一,计算机产生的随机数是受到存储格式的限制的,是离散的,并不能产生连续的任意实数;上述做法将平面分割成一个个网格,在空间也不是连续的,由此计算出来的面积当然与圆或多或少有差距。

蒙特卡洛方法在机器学习中的应用[编辑]

蒙特卡洛算法也常用于机器学习,特别是强化学习的算法中。一般情况下,针对得到的样本数据集建立相对模糊的模型,通过蒙特卡洛方法对于模型中的参数进行选取,使之于原始数据的残差尽可能的小。从而达到建立模型拟合样本的目的。

注释[编辑]

  1. ^ Kroese, D. P.; Brereton, T.; Taimre, T.; Botev, Z. I. Why the Monte Carlo method is so important today. WIREs Comput Stat. 2014, 6: 386–392. doi:10.1002/wics.1314. 

参考[编辑]

  • Anderson, Herbert L. Metropolis, Monte Carlo and the MANIAC (PDF). Los Alamos Science. 1986, 14: 96–108. 
  • 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. doi:10.1515/mcma-2016-0102. 
  • 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. 
  • 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. ISBN 978-981-283-415-7. 
  • 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. Bibcode:1995JGR...10012431M. doi:10.1029/94JB03097. 
  • 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. 
  • 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. ISBN 0-89871-572-5. 
  • Vose, David. Risk Analysis, A Quantitative Guide Third. John Wiley & Sons. 2008. 

上一篇: Production I.G
下一篇: Studio Ponoc