蒙特卡罗算法简述

蒙特卡罗算法简述摘要：本文介绍了蒙特卡罗算法的起源，原理，描述及应用，列举了一个蒙特卡罗全局光照算法得实例及研究过程。关键词：蒙特卡罗；全局光照；统计；自适应一、背景蒙特·卡罗算法（MonteCarlomethod），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。蒙特·卡罗方法的名字来源于摩纳哥的一个城市蒙地卡罗，该城市以赌博业闻名，而蒙特·卡罗方法正是以概率为基础的方法。起源于早期的用几率近似概率的数学思想，它利用随机数进行统计试验，以求得的统计特征值(如均值、概率等)作为待解问题的数值解。随着现代计算机技术的飞速发展，蒙特·卡罗算法也在不断的改进。1946年，美国拉斯阿莫斯国家实验室的三位科学家JohnvonNeumann，StanUlam和NickMetropolis共同发明，被称为蒙特卡洛方法。体定义是：在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形，现在要计算这个不规则图形的面积，蒙特卡洛(MonteCarlo)方法告诉我们，均匀的向该正方形内撒N（N是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个，那么，这个奇怪形积与正方形的面积之比便近似于M/N，N越大，算出来的值便越精确。在这里我们要假定豆子都在一个平面上，相互之间没有重叠。蒙特卡洛方法可用于近似计算圆周率：让计算机每次随机生成两个0到1之间的数，看这两个实数是否在单位圆内。生成一系列随机点，统计单位圆内的点数与总点数，（圆面积和正方形面积之比为PI：，PI为圆周率），当随机点取得越多（但即使取10的9次方个随机点时，其结果也仅在前4位与圆周率吻合）时，其结果越接近于圆周率。就数学特性而言，特卡罗方法的发展可以追溯到18世纪著名的蒲丰问题。777年，国科学家蒲丰(Buffon)提出用投针试验计算圆周率π值的问题。这里我们用蒲丰问题来初步说明蒙特卡罗方法的基本原理和解决问题的基本手续，蒲丰问题是这样一个古典概率问题：平面上有彼此相距为2a的平行线，此平面任意投一长度为2l的针，定然la，所投的针至多可与一条直线相交，那么，此针与任意条平行线相交的概率可以求出，由下面的分析可知，此概率与所取针长2l、平行线间距2a有关，并且包含有π值。在这里，任投一针的概率含义有以下三点：(1)针的中点Ml在平行线之间等概率落入，即Ml距平行线的距离x均匀分布在区间[0,a]之内；(2)针与线的夹角θ均匀分布在区间-π2，π2之内；(3)x与θ互相独立。在某一条平行线上的x轴，不失一般性，假定针的中心处于图示中的x轴上。由于对称性，我们只需分析针中心处在x∈(0,a)范围的情况即可。令探针中心的坐标值为x，显然，只有x≤1可能发生相交的事件。我们来分析在条件x≤1满足时，针与线相交的概率：只有当θ≤0=arccosxl时才能相交，且相交的概率为P1=2πarccosxl(1)下面再来分析针中心位置在轴上的分布，显然，这是一个均匀分布，即针中心处于区间(x,x+dx)内的概率为dP2=dxa(2)这样，一次投掷，针中心落入(x,x+dx)且与线相交的概率为dP=P1dP2=2πaarccosxldx(3)则一次投掷，针与线相交的总概率为P=∫dP=∫l0πaarccosxldx=2lπa(4)即：π=2lPa（5）从上式可见，可利用投针试验计算π值：设投针N次，其中n次针与线相交，则可用频率值n/N作为概率P的估计值，从而求得π的估计值为π≈2laNn(6)这就是早期的用频率值作为概率近似值的方法的应用实例，表1是在历史上一些有名的用投针试验计算π值的结果，其中针长以a为单位。需要指出的是，上述由投针试验求得π的近似值的方法，是进行真正的试验，并统计试验结果，要使获得的频率值与概率值偏差小，就要进行大量的试验，这在实际中，往往难以做到。可以设想，对蒲丰问题这样一个简单的概率问题，若要进行10万次投针试验，以每次投针、作出是否相交判断并累加相交次数用时5秒钟计算，则需用时50万秒，即大约139个小时。那么，可以设想，对于象上述确定条件下的核裂变、直流气体放电中粒子的输运过程及粒子输运的总效应，若要用多次掷骰子的方法近似求出就是不可能的了。所以，在现代计算机技术出现之前，用频率近似概率的方法——抑或称为雏形时代的蒙卡罗方法——并没有得到实质上的应用。若用数值模拟方法代替上述的真正的投针试验，是利用均匀分布于(0，1)之间的随机数序列，并构造出随机投针的数学模型，然后进行大量的随机统计并求得π的近似值。二、蒙特卡罗原理蒙特卡罗方法的基本原理及思想如下：当所要求解的问题是某种事件出现的概率，或者是某个随机变量的期望值时，它们可以通过某种“试验”的方法，得到这种事件出现的频率，或者这个随机变数的平均值，并用它们作为问题的解。这就是蒙特卡罗方法的基本思想。蒙特卡罗方法通过抓住事物运动的几何数量和几何特征，利用数学方法来加以模拟，即进行一种数字模拟实验。它是以一个概率模型为基础，按照这个模型所描绘的过程，通过模拟实验的结果，作为问题的近似解。可以把蒙特卡罗解题归结为三个主要步骤：构造或描述概率过程；实现从已知概率分布抽样；建立各种估计量。蒙特卡罗解题三个主要步骤：构造或描述概率过程：对于本身就具有随机性质的问题，如粒子输运问题，主要是正确描述和模拟这个概率过程，对于本来不是随机性质的确定性问题，比如计算定积分，就必须事先构造一个人为的概率过程，它的某些参量正好是所要求问题的解。即要将不具有随机性质的问题转化为随机性质的问题。实现从已知概率分布抽样：构造了概率模型以后，由于各种概率模型都可以看作是由各种各样的概率分布构成的，因此产生已知概率分布的随机变量（或随机向量），就成为实现蒙特卡罗方法模拟实验的基本手段，这也是蒙特卡罗方法被称为随机抽样的原因。最简单、最基本、最重要的一个概率分布是(0,1)上的均匀分布（或称矩形分布）。随机数就是具有这种均匀分布的随机变量。随机数序列就是具有这种分布的总体的一个简单子样，也就是一个具有这种分布的相互独立的随机变数序列。产生随机数的问题，就是从这个分布的抽样问题。在计算机上，可以用物理方法产生随机数，但价格昂贵，不能重复，使用不便。另一种方法是用数学递推公式产生。这样产生的序列，与真正的随机数序列不同，所以称为伪随机数，或伪随机数序列。不过，经过多种统计检验表明，它与真正的随机数，或随机数序列具有相近的性质，因此可把它作为真正的随机数来使用。由已知分布随机抽样有各种方法，与从(0,1)上均匀分布抽样不同，这些方法都是借助于随机序列来实现的，也就是说，都是以产生随机数为前提的。由此可见，随机数是我们实现蒙特卡罗模拟的基本工具。建立各种估计量：一般说来，构造了概率模型并能从中抽样后，即实现模拟实验后，我们就要确定一个随机变量，作为所要求的问题的解，我们称它为无偏估计。建立各种估计量，相当于对模拟实验的结果进行考察和登记，从中得到问题的解。例如：检验产品的正品率问题，我们可以用1表示正品，0表示次品，于是对每个产品检验可以定义如下的随机变数Ti，作为正品率的估计量：于是，在N次实验后，正品个数为：显然，正品率p为：不难看出，Ti为无偏估计。当然，还可以引入其它类型的估计，如最大似然估计，渐进有偏估计等。但是，在蒙特卡罗计算中，使用最多的是无偏估计。用比较抽象的概率语言描述蒙特卡罗方法解题的手续如下：构造一个概率空间(W，A，P)，其中，W是一个事件集合，A是集合W的子集的s体，P是在A上建立的某个概率测度；在这个概率空间中，选取一个随机变量q(w)，wÎW，使得这个随机变量的期望值正好是所要求的解Q，然后用q(w)的简单子样的算术平均值作为Q的近似值。蒙特卡罗方法与一般计算方法有很大区别，一般计算方法对于解决多维或因素复杂的问题非常困难，而蒙特卡罗方法对于解决这方面的问题却比较简单。其特点如下：直接追踪粒子，物理思路清晰，易于理解。采用随机抽样的方法，较真切的模拟粒子输运的过程，反映了统计涨落的规律。不受系统多维、多因素等复杂性的限制，是解决复杂系统粒子输运问题的好方法。MC程序结构清晰简单。研究人员采用MC方法编写程序来解决粒子输运问题，比较容易得到自己想得到的任意中间结果，应用灵活性强。MC方法主要弱点是收敛速度较慢和误差的概率性质，其概率误差正比于，如果单纯以增大抽样粒子个数N来减小误差，就要增加很大的计算量。近十年来，蒙特卡罗方法发展很快，从1983年到1988年期刊论文数量增长了五倍，有几本好书是关于电子¾光子蒙特卡罗问题的，蒙特卡罗方法的代码被认为是黑匣子，它已成为计算数学中不可缺少的组成部分，这主要是因为以下原因：·传统的分析方法受到了问题复杂性的限制。·MC方法直观，对实验者很有吸引力。·计算机变得更快更便宜。·量子理论的发展为我们提供了辐射与物质相互作用的截面数据。三、总结实验结果表明，用本文方法生成的图像在RMS的减小上有很大的提高，生成的图像的效果好于香农信息熵的和其他一些经典方法的效果。本文方法实现简单，对复杂场景的适用性同样很强。