什么是蒙特卡罗模拟 | 集智百科
本词条由集智俱乐部众包生产,难免存在纰漏和问题,欢迎大家留言反馈或者前往对应的百科词条页面进行修改,一经修改,可以获得对应的积分奖励噢!
目录
蒙特卡罗方法 Monte Carlo methods,或称蒙特卡罗实验 Monte Carlo experiments,是一大类计算算法的集合,依靠重复的随机抽样来获得数值结果。基本概念是利用随机性来解决理论上可能是确定性的问题。这类方法通常用于解决物理和数学问题,当面对棘手问题而束手无策时,往往它们可以大显身手。蒙特卡罗方法主要用于解决3类问题:最优化,数值积分,依据概率分布生成图像。
在物理学相关问题中,蒙特卡罗方法可用于模拟具有多个耦合自由度的系统,如流体、无序材料、强耦合固体和细胞结构(参见细胞波茨模型 Cellular Potts Model、相互作用粒子系统 Interacting Particle Systems、麦肯-弗拉索夫过程 McKean-Vlasov Processes、气体动力学模型 Kinetic Models of Gases)。
其他例子包括:对输入中具有重大不确定性的现象进行建模,如商业中的风险计算,以及在数学中对具有复杂边界条件的多维定积分进行评估。在系统工程问题(空间、石油勘探、飞机设计等)的应用中,基于蒙特卡罗的故障预测、成本超支和进度超支通常比人类的直觉或其他的“软性”方法更有效。
理论上,蒙特卡罗方法可以用来解决任何具有概率解释的问题。根据大数定律 Law of Large Numbers,用某个随机变量的期望值描述的积分可以用该变量独立样本的经验均值(即样本均值)来近似。当变量的概率分布被参数化时,数学家们经常使用马尔可夫链蒙特卡罗 Markov chain Monte Carlo(MCMC)采样器。其中心思想是设计一个具有给定稳态概率分布 Stationary Probability Distribution的有效马尔可夫链模型。也就是说,在极限情况下,马尔科夫链蒙特卡洛方法生成的样本将成为来自期望(目标)分布的样本。通过遍历定理 Ergodic Theorem,稳态分布可以用马尔科夫链蒙特卡洛采样器随机状态的经验测度来近似。
在其他问题中,要实现的目标则是从满足非线性演化方程的概率分布序列中生成图像。这些概率分布流总是可以解释为马尔可夫过程 Markov process的随机状态的分布,其转移概率依赖于当前随机状态的分布(见麦肯-弗拉索夫过程,非线性滤波方程 Nonlinear Filtering Equation)。其他情况下,我们给出了采样复杂度不断增加的概率分布流(如时间范围不断增加的路径空间模型,与温度参数降低有联系的玻尔兹曼—吉布斯测度 Boltzmann-Gibbs Measures,以及许多其他例子)。这些模型也可以看作是一个非线性马尔可夫链的随机状态规律的演化。模拟这些复杂非线性马尔可夫过程的一个自然的方法是对过程的多个副本进行抽样,用抽样的经验测度替代演化方程中未知的随机状态分布。与传统的蒙特卡罗和马尔科夫链蒙特卡洛方法相比,这些平均场粒子 Mean Field Particle技术依赖于连续相互作用的样本。平均场一词反映了每个样本(也就是粒子、个体、步行者、媒介、生物或表现型)与过程的经验测量相互作用的事实。当系统大小趋近于无穷时,这些随机经验测度收敛于非线性马尔可夫链随机状态的确定性分布,从而使粒子之间的统计相互作用消失。
尽管其概念和算法简单,但与蒙特卡罗模拟相关的计算成本却是高的惊人。一般情况下,该方法需要大量的样本来获得良好的近似,如果单个样本的处理时间较长,可能会导致总运行时间长度难以控制。尽管在非常复杂的问题中,这是一个严重的限制,但该算法令人尴尬的并行性质允许通过本地处理器、集群、云计算、GPU、FPGA等的并行计算策略来降低高昂的成本(或许降低到可以接受的水平上)。
概述
蒙特卡罗方法各不相同,但趋于遵循一个特定的模式:
1、定义可能输入的域
2、从域上的概率分布随机生成输入
3、对输入进行确定性计算
4、汇总结果
蒙特卡罗方法应用于估计π值。
例如,考虑一个单位正方形内嵌的四分之一圆。考虑到它们的面积比是π/4,π的值可以用蒙特卡罗方法来近似:
1、画一个正方形,然后在其中划出一个四分之一圆
2、在正方形上均匀散布给定数量的点
3、计算四分之一圆内的点数,即满足距离原点小于1的
4、四分之一圆内部计数与总样本计数之比是两个区域之比的估计值,π/4。把结果乘以4就可以估算出π的值。
在这个过程中,输入域是限定四分之一圆的正方形。我们通过将颗粒散射到正方形上来产生随机输入,然后对每个输入执行计算(测试它是否在四分之一圆内)。汇总这些结果会产生最终的结果——π的近似值。
有两个重要的考虑因素:
1、如果这些点不是均匀分布的,那么近似效果就会很差。
2、这一过程需要很多点。如果整个正方形中只有几个点是随机放置的,那么这个近似值通常是很差的。平均而言,随着放置更多的点,近似值精度会提升。
应用蒙特卡罗方法需要大量的随机数,这也就刺激了伪随机数生成器 Pseudorandom Number Generators的发展,伪随机数生成器比以前用于统计抽样的随机数表要快得多。
历史
在开发蒙特卡罗方法之前,人们模拟测试一个已经解决的确定性问题,通过统计抽样估计模拟中的不确定性。蒙特卡罗模拟将这种方法反转,使用概率元启发式方法Probabilistic Metaheuristics解决确定性问题(参见模拟退火法 Simulated Annealing)。
蒙特卡罗方法的早期变种被设计来解决 布丰投针 Buffon’s Needle Problem问题,在布丰投针问题中,π可以通过将针落在由平行等距条组成的地板上来估计。20世纪30年代,恩里科·费米 Enrico Fermi在研究中子扩散时首次尝试了蒙特卡罗方法,但他没有发表这项工作。
20世纪40年代末,斯坦尼斯拉夫·乌拉姆 Stanislaw Ulam在洛斯阿拉莫斯国家实验室研究核武器项目时,发明了现代版的马尔可夫链蒙特卡罗方法。在乌拉姆的突破之后,约翰·冯·诺伊曼 John von Neumann立即意识到了它的重要性。冯·诺伊曼为ENIAC(人类第一台电子数字积分计算机)编写了程序来进行蒙特卡罗计算。1946年,洛斯阿拉莫斯的核武器物理学家正在研究中子在可裂变材料中的扩散。尽管拥有大部分必要的数据,例如中子在与原子核碰撞之前在物质中的平均运行距离,以及碰撞后中子可能释放出多少能量,但洛斯阿拉莫斯的物理学家们无法用传统的、确定性的数学方法解决这个问题。此时乌拉姆建议使用随机实验。他后来回忆当初灵感产生过程:
我最初构想和尝试蒙特卡洛法是在1946年,当时我正从疾病中康复,时常玩单人纸牌游戏。那时我会思考这样一个问题:一盘52张的加菲尔德纸牌成功出牌的几率有多大?在花了大量时间尝试通过纯粹的组合计算来估计它们之后,我想知道是否有一种比“抽象思维”更实际的方法,可能不是将它展开100次,然后简单地观察和计算成功的游戏数量。在快速计算机新时代开始时,这已经是可以想象的了,我立刻想到了中子扩散和其他数学物理的问题,以及更一般的情形—如何将由某些微分方程描述的过程转换成可解释为一系列随机操作的等价形式。后来(1946年),我向约翰·冯·诺伊曼描述了这个想法,然后我们开始计划实际的计算。
冯·诺依曼和乌拉姆的工作是秘密进行的,需要一个代号。冯·诺依曼和乌拉姆的一位同事,尼古拉斯·梅特罗波利斯 Nicholas Metropolis建议使用蒙特卡洛这个名字,这个名字指的是摩纳哥的蒙特卡洛赌场,乌拉姆的叔叔会和亲戚借钱然后去那里赌博。使用“真正随机”的随机数列表是非常慢的,然而冯·诺依曼使用平方取中法 Middle-Square Method开发了一种计算伪随机数生成器的方法。虽然许多人一直批评这种方法较为粗糙原始,但是冯·诺依曼也意识到这一点:他证明这种方法比任何其他方法都快,并指出当它出错时,人们可以轻易发现,不像其他方法产生的错误可能会不易察觉。
尽管受到当时的计算工具严重限制,蒙特卡洛方法依然是曼哈顿计划 Manhattan Project所需模拟的核心关键。20世纪50年代,它们在洛斯阿拉莫斯用于与氢弹开发有关的早期工作,并在物理学、物理化学和运筹学领域得到普及。兰德公司 Rand Corporation和美国空军是当时负责资助和宣传蒙特卡罗方法信息的两个主要组织,从那时起他们开始在许多不同的领域广泛地应用这一方法。
更复杂的平均场型粒子蒙特卡罗方法的理论产生于20世纪60年代中期,最初来自于小亨利·麦基恩 Henry P. McKean Jr.研究流体力学中出现的一类非线性抛物型偏微分方程的马尔可夫解释。西奥多·爱德华·哈里斯 Theodore E. Harris和赫曼·卡恩 Herman Kahn在1951年发表了一篇开创性文章,使用平均场遗传型蒙特卡罗方法来估计粒子传输能量。这一方法在演化计算中也被用作启发式自然搜索算法(又称元启发式)。这些平均场计算技术的起源可以追溯到1950年和1954年,当时阿兰·图灵 Alan Turing在基因类型突变-选择学习机器上的工作,以及来自新泽西州普林斯顿高等研究院的尼尔斯·阿尔·巴里里利 Nils Aall Barricelli的文章。
量子蒙特卡罗方法,更具体地说,扩散蒙特卡罗方法也可以解释为费曼-卡茨路径积分 Feynman–Kac Path Integrals的平均场粒子蒙特卡罗近似。量子蒙特卡罗方法的起源通常归功于恩里科·费米 Enrico Fermi和罗伯特·里希特迈耶 Robert Richtmyer于1948年开发了中子链式反应的平均场粒子解释,但是用于估计量子系统的基态能量(在简化矩阵模型中)的第一个类启发式和遗传型粒子算法(也称为重取样或重构蒙特卡洛方法)则是由杰克·H·海瑟林顿在1984年提出。在分子化学中,使用遗传类启发式的粒子方法(又名删减和富集策略)可以追溯到1955年——马歇尔·罗森布鲁斯 Marshall Rosenbluth和阿里安娜·罗森布鲁斯Arianna Rosenbluth的开创性工作。
在高级信号处理和贝叶斯推断 Bayesian Inference中使用序列蒙特卡罗方法 Sequential Monte Carlo是最近才出现的。1993年,高登等人在他们的开创性工作中发表了蒙特卡罗重采样算法在贝叶斯推论统计学中的首次应用。[36]作者将他们的算法命名为“自举过滤器”,并证明了与其他过滤方法相比,他们的自举过滤算法不需要任何关于系统状态空间或噪声的假设。此外北川源四郎也进行了“蒙特卡洛过滤器”相关的开创性研究。在1990年代中期,皮埃尔·德尔·莫勒尔 Pierre Del Moral和希米尔康·卡瓦略 Himilcon Carvalho以及皮埃尔·德尔·莫勒尔、安德烈·莫宁 André Monin和杰拉德·萨鲁特 Gérard Salut 发表了关于粒子过滤器的文章。1989-1992年间,在LAAS-CNRS(系统分析和体系结构实验室),皮埃尔·德尔·莫勒尔、J·C·诺亚 J. C. Noyer、G·里加尔 G. Rigal和杰拉德·萨鲁特开发了粒子滤波器用于信号处理。他们与STCAN(海军建造和武装服务技术部)、IT公司DIGILOG共同完成了一系列关于雷达/声纳和GPS信号处理问题的限制性和机密性研究报告。这些序列蒙特卡罗方法可以解释为一个接受拒绝采样器配备了相互作用的回收机制。
从1950年到1996年,所有关于顺序蒙特卡罗方法的出版物,包括计算物理和分子化学中引入的删减和重采样蒙特卡罗方法,目前应用于不同的情况的自然和类启发式算法,没有任何一致性证明,也没有讨论估计的偏差和基于谱系和遗传树的算法。皮埃尔·德尔·莫勒尔在1996年的写作中阐述了关于这些粒子算法的数学基础,并对其第一次进行了严格的分析。
20世纪90年代末,丹·克里桑 Dan Crisan、杰西卡·盖恩斯 Jessica Gaines和特里·利昂斯 Terry Lyons,以及丹·克里桑、皮埃尔·德尔·莫勒尔和特里·利昂斯也发展了具有不同种群大小的分支型粒子方法。2000年,皮埃尔·德尔·莫勒尔、爱丽丝·吉奥内 A. Guionnet和洛朗·米克洛 L. Miclo进一步发展了这一领域。
定义
对于如何定义蒙特卡洛还没有达成共识。例如,里普利 Ripley将大多数概率建模定义为随机模拟 stochastic simulation,蒙特卡罗则包含蒙特卡罗积分和蒙特卡罗统计检验。萨维罗斯基 Sawilowsky区分了模拟、蒙特卡罗方法和蒙特卡罗模拟:模拟是对现实的一种虚构的表现,蒙特卡罗方法是一种可以用来解决数学或统计问题的技术,蒙特卡罗模拟使用重复抽样来获得某些现象(或行为)的统计特性。例如:
-
模拟:从区间[0,1]中绘制一个伪随机均匀变量可以用来模拟抛硬币:如果值小于或等于0.50,则结果为正面,但如果值大于0.50,则结果为反面。这是一个模拟,但不是蒙特卡洛模拟。
-
蒙特卡洛方法:将一盒硬币倒在桌子上,然后计算正面与反面落地的硬币比例。这是一种确定重复掷硬币行为的蒙特卡洛方法,但它不是模拟。
-
蒙特卡罗模拟法:一次或多次从区间[0,1]中绘制“大量”伪随机均匀变量,赋值小于或等于0.50作为正面,大于0.50为反面。这是一个多次掷硬币的“蒙特卡罗模拟”行为。
-
(伪随机数)生成器具有某些特征(例如,序列重复之前有一个很长的“周期”)
-
(伪随机数)生成器可以产生能通过随机性测试的值
-
有足够的样本来确保准确的结果
-
使用适当的取样方法
-
使用的算法对建模内容是有效的
-
它可以对问题中的现象进行模拟
蒙特卡罗模拟与“假设”情景
应用
物理科学
工程学
-
在微电子工程 Microelectronics Engineering中,蒙特卡罗方法被用于分析模拟和数字集成电路中相关和不相关的变化。
-
在地质统计学 Geostatistics和地质冶金学 Geometallurgy中,蒙特卡罗方法是矿物处理流程设计的基础,并有助于定量风险分析。
-
在风能产量分析中,考虑不同的不确定性(P90、P50等),计算风电场在其生命周期内的预测发电量。
-
模拟了污染产生的影响,并将柴油和汽油进行了比较。
-
在流体动力学,特别是稀薄气体动力学 Rarefied Gas Dynamics中,采用直接模拟蒙特卡罗方法 Direct Simulation Monte Carlo结合高效计算算法求解有限努森数 Knudsen Number流体的玻尔兹曼方程。
-
在自主机器人中,蒙特卡洛定位 Monte Carlo Localization可以确定机器人的位置。它通常应用于随机滤波器,如卡尔曼滤波器 Kalman Filter或粒子滤波器 Particle Filter,构成同步定位和映射算法 Simultaneous Localization and Mapping(SLAM)的核心。
-
在电信行业,在规划无线网络时,必须证明设计适用于各种不同用户数量、用户位置和他们想使用的服务的场景。蒙特卡罗方法通常用于生成这些用户及其状态。然后对网络性能进行评估,如果结果不能令人满意,则进行网络设计优化。
-
在可靠性工程中,给定部件级响应,蒙特卡罗仿真用来计算系统级响应。例如,对于一个受地震事件影响的交通网络,给定其组件,如桥梁、道路等的失效概率,蒙特卡洛模拟可以用来评估网络的k-终端可靠性。另一个意义深远的例子是应用蒙特卡罗方法求解广义更新过程 Generalized Renewal Process的G-更新方程。
-
在信号处理和贝叶斯推断中,粒子滤波器和序列蒙特卡罗技术是一类平均场粒子方法,用于对给定噪声和局部观测的信号过程进行采样和计算后验分布,使用相互作用的经验测度。
-
在地下水模拟中,利用蒙特卡罗方法产生了大量的非均质参数场实现,用于模型不确定性量化或参数反演。
C气候变化与辐射强迫
计算生物学
计算机图形学
应用统计学
人工智能在游戏中的应用
设计与视觉效果
金融与商业
法律
数学应用
积分
模拟与优化
逆问题
哲学
编者推荐
集智文章推荐
课程推荐
-
揭秘AlphaGo:深度强化学习与蒙特卡洛搜索
https://campus.swarma.org/course/177
-
蒙特卡罗方法
文章推荐
-
蒙特卡罗方法
百科项目志愿者招募
在这里从复杂性知识出发与伙伴同行,同时我们希望有更多志愿者加入这个团队,使百科词条内容得到扩充,并为每位志愿者提供相应奖励与资源,建立个人主页与贡献记录,使其能够继续探索复杂世界。
如果你有意参与更加系统精细的分工,扫描二维码填写报名表,我们期待你的加入!
来源:集智百科
编辑:王建萍
-
什么是有效场论 | 集智百科 -
什么是图灵机 | 集智百科 -
什么是薛定谔的猫 | 集智百科 -
什么是自组织临界控制 | 集智百科 -
《张江·复杂科学前沿27讲》完整上线! -
成为集智VIP,解锁全站课程/读书会
点击“阅读原文”,阅读词条蒙特卡罗模拟原文与参考文献