当前位置：文档之家 › 蒙特卡洛算法

蒙特卡洛算法

  • 格式：doc
  • 大小：91.50 KB
  • 文档页数：4

蒙特卡洛算法

组员 李小兵 周立 冯俊 李继华 艾海提 李日浩

算法简介

蒙特·卡洛方法，也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。蒙特·卡洛方法的名字来源于摩纳哥的一个城市蒙地卡罗，该城市以赌博业闻名，而蒙特·卡罗方法正是以概率为基础的方法。

与它对应的是确定性算法。

蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)等领域应用广泛。

背景知识

1946年，美国拉斯阿莫斯国家实验室的三位科学家John von

Neumann,Stan Ulam 和 Nick Metropolis共同发明，被称为蒙特卡洛方法。它的具体定义是：在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，现在要计算这个不规则图形的面积，怎么计算列?蒙特卡洛(Monte Carlo)方法告诉我们，均匀的向该正方形内撒N（N 是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个，那么，这个奇怪形状的面积便近似于M/N，N越大，算出来的值便越精确。在这里我们要假定豆子都在一个平面上，相互之间没有重叠。蒙特卡洛方法可用于近似计算圆周率：让计算机每次随机生成两个0到1之间的数，看这两个实数是否在单位圆内。生成一系列随机点，统计单位圆内的点数与总点数，（圆面积和正方形面积之比为PI:1，PI为圆周率），当随机点取得越多（但即使取10的9次方个随机点时，其结果也仅在前4位与圆周率吻合）时，其结果越接近于圆周率。

算法描述

以概率和统计理论方法为基础的一种计算方法。将所求解的问题同一定的概率模型相联系，用计算机实现统计模拟或抽样，以获得问题的近似解。比如，给定x=a，和x=b，你要求某一曲线f和这两竖线，及x轴围成的面积，你可以起定y轴一横线 y=c 其中c>=f(x)max，很简单的，你可以求出 y=c,x=a,x=b,及 x轴围成的矩形面积，然后利用随机产生大量在这个矩形范围之内的点，统计出现在曲线上部点数和出现在曲线下部点的数目，记为：doteUpCount,nodeDownCount,然后所要求的面积可以近似为

doteDownCounts所占比例*矩形面积。

问题描述

在数值积分法中，利用求单位圆的1/4的面积来求得Pi/4，从而得到Pi。单位圆的1/4面积是一个扇形，它是边长为1单位正方形的一部分。只要能求出扇形面积S1在正方形面积S中占的比例K=S1/S就立即能得到S1，从而得到Pi的值。怎样求出扇形面积在正方形面积中占的比例K呢？一个办法是在正方形中随机投入很多点，使所投的点落在正方形中每一个位置的机会相等看其中有多少个点落在扇形内。将落在扇形内的点数m与所投点的总数n的比m/n作为k的近似值。Pi=4m/n。P落在扇形内的充要条件是x^2+y^2<=1。

利用蒙特卡洛算法近似求圆周率PI

VC++6.0

ZZH

#include

#include

#include

#define COUNT 500000 //循环取样次数

using namespace std;

bool InCircle(double x,double y)//是否在1/4圆范围之内

{

if((x*x+y*y)<=1)return true;

return false;

}

void main()

{

double x,y;

int num=0;

int i;

srand((unsigned)time(NULL));

for(i=0;i

{

x=rand()*1.0/RAND_MAX;

y=rand()*1.0/RAND_MAX;

if(InCircle(x,y)) num++;

}

cout<<"PI:"<<(num*4.0)/COUNT<

}

结果：测试5次的结果显示：3.13958，3.14041，3.13729，3.13859，3.14186

什么是Mapreduce

MapReduce 是 Google 公司的核心计算模型，它将复杂的运行于大规模集群上的并行计算过程高度的抽象到了两个函数，Map（映射） 和 Reduce（简化）, 这是一个令人惊讶的简单却又威力巨大的模型。适合用 MapReduce 来处理的数据集(或任务)有一个基本要求: 待处理的数据集可以分解成许多小的数据集，而且每一个小数据集都可以完全并行地进行处理。

图 1. MapReduce 计算流程

图一说明了用 MapReduce 来处理大数据集的过程, 这个 MapReduce 的计算过程简而言之，就是将大数据集分解为成百上千的小数据集，每个(或若干个)数据集分别由集群中的一个结点(一般就是一台普通的计算机)进行处理并生成中间结果，然后这些中间结果又由大量的结点进行合并, 形成最终结果。

计算模型的核心是 Map 和 Reduce 两个函数，这两个函数由用户负责实现，功能是按一定的映射规则将输入的 对转换成另一个或一批

value> 对输出。 开发者只需要为数据集编写特定的Map/Reduce操作，有时甚至只需25-50行代码就够了，而MapReduce软件微架构会处理并行任务并且向分布在各处的计算机分发任务，同时处理机器错误和数据中的错误条件并进行优化操作，例如把计算过程推移到靠近数据的一方执行来减少I/O带来的带宽消耗，还提供了系统监控并且通过数以千计的计算机保持服务的可拓展性。

Hadoop 实现了 Google 的 MapReduce 编程模型，提供了简单易用的编程接口，也提供了它自己的分布式文件系统 HDFS,与 Google 不同的是，Hadoop 是开源的，任何人都可以使用这个框架来进行并行编程。

Hadoop就不细说了，Hadoop 支持 Linux 及 Windows 操作系统两种，真心难装，本人是Linux上的，请高手装的，建议在Windows下装，体验伪分布式的。Hadoop的安装别的组有高手就说说吧！

伪分布式运行模式

这种模式也是在一台单机上运行，但用不同的 Java 进程模仿分布式运行中的各类结点 ( NameNode, DataNode, JobTracker, TaskTracker, Secondary

NameNode )，请注意分布式运行中的这几个结点的区别：

从分布式存储的角度来说，集群中的结点由一个 NameNode 和若干个 DataNode

组成, 另有一个 Secondary NameNode 作为 NameNode 的备份。从分布式应用的角度来说，集群中的结点由一个 JobTracker 和若干个 TaskTracker 组成，JobTracker 负责任务的调度，TaskTracker 负责并行执行任务。TaskTracker 必须运行在 DataNode 上，这样便于数据的本地计算。JobTracker 和 NameNode 则无须在同一台机器上。

Hadoop上的pi值程序：

转另一个文档。

合集下载

蒙特卡洛算法计算概率分布

蒙特卡洛算法计算概率分布

蒙特卡洛算法计算概率分布

蒙特卡洛算法是一种基于随机模拟的计算方法，可以用于计算概率分布。下面是一个使用蒙特卡洛算法计算概率分布的示例：

假设我们要计算一个函数 $f(x)$ 在区间 $[a,b]$ 上的概率分布。我们可以按照以下步骤进行：

1. 生成随机数：在区间 $[a,b]$ 上生成大量的随机数。这些随机数可以通过随机数生成器或者其他方法获得。

2. 计算函数值：对于每个生成的随机数 $x_i$，计算函数 $f(x_i)$ 的值。

3. 统计分布：统计函数值出现的次数，并将其与总的随机数数量相除，得到函数值在区间 $[a,b]$ 上的概率分布。

通过重复上述步骤多次（通常称为“蒙特卡洛模拟”），我们可以获得函数在区间

$[a,b]$ 上的概率分布的估计。

需要注意的是，蒙特卡洛算法的准确性取决于生成的随机数数量和质量。为了获得更准确的结果，通常需要生成大量的随机数，并采用合适的随机数生成方法。

蒙特卡洛算法在许多领域都有应用，如统计学、计算机科学、金融工程等。它可以用于计算复杂问题的近似解，或者对难以直接计算的概率分布进行估计。

这只是一个简单的示例，实际应用中可能需要根据具体问题进行适当的修改和扩展。蒙特卡洛算法是一种强大的工具，但在使用时需要谨慎考虑其局限性和误差来源。

希望这个解释对你有帮助！如果你有任何其他问题，请随时提问。

蒙特卡罗算法

蒙特卡罗算法

Monte Carlo方法概述

一、Monte Carlo历史渊源

Monte Carlo方法的实质是通过大量随机试验，利用概率论解决问题的一种数值方法，基本思想是基于概率和体积间的相似性。它和Simulation有细微区别。单独的Simulation只是模拟一些随机的运动，其结果是不确定的；Monte Carlo在计算的中间过程中出现的数是随机的，但是它要解决的问题的结果却是确定的。

历史上有记载的Monte Carlo试验始于十八世纪末期（约1777年），当时布丰（Buffon）为了计算圆周率，设计了一个“投针试验”。（后文会给出一个更加简单的计算圆周率的例子）。虽然方法已经存在了200多年，此方法命名为Monte Carlo则是在二十世纪四十年，美国原子弹计划的一个子项目需要使用Monte Carlo方法模拟中子对某种特殊材料的穿透作用。出于保密缘故，每个项目都要一个代号，传闻命名代号时，项目负责人之一von Neumann灵犀一点选择摩洛哥著名赌城蒙特卡洛作为该项目名称，自此这种方法也就被命名为Monte

Carlo方法广为流传。

十一、Monte Carlo方法适用用途

（一）数值积分

计算一个定积分，如，如果我们能够得到f(x)的原函数F(x)，那么直接由表达式: F(x1)-F(x0)可以得到该定积分的值。但是，很多情况下，由于f(x)太复杂，我们无法计算得到原函数F(x)的显示解，这时我们就只能用数值积分的办法。如下是一个简单的数值积分的例子。

数值积分简单示例

如图，数值积分的基本原理是在自变量x的区间上取多个离散的点，用单个点的值来代替该小段上函数f(x)值。

常规的数值积分方法是在分段之后，将所有的柱子（粉红色方块）的面积全部加起来，用这个面积来近似函数f(x)（蓝色曲线）与x轴围成的面积。这样做当然是不精确的，但是随着分段数量增加，误差将减小，近似面积将逐渐逼近真实的面积。

马尔可夫链蒙特卡洛算法

马尔可夫链蒙特卡洛算法

马尔可夫链蒙特卡洛算法

马尔可夫链蒙特卡洛算法（Markov Chain Monte Carlo，MCMC算法）是一类经典的统计模拟方法，用于从复杂的概率分布中进行抽样，以求解各种统计问题。

MCMC算法的核心是利用马尔可夫链的性质进行概率抽样。具体步骤如下：

1. 确定目标分布：首先需要确定所要抽样的目标分布，通常是在计算困难的概率模型中计算概率密度（或概率质量）函数的常数比例。

2. 构建马尔可夫链：构建一个马尔可夫链，使得其平稳分布等于目标分布。常见的马尔可夫链包括Metropolis-Hastings算法、Gibbs采样等。

3. 进行迭代抽样：从适当的初始状态开始，根据马尔可夫链的转移规则进行迭代。每次迭代都根据当前状态和转移规则生成一个新的候选状态，接受或者拒绝该状态作为下一步的状态，通过计算接受概率等条件转移概率来决定是否接受。

4. 收敛检验：经过充分迭代后，进行收敛检验，判断抽样结果是否已经达到平稳分布，通常使用自相关函数等进行检验。

5. 统计分析：使用抽样结果进行统计分析，例如估计分布的均值、方差等参数。

MCMC算法具有广泛的应用，如蒙特卡洛积分、贝叶斯统计、马尔可夫链模型参数估计等。但是，MCMC算法的主要困难在于如何构建合适的马尔可夫链、如何设置收敛准则以及如何处理高维空间中的抽样问题。

(完整版)蒙特卡洛算法详讲

(完整版)蒙特卡洛算法详讲

Monte Carlo 法

§8.1 概述

Monte Carlo 法不同于前面几章所介绍的确定性数值方法，它是用来解决数学和物理问题的非确定性的（概率统计的或随机的）数值方法。Monte Carlo 方法（MCM），也称为统计试验方法，是理论物理学两大主要学科的合并：即随机过程的概率统计理论（用于处理布朗运动或随机游动实验）和位势理论，主要是研究均匀介质的稳定状态[1]。它是用一系列随机数来近似解决问题的一种方法，是通过寻找一个概率统计的相似体并用实验取样过程来获得该相似体的近似解的处理数学问题的一种手段。运用该近似方法所获得的问题的解in spirit更接近于物理实验结果，而不是经典数值计算结果。

普遍认为我们当前所应用的MC技术，其发展约可追溯至1944年，尽管在早些时候仍有许多未解决的实例。MCM的发展归功于核武器早期工作期间Los

Alamos（美国国家实验室中子散射研究中心）的一批科学家。Los Alamos 小组的基础工作刺激了一次巨大的学科文化的迸发，并鼓励了MCM在各种问题中的应用[2]-[4]。“Monte Carlo”的名称取自于Monaco（摩纳哥）内以赌博娱乐而闻名的一座城市。

Monte Carlo 方法的应用有两种途径：仿真和取样。仿真是指提供实际随机现象的数学上的模仿的方法。一个典型的例子就是对中子进入反应堆屏障的运动进行仿真，用随机游动来模仿中子的锯齿形路径。取样是指通过研究少量的随机的子集来演绎大量元素的特性的方法。例如，)(xf在bxa上的平均值可以通过间歇性随机选取的有限个数的点的平均值来进行估计。这就是数值积分的Monte Carlo 方法。MCM已被成功地用于求解微分方程和积分方程，求解本征值，矩阵转置，以及尤其用于计算多重积分。

任何本质上属随机组员的过程或系统的仿真都需要一种产生或获得随机数的方法。这种仿真的例子在中子随机碰撞，数值统计，队列模型，战略游戏，以及其它竞赛活动中都会出现。Monte Carlo 计算方法需要有可得的、服从特定概率分布的、随机选取的数值序列。