蒙特卡罗算法简述

1、蒙特卡罗算法简述摘要：本文介绍了蒙特卡罗算法的起源，原理，描述及应用，列举了一个蒙特卡 罗全局光照算法得实例及研究过程。关键词：蒙特卡罗；全局光照；统计；自适应 一、背景蒙特卡罗算法（Monte Carlo method）,也称统计模拟方法，是二十世纪四 十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。蒙特卡罗方法的名字来源于摩纳哥的一 个城市蒙地卡罗，该城市以赌博业闻名，而蒙特卡罗方法正是以概率为基础的 方法。起源于早期的用几率近似概率的数学思想，它利用随机数进行统计

2、试验， 以求得的统计特征值（如均值、概率等）作为待解问题的数值解。随着现代计算 机技术的飞速发展，蒙特卡罗算法也在不断的改进。1946年，美国拉斯阿莫斯国家实验室的三位科学家 John von Neumann Stan Ulam和Nick Metropolis共同发明，被称为蒙特卡洛方法。体定义是：在广场上 画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形，现在要 计算这个不规则图形的面积，蒙特卡洛（Monte Carlo）方法告诉我们，均匀的向该 正方形内撒N （N是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这 个不规则几何形状内部，比如说有 M个，那么，这个奇怪形积与正

3、方形的面积 之比便近似于M/N , N越大，算出来的值便越精确。在这里我们要假定豆子都 在一个平面上，相互之间没有重叠。蒙特卡洛方法可用于近似计算圆周率：让计算机每次随机生成两个0至M之间的数，看这两个实数是否在单位圆内。生成一 系列随机点，统计单位圆内的点数与总点数，（圆面积和正方形面积之比为 PI:, PI为圆周率），当随机点取得越多（但即使取10的9次方个随机点时，其结果 也仅在前4位与圆周率吻合）时，其结果越接近于圆周率。就数学特性而言，特 卡罗方法的发展可以追溯到 18世纪著名的蒲丰问题。777年，国科学家蒲丰 （Buffon）提出用投针试验计算圆周率 冗值的问题。这里我们用蒲丰问题

4、来初步说 明蒙特卡罗方法的基本原理和解决问题的基本手续，蒲丰问题是这样一个古典概率问题：平面上有彼此相距为 2a的平行线，此平面任意投一长度为 2 l的针， 定然l a,所投的针至多可与一条直线相交，那么，此针与任意条平行线相交 的概率可以求出，由下面的分析可知，此概率与所取针长2 1、平行线间距2 a有 关，并且包含有 冗值。在这里，任投一针的概率含义有以下三点：(1)针的中点Ml在平行线之间等概率落入，即Ml距平行线的距离x均匀 分布在区间0 ,a 之内；(2)针与线的夹角8均匀分布在区间-九Z九2之内；(3) x与8互相独立。在某一条平行线上的x轴，不失一般性，假定针的中心处于图示中的

5、x轴 上。由于对称性，我们只需分析针中心处在x (0 , a)范围的情况即可。令探针中心的坐标值为x,显然，只有x 01可能发生相交的事件。我们来分析在条 件x司满足时，针与线相交的概率：只有当0 0 = arccosxl时才能相交，且相交的概率为 TOC o 1-5 h z P1 =2 兀 arccosxl(1)下面再来分析针中心位置在轴上的分布， 显然，这是一个均匀分布，即针中心处 于区间(x , x + d x)内的概率为d P2 =d xa(2)这样，一次投掷，针中心落入(x , x + d x)且与线相交的概率为d P = P1d P2 =2 兀 aarccosxld x(3)则一次

6、投掷，针与线相交的总概率为P = /d P = 110 兀 aarccosxld x =2 l 兀 a(4)即：兀=2 lPa(5)从上式可见，可利用投针试验计算 冗值：设投针N次，其中n次针与线相 交，则可用频率值n/ N作为卞S率P的估计值，从而求得 冗的估计值为兀=2 laNn(6)这就是早期的用频率值作为概率近似值的方法的应用实例，表1是在历史上一些有名的用投针试验计算 冗值的结果，其中针长以a为单位。需要指出的 是，上述由投针试验求得 冗的近似值的方法，是进行真正的试验，并统计试验结 果，要使获得的频率值与概率值偏差小，就要进行大量的试验，这在实际中，往往难以做到。可以设想，对蒲丰问

7、题这样一个简单的概率问题， 若要进行10万 次投针试验，以每次投针、作出是否相交判断并累加相交次数用时 5秒钟计算， 则需用时50万秒，即大约139个小时。那么，可以设想，对于象上述确定条 件下的核裂变、直流气体放电中粒子的输运过程及粒子输运的总效应，若要用多次掷骰子的方法近似求出就是不可能的了。所以，在现代计算机技术出现之前， 用频率近似概率的方法一一抑或称为雏形时代的蒙卡罗方法一一并没有得到 实质上的应用。若用数值模拟方法代替上述的真正白投针试验，是利用均匀分布于（0, 1）之间的随机数序列，并构造出随机投针的数学模型，然后进行大量的随机统计并求 得冗的近似值。二、蒙特卡罗原理蒙特卡罗方法

8、的基本原理及思想如下：当所要求解的问题是某种事件出现的 概率，或者是某个随机变量的期望值时，它们可以通过某种“试验”的方法，得 到这种事件出现的频率，或者这个随机变数的平均值，并用它们作为问题的解。 这就是蒙特卡罗方法的基本思想。蒙特卡罗方法通过抓住事物运动的几何数量和 几何特征，利用数学方法来加以模拟，即进行一种数字模拟实验。它是以一个概 率模型为基础，按照这个模型所描绘的过程，通过模拟实验的结果，作为问题的 近似解。可以把蒙特卡罗解题归结为三个主要步骤：构造或描述概率过程；实现从已知概率分布抽样；建立各种估计量。蒙特卡罗解题三个主要步骤：构造或描 述概率过程：对于本身就具有随机性质的问题，

9、 如粒子输运问题，主要是正确描 述和模拟这个概率过程，对于本来不是随机性质的确定性问题，比如计算定积分， 就必须事先构造一个人为的概率过程， 它的某些参量正好是所要求问题的解。 即 要将不具有随机性质的问题转化为随机性质的问题。实现从已知概率分布抽样： 构造了概率模型以后，由于各种概率模型都可以看作是由各种各样的概率分布构 成的，因此产生已知概率分布的随机变量（或随机向量），就成为实现蒙特卡罗 方法模拟实验的基本手段，这也是蒙特卡罗方法被称为随机抽样的原因。 最简单、 最基本、最重要的一个概率分布是（0,1）上的均匀分布（或称矩形分布）。随机数 就是具有这种均匀分布的随机变量。随机数序列就是具

10、有这种分布的总体的一个 简单子样，也就是一个具有这种分布的相互独立的随机变数序列。产生随机数的 问题，就是从这个分布的抽样问题。在计算机上，可以用物理方法产生随机数， 但价格昂贵，不能重复，使用不便。另一种方法是用数学递推公式产生。这样产 生的序列，与真正的随机数序列不同，所以称为伪随机数，或伪随机数序列。不 过，经过多种统计检验表明，它与真正的随机数，或随机数序列具有相近的性质， 因此可把它作为真正的随机数来使用。由已知分布随机抽样有各种方法，与从(0,1) 上均匀分布抽样不同，这些方法都是借助于随机序列来实现的， 也就是说，都是 以产生随机数为前提的。由此可见，随机数是我们实现蒙特卡罗模拟

11、的基本工具。 建立各种估计量：一般说来，构造了概率模型并能从中抽样后， 即实现模拟实验 后，我们就要确定一个随机变量，作为所要求的问题的解，我们称它为无偏估计。 建立各种估计量，相当于对模拟实验的结果进行考察和登记，从中得到问题的解。 例如：检验产品的正品率问题，我们可以用 1表示正品，0表示次品，于是对每 个产品检验可以定义如下的随机变数 Ti,作为正品率的估计量：于是，在 N次 实验后，正品个数为：显然，正品率p为：不难看出，Ti为无偏估计。当然，还 可以引入其它类型的估计，如最大似然估计，渐进有偏估计等。但是，在蒙特卡 罗计算中，使用最多的是无偏估计。用比较抽象的概率语言描述蒙特卡罗方法

12、解 题的手续如下：构造一个概率空间(W , A, P),其中，W是一个事件集合，A 是集合W的子集的s体，P是在A上建立的某个概率测度；在这个概率空间中， 选取一个随机变量q (w ) , w ? W,使得这个随机变量的期望值正好是所要求的 解Q ,然后用q (w )的简单子样的算术平均值作为 Q的近似值。蒙特卡罗方法与一般计算方法有很大区别，一般计算方法对于解决多维或因 素复杂的问题非常困难，而蒙特卡罗方法对于解决这方面的问题却比较简单。其特点如下：直接追踪粒子，物理思路清晰，易于理解。采用随机抽样的方法，较 真切的模拟粒子输运的过程，反映了统计涨落的规律。不受系统多维、多因素等 复杂性的限制，是解决复杂系统粒子输运问题的好方法。MC程序结构清晰简单。 研究人员采用MC方法编写程序来解决粒子输运问题，比较容易得到自己想得到 的任意中间结果，应用灵活性强。MC方法主要弱点是收敛速度较慢和误差的概 率性质，其概率误差正比于，如果单纯以增大抽样粒子个数N来减小误差，就要增加很大的计算量。近十年来，蒙特卡罗方法发展很快，从 1983年到1988 年期刊论文数量增长了五倍，有几本好书是关于电子？光子蒙特卡罗问题的，蒙特卡罗方法的代码被