首页 > 编程语言 >蒙特卡洛算法

蒙特卡洛算法

时间:2023-05-31 23:38:21浏览次数:53  
标签:double 点集 算法 蒙特卡罗 MAX 蒙特卡洛 方法


从今天开始要研究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. 蒙特卡洛的应用

 

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

 

代码:

#include <bits/stdc++.h>

#define MAX_ITERS 1000000

using namespace std;

double Rand(double L, double R)
{
	return L + (R - L) * rand() * 1.0 / RAND_MAX;
}

double GetPi()
{
	srand(time(NULL));
	int cnt = 0;
	for(int i = 0; i < MAX_ITERS; i++)
	{
		double x = Rand(-1, 1);
		double y = Rand(-1, 1);
		if(x * x + y * y <= 1)
			cnt++;
	}
	return cnt * 4.0 / MAX_ITERS;
}

int main()
{
    for(int i = 0; i < 10; i++)
		cout << GetPi() << endl;
	return 0;
}

 

3. 蒙特卡洛积分

 

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

 

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


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

蒙特卡洛算法_i++

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


   首先考虑如下积分


      

蒙特卡洛算法_随机数_02


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


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


      

蒙特卡洛算法_点集_03


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

蒙特卡洛算法_随机数_04

对随机点

蒙特卡洛算法_点集_05

,    对于每一对

蒙特卡洛算法_随机数_06

,考察是否满足如下条件


         

蒙特卡洛算法_i++_07


    假设满足上述条件的点有

蒙特卡洛算法_随机数_08

个,而全部的点有

蒙特卡洛算法_随机数_04

个,所以得到近似公式为


         

蒙特卡洛算法_随机数_10


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


         

蒙特卡洛算法_随机数_11


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


          

蒙特卡洛算法_随机数_12


    接下来写写代码吧!


代码:


#include <bits/stdc++.h>

#define MAX_ITERS 10000000

using namespace std;

struct Point
{
	double x, y;
};

double Rand(double L, double R)  
{  
	return L + (R - L) * rand() * 1.0 / RAND_MAX;  
} 

Point getPoint()
{
	Point t;
	t.x = Rand(1.0, 2.0);
	t.y = Rand(0.0, 1.0);
	return t;
}

double getResult()
{
	int m = 0;
	int n = MAX_ITERS;
	srand(time(NULL));
	for(int i = 0; i < n; i++)
	{
		Point t = getPoint();
		double res = t.x * t.y;
		if(res <= 1.0)
			m++;
	}
	return pow(2.0, 1.0 * n / m);
}

int main()
{
	for(int i = 0; i < 20; i++)
		cout << fixed << setprecision(6) << getResult() << endl;
	return 0;
}

 

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

 

             

蒙特卡洛算法_i++_13

 

 

 

标签:double,点集,算法,蒙特卡罗,MAX,蒙特卡洛,方法
From: https://blog.51cto.com/u_16146153/6391028

相关文章

  • MATLAB用改进K-Means(K-均值)聚类算法数据挖掘高校学生的期末考试成绩|附代码数据
    全文链接:http://tecdat.cn/?p=30832最近我们被客户要求撰写关于K-Means(K-均值)聚类算法的研究报告,包括一些图形和统计输出。本文首先阐明了聚类算法的基本概念,介绍了几种比较典型的聚类算法,然后重点阐述了K-均值算法的基本思想,对K-均值算法的优缺点做了分析,回顾了对K-均值改进......
  • 通用数字滤波算法
    不论你是做数字信号处理还是系统自动控制,只要系统中有模拟数据采集部分,就不可避免的存在噪声干扰的问题。应对噪声,一个方法就是利用硬件搭建模拟的滤波器,在前端采样电路滤除掉噪声;另一个方法,就是利用ADC采样,运行软件滤波算法,滤除掉信号中的噪声。特别声明:本文为个人在阅读《匠......
  • 基于模拟退火优化算法的三维装箱优化matlab仿真,优化重量利用率和空间利用率
    1.算法仿真效果matlab2022a仿真结果如下:2.算法涉及理论知识概要模拟退火算法来源于固体退火原理,是一种基于概率的算法,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减......
  • 基于模拟退火优化算法的三维装箱优化matlab仿真,优化重量利用率和空间利用率
    1.算法仿真效果matlab2022a仿真结果如下:     2.算法涉及理论知识概要      模拟退火算法来源于固体退火原理,是一种基于概率的算法,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平......
  • m基于HOG特征提取和GRNN网络的人体姿态识别算法matlab仿真,样本为TOF数据库的RGB-D深
    1.算法仿真效果matlab2022a仿真结果如下:TOF数据库如下:2.算法涉及理论知识概要1、HOG特征:方向梯度直方图(HistogramofOrientedGradient,HOG)特征是一种在计算机视觉和图像处理中用来进行物体检测的特征描述子。它通过计算和统计图像局部区域的梯度方向直方图来构成特征。......
  • 基于ACGWO混沌灰狼优化算法的MATLAB对比仿真,对比标准的GWO
    1.算法仿真效果matlab2022a仿真结果如下:2.算法涉及理论知识概要灰狼优化算法(GWO),灵感来自于灰狼.GWO算法模拟了自然界灰狼的领导层级和狩猎机制.四种类型的灰狼,如α,β,δ,w被用来模拟领导阶层。此外,还实现了狩猎的三个主要步骤:寻找猎物、包围猎物和攻击猎物。为了在......
  • 基于ACGWO混沌灰狼优化算法的MATLAB对比仿真,对比标准的GWO
    1.算法仿真效果matlab2022a仿真结果如下: 2.算法涉及理论知识概要       灰狼优化算法(GWO),灵感来自于灰狼.GWO算法模拟了自然界灰狼的领导层级和狩猎机制.四种类型的灰狼,如α,β,δ,w被用来模拟领导阶层。此外,还实现了狩猎的三个主要步骤:寻找猎物、包围猎物和攻......
  • 算法学习(22): 逆序对与原序列
    逆序对与原序列在《组合数学》中有这么一个从逆序列构建一个排列的过程……而刚好有一场考试有考了类似的问题,于是在此总结一下。目录逆序对与原序列逆序列逆序个数带修改问题逆序列假定我们有序列\(P\)是\(\{1,2,\cdots,n\}\)的一个排列。如果\(i<j\)并且\(p_......
  • m基于HOG特征提取和GRNN网络的人体姿态识别算法matlab仿真,样本为TOF数据库的RGB-D深
    1.算法仿真效果matlab2022a仿真结果如下:  TOF数据库如下:      2.算法涉及理论知识概要1、HOG特征:        方向梯度直方图(HistogramofOrientedGradient,HOG)特征是一种在计算机视觉和图像处理中用来进行物体检测的特征描述子。它通过计算和统......
  • 算法:排序算法-选择排序
       ......