专栏首页小樱的经验随笔蒙特卡洛算法及其实现

蒙特卡洛算法及其实现

从今天开始要研究Sampling Methods,主要是MCMC算法。本文是开篇文章,先来了解蒙特卡洛算法

Contents

   1. 蒙特卡洛介绍

   2. 蒙特卡洛的应用

   3. 蒙特卡洛积分

1. 蒙特卡洛介绍

蒙特卡罗方法(Monte Carlo method),也称统计模拟方法,是二十世纪四十年代中期由于科学技术的

   发展和电子计算机的发明,而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使

   用随机数(或伪随机数)来解决很多计算问题的方法。与它对应的是确定性算法。蒙特卡罗方法在金融工程

   学,宏观经济学,计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)等领域应用广泛。

   蒙特卡罗方法于20世纪40年代美国在第二次世界大战中研制原子弹的“曼哈顿计划”计划的成员S.M.乌拉姆

   和J.冯·诺伊曼首先提出。数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的Monte Carlo—来命名这种方法,

   为它蒙上了一层神秘色彩。在这之前,蒙特卡罗方法就已经存在。1777年,法国数学家布丰提出用投针实验

   的方法求圆周率,这被认为是蒙特卡罗方法的起源。

   另外,拟蒙特卡洛算法在近几年也获得迅速发展。这种方法是用确定性的超均匀分布代替蒙特卡洛算法中的

   随机数序列,对于某些特定问题计算速度比普通的蒙特卡洛算法高几百倍。

   由于产生随机数的随机性,当我们用N个随机点以蒙特卡罗方法来求解具体的问题时,其计算得到近似解的误

   差值有大有小,但是肯定有一个确定的平均值,即一些误差大于此值,而其余误差小于此值。鉴于此,显然肯

   定存在这样的N个点,使得误差的绝对值不大于平均值。如果我们能够构造这样的点集,就可以对原有的方法

   进行较大的改进。拟蒙特卡罗方法就是至于此而提出的,它致力于构造其误差比平均误差显著要好的那种点集,

   而其求解形式与蒙特卡罗方法一致,只不过所用的随机数不一样。用蒙特卡罗方法求解问题时,影响结果好坏

   的主要是随机数序列的均匀性。而拟蒙特卡罗方法中的具有低偏差的一致分布点集较伪随机数序列更为均匀,

   而且用拟蒙特卡罗方法求解得到的是真正的误差,避免了蒙特卡罗方法得到概率误差的缺陷。

   由此可见用拟蒙特卡罗方法求解问题的关键是如何找到一个均匀散布的点集。目前常用的点集有GLP点集(好格

   子点集,good lattice point set)、GP点集(好点集,good point set)、Halton点集及其变体、

   Hammersley点集等。

   蒙特卡洛方法的理论基础是大数定律。大数定律是描述相当多次数重复试验的结果的定律,根据这个定律知道

   样本数量越多,其平均就越趋近于真实值。

2. 蒙特卡洛的应用

   最经典的应用就是利用蒙特卡洛算法求圆周率。代码如下

代码:

 1 #include <bits/stdc++.h>
 2 
 3 #define MAX_ITERS 1000000
 4 
 5 using namespace std;
 6 
 7 double Rand(double L, double R)
 8 {
 9     return L + (R - L) * rand() * 1.0 / RAND_MAX;
10 }
11 
12 double GetPi()
13 {
14     srand(time(NULL));
15     int cnt = 0;
16     for(int i = 0; i < MAX_ITERS; i++)
17     {
18         double x = Rand(-1, 1);
19         double y = Rand(-1, 1);
20         if(x * x + y * y <= 1)
21             cnt++;
22     }
23     return cnt * 4.0 / MAX_ITERS;
24 }
25 
26 int main()
27 {
28     for(int i = 0; i < 10; i++)
29         cout << GetPi() << endl;
30     return 0;
31 }

3. 蒙特卡洛积分

   关于蒙特卡洛求积分,可以先参照如下文章。

   链接:http://cos.name/2010/03/monte-carlo-method-to-compute-integration/

   接下来用蒙特卡洛积分求自然常数

。这是2015年阿里的一道笔试题。

   首先考虑如下积分

   接下来分别用蒙特卡洛积分牛顿莱布尼兹公式计算,在蒙特卡洛方法中样本很多时,它们的值应该相等。

   利用蒙特卡洛方法,图像大致如下

    上述积分的目的是求阴影部分的面积,所以先在所标矩形内取

对随机点

    对于每一对

,考察是否满足如下条件

    假设满足上述条件的点有

个,而全部的点有

个,所以得到近似公式为

    而依据牛顿莱布尼兹公式可以得到

    这两种方法结果应该是相等的,即有

    接下来写写代码吧!

代码:

 1 #include <bits/stdc++.h>
 2 
 3 #define MAX_ITERS 10000000
 4 
 5 using namespace std;
 6 
 7 struct Point
 8 {
 9     double x, y;
10 };
11 
12 double Rand(double L, double R)  
13 {  
14     return L + (R - L) * rand() * 1.0 / RAND_MAX;  
15 } 
16 
17 Point getPoint()
18 {
19     Point t;
20     t.x = Rand(1.0, 2.0);
21     t.y = Rand(0.0, 1.0);
22     return t;
23 }
24 
25 double getResult()
26 {
27     int m = 0;
28     int n = MAX_ITERS;
29     srand(time(NULL));
30     for(int i = 0; i < n; i++)
31     {
32         Point t = getPoint();
33         double res = t.x * t.y;
34         if(res <= 1.0)
35             m++;
36     }
37     return pow(2.0, 1.0 * n / m);
38 }
39 
40 int main()
41 {
42     for(int i = 0; i < 20; i++)
43         cout << fixed << setprecision(6) << getResult() << endl;
44     return 0;
45 }

观察一下运行结果,效果还是不错的。如下图

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 想知道 GitHub 上各开源项目的生存状况如何?这个软件告诉你!

    今日凌晨,DataScience Inc. 发布了 DataScience Trends。 这是一个针对 GitHub 资源库的交互式数据分析与可视化工具,能方...

    AI研习社
  • 走出并行计算的误区,你应该在什么时候用它?

    AI 研习社按:本文为 Salesforce 知名数据科学家、机器学习工程师 Anmol Rajpurohit 对开发者的建议。对算法进行并行处理,是业内常见的...

    AI研习社
  • 常见面试之机器学习算法思想简单梳理

    导语:今天小编从别的地方推送一篇更广泛的文章供你们学习参考,总结的常见机器学习算法(主要是一些常规分类器)大概流程和主要思想,希望对大家找机器学习岗位时有点帮助...

    IT派
  • 谈谈数据结构

    沃斯大神说过,程序 = 算法 + 数据结构。 程序君认为,等式的右边,数据结构的权重要大于算法。数据结构定义好,基本上,你所用的算法也就确定了,算法的时间复杂度...

    tyrchen
  • 吴恩达带斯坦福ML组发了新论文:深度学习攻克心律不齐难题

    李林 编译整理 量子位 报道 | 公众号 QbitAI ? 吴恩达带领的斯坦福机器学习组(Stanford ML Group)最近开发了一种深度学习新算法,能诊...

    量子位
  • 一篇文章告诉你如何成为数据科学家

    通常来说,年轻人都很容易立志成为什么,例如成为一名科学家,然后又很快放弃。这一方面是因为摆在他们面前的诱惑太多,同时也因为成为一名科学家真的很不容易。 这一点放...

    AI研习社
  • 我所理解的接口设计

    前言 自己做接口开发的时间也算不短了(三年),想写这篇文章其实差不多已经有一年多的时间了。我将从下面的方向来对我所理解的接口设计做个总结: 接口参数定义 -> ...

    程序员宝库
  • 从零教你写一个完整的GAN(附代码)

    导言 啦啦啦,现今 GAN 算法可以算作 ML 领域下比较热门的一个方向。事实上,GAN 已经作为一种思想来渗透在 ML 的其余领域,从而做出了很多很 Am...

    AI研习社
  • 一篇文章搞懂人脸识别的十个概念

    作者:汪铖杰 首发于 腾讯云技术社区 量子位 已获授权编辑发布 优图实验室研究人脸技术多年,不仅在技术方面有很好的积累,而且在公司内外的业务中有众多应用。笔者作...

    量子位
  • 机器学习中的“哲学”

    作者:阿萨姆 普华永道|数据科学家 量子位 已授权编辑发布 0. 前言 我更喜欢把”思想”认为是一种“道”,而”模型”是一种”术”,也可类比为“外功”和“内功”...

    量子位

扫码关注云+社区

领取腾讯云代金券