蒙特卡罗法在计算机仿真中的应用研究.doc

本科毕业论文（设计、创作）题目： 蒙特卡罗法在计算机仿真中的应用研究 学生姓名： 学号： 0321002020 所在院系：信息与通信技术系专业：电子信息工程 入学时间： 2010 年 9 月导师姓名： 傅有亮/朱亮 职称/学位： 副教授/硕士/讲师/硕士 导师所在单位： 完成时间： 2014 年 5 月安徽三联学院教务处 制 安徽三联学院本科毕业论文蒙特卡罗法在计算机仿真中的应用研究摘要: 在运用蒙特卡罗法计算求解问题的过程中会遇到一系列的问题：比如如何构造或描述概率过程、并且如何从已知概率分布抽样和建立估计量。其中，构造或描述概率过程实际上就是建立随机试验模型，构造概率过程是对确定性的问题而言的，描述概率过程是对随机性的问题而言的，不同的问题所需要建立的随机试验模型各不相同。此问题将是本论文的重点之所在。所谓的从已知概率分布抽样指的是随机试验过程，随机模拟中必要包含某些已知概率分布的随机变量或随机过程作为输入，进行随机试验过程就是对随机变量的样本或随机过程的样本函数作为输入相应的输出过程，因此通常被称之为对已知概率分布的抽样。如何产生已知分布的随机变量或随机过程是蒙特卡罗法中的一个关键问题，亦是本论文的关键。总之，本论文所要阐述的主要问题包括如何产生随机数，如何描述概率过程以及如何使用计算机C语言程序来对蒙特卡罗法进行仿真。关键词：蒙特卡罗法； 仿真； 概率； 随机数； 定积分 The Research of the Monte carlo method in the application of computer simulation Abstract: Process calculation problem in using the Monte Carlo method will encounter a series of problems: such as how to structure or a probabilistic description of process, and from the known probability distribution of sampling and estimation. Among them, structure or describing the probability is actually a process of a random test model, construct probabilistic process is to the deterministic problem,describing the probability of random process is the problem in terms of the model of random test, different problems need to establish each are not identical. This problem will be the key point of the paper. The so-called from the known probability distribution of sample is a random process, the necessary simulation contains some known probability distribution of random variables or random process as input, the sample function of the random testing is the process of the samples of random variables or random process as the input and output process, it is often referred to as the known probability the sampling distribution. How to produce a known distribution of the random variables or random process is a key problem of Monte Carlo method, also is the key of this paper. Always, the main issues in this paper to set including how to generate random numbers, how to describe the probability process and how to use the computer Clanguage program to simulate the Monte Carlo method.Keywords:Monte Carlo method； simulation； probability ；random number； definite integral1 目录第一章 绪 论11.1 研究背景11.2 研究现状分析11.3 研究思路和方法2第二章 计算机仿真32.1 计算机仿真技术的概述32.2 计算机仿真技术的发展32.3 计算机仿真技术的发展现状及前景3第三章 定积分及其应用63.1 定积分的概念63.2 定积分的基本计算方法6第四章 蒙特卡罗法104.1 蒙特卡罗法的来源和概述104.2 概率模型和蒙特卡罗法114.3 基于蒙特卡罗法的定积分计算13结语15致谢16参考文献17 第一章 绪 论1.1 研究背景蒙特卡罗方法在科学上又称统计模拟法、随机抽样技术，是随机模拟方法的一种，它的理论基础是以概率论和统计理论方法为前提的，或者说是通过使用随机数来对一些问题进行求解。这就要求将所求解的问题与一定的概率模型相联系起来，再通过利用电子计算机对试验过程进行统计、模拟或抽样，从而得到问题的近似解。因此，科学上为了突出这一方法的概率统计特征，从而借用赌城蒙特卡罗命名。提出：蒙特卡罗方法的提出是在第二次世界大战时期。当时由美国科学家研制原子弹的“曼哈顿计划”计划的成员S.M.乌拉姆和J.冯诺伊率先提出的。数学家冯诺伊曼用摩洛哥赌城蒙特卡罗来命名这种方法，给该方法蒙上了一层神秘色彩。但是，在这之前，蒙特卡罗方法就已经在科学上得到了应用。1777年，法国数学家布丰提出圆周率可以使用投针试验的方法进行求解，此方法被后人一致认为是蒙特卡罗法的源头1.2 研究现状分析 通常蒙特卡罗方法用来解决数学上的各种问题的途径主要是构造随机数。这就给科学上许多很难得以解答的复杂问题的求解提供了契机。蒙特卡罗方法在解决这类问题上无疑是一种有效的求出数值解的方法。蒙特卡罗方法在数学中最常见的应用就是蒙特卡罗法求解定积分。本文将在后续章节进行详细介绍。在力学中，蒙特卡罗方法在求解气体动力学问题也有着很重要的作用，澳大利亚G.A.伯德等人在求解此类问题是使用的是直接模拟统计试验法。该方法通过在计算机上对成千上万个模拟分子的运动、碰撞及相互作用，用来模拟真实气体的流动。它的设计思路基本上与玻耳兹曼方程是一样的，但是它是通过追踪有限个分子的空间位置和速度来代替计算真实气体中分布函数。在试验过程中，由于事先不知道那两个分子将会发生碰撞，所以将空间网格适当的取小值，在此基础上可以对分子之间有无碰撞和运动进行考察。所以随机取一对分子，通过对他们的模拟，从而计算它们的相对速度，在此基础上来对该分子进行取舍。运用此方法可以得出气体的密度、温度、速度等一些宏观参量。1.3 研究思路和方法 蒙特卡罗方法的是由Von.Neumann等数学家提出并对一些科学现象进行仿真。在这里，我将蒙特卡罗法的研究基本思路归纳如下：为了求解数学、物理、金融等方面的问题,首先要求建立一个模型，使其某个参数等于问题的解,随后通过对模型或过程的抽样和观察来计算所要求得的参数的统计特征,最后给出要求解的值的近似值。上述思想可以归纳为三步：描述或构造概率过程；在概率过程当中随机抽样；建立各种估计量并且给出近似解。 和传统的数值方法相比,蒙特卡罗方法体现出很强的灵活性和易实现性。其样本数量可以依据仿真需要的精度进行灵活的选取。正是因为这些优点,近年来蒙特卡罗方法已引起了信号处理专家的兴趣并被应用于信号处理的许多领域。 蒙特卡罗方法同样被广泛运用于通信领域,通信中人们最关心的问题之一系统的误码率性能问题。如果把码元是否出错对应的理解为服从0-1分布的随机变量,那么误码率正好是该随机变量的期望值,而对随机变量的数学期望进行估计,正是蒙特卡罗方法中最为经典的问题。 第二章 计算机仿真2.1 计算机仿真技术的概述 通过利用计算机软件模拟实际环境进行科学实验的技术被称为计算机仿真技术。它是以数学原理为基础，以计算机和各种物理设备为工具，利用系统模型对实际的或设想的系统进行试验仿真研究的一门综合技术。它具有经济、可靠、灵活、实用、安全等多重优点，已经成为对许多复杂系统进行分析、设计、实验、评估的必不可少的手段。2.2 计算机仿真技术的发展 计算机仿真技术主要是随着计算机技术，图形图像技术，和专业建模技术的发展而发展的。从历史上看，大致可以分为以下几个阶段：1、模型试验。最原始的仿真思想，其模型试验是基于物理模型进行的，存在精度上的缺陷。2、数字化仿真。采用计算机进行分析计算，但是计算结果表达局限于图表和文件上，使研究者不能直观观察。3、图像化仿真。大量采用丰富的图形图像技术来表达仿真结果，如现在生活中的三维图形。4、虚拟现实技术。该技术不光采用图像化技术表达计算结果，而且采用特殊装置，如带上三维数据头盔，触摸仪器，使人有身临其境的感觉。2.3 计算机仿真技术的发展现状及前景 自从计算机出现以后, 就开始有人利用计算机进行实际系统的仿真. 第二次世界大战期间, 美国研制原子弹的工作秘密的加紧进行, 其中的一个项目就是研究核裂变物质的中子随机扩散产生的破坏程度, 这要对一系列的材料分别进行实验, 实验周期长, 并且耗费大量的人力和物力, 对人体和环境都有直接或间接的伤害和危险。 但是负责项目研究的Von Neumann和Ulam使用电子计算机进行了模拟,并把这一研究项目称为蒙特卡罗计划.蒙特卡罗方法属于试验数学的一个分支，它是利用随机数技术进行试验,以求得统计特征值(如均值,概率等)作为问题的数值解. 在Von Neumann与Ulam的计算机模拟中采用了蒙特卡罗法, 这是世界上目前发现最早的计算机仿真。 后来Naylor(内勒)等人把Von Neumann等人的这一工作看作是计算机仿真的现代概念的源头。当时用ENIAC计算机进行的主要是为了给陆军计算弹道轨迹问题, 并且同时, 麻省理工学院研制计算机Whirlwind模拟飞行器, 贝尔实验室研制用运算放大为基础的电子模拟计算机, 实时模拟导弹和飞机的飞行。从理论上说，我们日常生活、工作中以及自然界中碰到的很多问题，都可用计算机进行仿真，使用计算机仿真具有经济、安全可靠、实验周期短的优点与特点。所以它已成为工程系统、科学研究人员乐于使用的一种设计分析的工具。下面简单介绍的一下计算机仿真的应用情况，在后面的章节里我们还将详细介绍一些应用实例。计算机仿真在工程系统研究的各个阶段，如方案论证、系统对象和基本部件的分析和设计等各个阶段，均发挥了显著作用。在航天航空科学方面，计算机仿真起着重大的作用，也是整个计划实施的第一步。例如：宇航员培训仿真系统。计算机仿真器在各行各业均有应用，飞机、坦克、火箭、导弹等复杂设备的操作训练均可使用仿真器，这种技术的有点不仅可以提高培训效率、节约资金和能源，最关键的乃是安全可靠。据不完全统计，目前世界各国用于训练仿真器的经费达数千亿美元，而且每年呈递增的势头。我国在电力、航空航天、国防科学领域均研制有相应的培训仿真器，1992年9月新闻报道，清华大学30万千瓦火力发电仿真机和300兆瓦火力发电仿真系统研制成功。1997年大亚湾核电站购买核电站仿真机消费1300万美元，后来我国自己研制了属于自己的核电站仿真机，也培养了一批本国的专业人员。国防科学及战争演练使用计算机仿真技术是不胜枚举的。最早的战争模拟是类似于象棋的征战模型，后来在18世纪初出现了沙盘模型用来模拟现实的地形和建筑，并应用于战争中，这在人类战争史上是一个很大的进步，但真正有效的模拟还是后来所使用的电子计算机进行仿真。现代战争和核战争的残酷性是可想而知的，无论是人员伤亡、物资消耗以及对现代文明的破坏远远超过以前的任何战争。为了消灭战争，就必须拥有强大的军事力量和巩固的国防，新的战略战术研究和制定、新武器的出台和投入使用的效果都要通过军事演习实践来检验，局部军事演习也会有很大的消耗，而在计算机上进行战争模拟和军事演习是最好的选择，它有着独特的优越性。我国新闻媒体曾多次报道计算机模拟技术在军事方面的应用，先进的军事与国防科学领域的计算机仿真技术正在飞速发展。计算机仿真是现代社会的产物，其功效取决于研究人员的研究深度和计算机的性能。自50年代开始以来，它的发展是非常迅速的，特别是近20年来显示出更强大的生命力。计算机模拟是一个强有力的工具，只要人们灵活地使用，就可使其在各部门、各行业发展巨大作用，为人类造福。同时它又是一门艺术，灵活多变、方法各异，正因为它具有这些特点，人们越来越重视它、喜爱它了。 第三章 定积分及其应用3.1 定积分的概念设函数在区间上连续，将区间分成个子区间,.，可知各区间的长度依次是：，.在每个子区间任取一点，作和式，设(即属于最大的区间长度），则当0时，该和式无限接近于某个常数，这个常数叫做函数在区间的定积分。记为：。其中：叫做积分下限，叫做积分上限，区间称为积分区间，被称作被积函数， 称为积分变量， 称为被积表达式， 称为积分号。之所以称其为定积分，是因为它积分后得出的值是确定的，是一个数， 而不是一个函数。 即：3.2 定积分的基本计算方法 在科学研究和实际生产中,经常遇到求积分的计算问题，由积分学知识可知，若函数在区间a,b连续且原函数为，则可用牛顿-莱布尼茨公式- = 求得积分。这个公式在理论上实际问题的解决中都起到了很大的作用.。另外，对于求导数也有一系列可以遵循的公式和法则。但是，也许在实际问题中我们常常会遇到如下求积分的计算的情形：对于某些函数的原函数无法用现有的公式求出.例如积分, 等，从而牛顿-莱布尼茨公式也无法解除类似问题的积分。对于某些函数使用表格或图形形式给出，所以在这种情况下也因不能直接用积分公式或导数公式求解出来。对于某些函数的原函数或导数值虽然能够求出，但形式过于复杂，不便使用.。由此可见，利用原函数求积分或利用求导法则求导数有很大的局限性，所以人们就在探寻更多求解积分的基本方法，目前有牛顿柯特斯公式法，梯形法，矩形法，抛物线法，随机投点法,平均值法,高斯型求积法等等，本文将会对其中的其中某些方法作一个横纵向的比较。 1、 几何意义上的数值算法 在几何上表示以a,b为底，以曲线为曲边的曲边梯形的面积,因此,计算的近似值也就是的近似值。沿着积分区间a,b，可以把大的曲边梯形分割成许多小的曲边梯形面积之和。常采用均匀分割，假设a,b上等分的小区间，其中表示小区间的长度.（1）矩形法 矩形法是用小矩形面积代替各个小曲边梯形面积来求得近似值，从面积得到的近似值。假设取小区间左端点的函数值为小矩形的高，如图1所示，则=- = 图1. 矩形法法求定积分的图解（2）梯形法 梯形法就是利用小直边梯形的面积代替小曲边梯形面积求得近似值，如图2所示，从而得到S的近似值为 图2. 梯形法法求定积分的图解2、概率意义上的数值方法 概率算法如今在求解定积分的时候属于一种常规方法，它的设计思想比较通俗易懂,容易得到实现。尽管这种算法消耗的计算时间会比较长,但是往往就能得到问题的近似解,并且近似程度会随计算时间的增加得到提高。所以概率算法适用于计算定积分的近似值。假如要求定积分的近似值,其中在a,b内可积,我们利用平均值法计算该积分,首先随机产生n个独立的随机变量,且在a,b上撑均匀分布的态势,即；然后,计算的近似值, 由中心极限定理知,若相互独立、同分布,且数学期望及标准差存在,则当n充分大时,随机变量渐近服从正态分布,即对任意的,从这里可以看出来,用平均值法计算定积分存在缺陷，即它的收敛速度较慢,在概率意义下的误差阶仅为 第四章 蒙特卡罗法4.1 蒙特卡罗法的来源和概述 当我们在求解某种随机事件出现的概率，或者是某个随机变量的期望值时，通过一种“实验”的方法，以出现这种事件的频率去估计所要求的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。现在就举一个简单的例子来认识一下蒙特卡罗方法：假设要计算一个不规则图形的面积，那么图形的不规则程度越高，分析性计算的复杂程度就越高，反之亦然。那么，蒙特卡罗方法是怎么计算的呢？首先在这不规则图形外作一个正方形或矩形将其包围，假想有一袋大米，把大米均匀地在这个图形上撒开来，然后数正方形和这个图形之中各有多少粒大米，求出这两个图中大米的数目比值，由于正方形面积是已知的，就可计算就是图形的面积。当你的大米越小，撒的越多，结果就越精确。由概率论的基本定义可知，某事件发生的概率可以用试验中该事件发生的频率来估算，当样本容量足够大时，可以认为该事件的发生的概率和频率是对等的。因此，对可能影响其可靠度的随机变量进行适当的随机抽样，然后把这些抽样值逐个地代入函数，确定结构是否失效，从而求得结构的失效概率。这正是蒙特卡罗法分析的基本思路。 设有随机变量，其对应的概率密度函数为、.，功能函数式为。首先根据各随机变量的相应分布，产生组随机数，.，值，计算功能函数值，若其中有L组随机数对应的功能函数值0，则当时，根据伯努利大数定理及正态随机变量的特性有：结构失效概率，可靠指标。 从蒙特卡罗方法的研究思路可看出，该方法在运用过程中避免了结构可靠度分析中大量数学困难，不管状态函数是不是非线性、随机变量是不是非正态，只要模拟的次数多，就可以得到一个比较精确的失效概率和可靠度指标。与法计算的可靠指标相比，结果更为精确，并且由于思路简单易于编制程序。4.2 概率模型和蒙特卡罗法现代社会中有许多由各学科相互交叉形成的巨大系统，例如环境系统、经济系统、人口系统、军事系统等，这些系统结构复杂，系统内各种因素的随机性对系统性能有很大影响，使系统性能具有随机性。对这类问题一般要建立随机模型，使用计算机模拟来对其定量、评价、决策和寻求达到最优化的途径，使用的方法是概率论和统计分析的方法。在前面对概率模型中使用的随机数进行了简单讨论，这里讨沦概率法建模，这些模型称为概率模型。1.古典概率模型 古典概率模型是一种重要的古老概率模型，在概率论发展的初期是主要的对象。设E是随机试验，是E的样本空间，若（1） 只含有有限个基本事件（有限性）。（2） 每个基本事件发生的可能性相等（等可能性）。这类随机现象的数学模型称为古典概率模型，即称E为古典概率模型。若E为古典概率模型，且,事件,其中是1，2，.n中任意r个不同的数，则可以求得事件A的概率，即为： 1 几何概率模型假如将古典概率模型中的有限范围推广到无限范围，并且保留等可能性，就能得到几何概率模型。几何概率模型的特点如下：一个拥有可度量的几何图形，试验E看成在中随机地投一点，即为样本空间。而事件A就是所投的点落在中的该可度量图形A中。事件A的概率与A的度量成正比。几何概率模型的概率定义为其中L表示度量，单位可以是面积、体积和长度等。 几何概率模型的典型事例就是著名的蒲丰（Buffon) 投针试验问题。这也是用蒙特卡罗法解决实际问题的一个典型事例, 蒙特卡罗法是计算机仿真中常用的方法。1777年法国数学家蒲丰提出用投针试验来计算圆周率值，其方法是：在平面上画一些彼此相距为a的平行线，向此平面投一长为l的针，假定针长1a，现要求出针与任一平行线相交的概率，试验如图所示。针的中点M1落在平行线之间，M1距平行线的距离为x，x的值均匀分布在0,a/2区间之内，针与线夹角均匀分布在0,之间，x与相互独立。如图3可以看到，针线相交的充要条件为 图3. 蒲丰实验 相交的概率为随机变量x与的联合密度函数的积分这一结果表明：针线相交的概率为阴影面积与矩形面积之比。如投针N次，M次针线相交，这一概率M/N，与上式相等，可求出值 “投针问题”还是找矿中的一个重要概率模型。设在一给定区域内的某处有一矿脉（相当于针），长为l,用间隔为a的一组平行线进行探测，假定la，要求出“找到此矿脉”的概率有多大，这就是投针问题的结果。概率模型种类较多，例如：二项分布概率模型、贝努利概率模型、几何分布概率模型、指数分布概率模型、正态分布概率模型等，在此不一一详述，读者可根据需要参考其他书籍 。 蒙特卡罗法的计算机模拟应用是J.Von Neumann 和S. Ulam于第二次世界大战期间提出的，当时他们在Los Alamos科学试验室进行核武器研究，为了设计核屏蔽防护，他们需要知道中子在各种材料中能传多远的距离，他们把这个研究称为蒙特卡罗计划。这个问题是不容易解决的，如果用实验的方法来测试非常危险，核辐射会伤害人体，也会耗费大量时间与金钱，因此他们在计算机上用随机数对实验系统进行模拟，由于这种模拟采用了博奕原理，因此这一方法也被称为蒙特卡罗法。并不是所有使用随机数的计算方法都叫蒙特卡罗法。只有对那些本质上为确定性别的问题使用随机数求解才能叫蒙特卡罗法。而用随机数对本质上是随机性的问题求解，只能叫“随机模拟”，这两者是不同的。例如对库存问题的模拟叫随机模拟，而用随机数计算值与用随机数模拟肥皂泡系统的方法则叫蒙特卡罗法。4.3 基于蒙特卡罗法的定积分计算现就以蒙特卡罗法为例求解一维定积分 该定积分为求曲线y=g(x)与x轴，y轴，以及x=1为边界的面积，见图4。计算的方法是: 在单位正方形（0x1,0y1）内随机投一点, 它的两个坐标值(xi，yi)是 y 1 (X2,Y2) g(x) (X1,Y1) 0 1 x 图4. 求定积分的例子图示相互独立的均匀分布在0,1区间的随机数，显然，落在曲线y =g(x)下部区域的概率P可按下式求出 即投点N次，落入y =g(x)曲线下部为M次，落在阴影外及正方形内的为N-M次，则上式积分的估计值为 一维积分C程序如下：MAIN（） INT M,N； FLOAT X,Y,S,F； SCANF(“%d”,N)； M=0； FOR(I=0;IN;I+) X=RAND(Z)； Y=RAND(Z)； F=FUNCTN(X)； IF(Y=F) M=M+1 ； S=FLOAT(M)/FLOAT(N) ； PRINTF(“%f”,S)； 其中，为随机投点的坐标，N为试验总数，M为落在阴影内的点数, S为待求积分值, RAND(Z)为产生0,1区间均匀分布随机数函数, FUNCTN(X)为计算被积函数g(x)值的函数。 下面就此方法举例演示：假如要计算，模拟次数分别为、调试此程序，将会得到如下的结果定积分的精确值和模拟值如表1所示：表1. 计算的精确值和模拟值比较精确值0.34134470.3420.3440.341870.3415390.341302结语 计算机仿真实际上就是将一个描述实际系统的数学模型经过第二次模型化，使其变成一个能够运用计算机运算求解的当代计算机仿真模型，并在计算机内进行运转的过程，以此获得大量实际系统的定量信息、数据和资料，强化对实际系统的认识和探究。目前在很多领域都发挥着重要的作用。 用蒙特卡罗模拟法计算定积分具有十分普遍的意义。蒙特卡罗模拟方法给我们提供了一个看待世界的新思路，那就是一个或许根本不具随机性的事件可以通过像类似蒙特卡罗模拟的方法用随机事件来模拟或逼近。 致谢 经过将近半年的努力本论文终于完成了，首先感谢学院对我的培育之恩，以及给我提供了良好的写作环境，使我有充足的时间和空间去学习和设计，在这期间我学到了太多新的知识，也让我充分了解到了自己的不足之处，在以后的工作和学习中我会更加努力。再次感谢全体老师对我的栽培，是你们带领我走向计算机和电子技术的大门，也促使我对该方面产生了浓厚的兴趣。 特别感谢我的指导老师，整个毕业论文的写作过程都是在老师的悉心教导下完成的。从论文的选题、程序设计思想、理论的构造以至最终的完稿，老师都给予了大量的帮助。老师们治学严谨，认真负责，为我的写作营造了一种良好的精神氛围。在此论文完成之际，谨向老师们致以衷心的感谢！ 同时我还要感谢帮助过我的同学。感谢他们在系统设计期间给予的无私帮助，使我能按时顺利的完成。谢谢！参考文献 1 傅廷亮，计算机模拟技术，中国科学技术大学出版社，2001年12月2 朱志明和包焕升,海轮县经济系统的动态仿真，1985年12月第4期3 郭俊义,计算机模拟理论方法及其应用宇航出版社，1988年4 王明亮，GPSSWorld 模拟仿真系统实验教程，M. 西南交通大学出版社，2010, 4-605 陈义华，数学模型，M. 重庆大学出版社， 1995年.6 骆承钦，高等数学，高等教育出版社，2006年7 刘光宇，虞跃升。计算机模拟的应用。汽车科技2006年第06期。8 Narsingh Deo, System Simulation with Digital Computer, Prentice Hall of India Private Limited. New Delhi110001, 1979年.9 W. J. Meyer, Concepts of Mahematical Modeling, 1984年.10 SamidipBasu.IntrouctiontoSoftwareEngineeringM.NorthDakotaStateUniversityThesisCollection2002,11:20-2816