MonteCarlo算法模拟.ppt

MonteCarlo模拟,内容提纲,1.引言2.MonteCarlo模拟基本思想3.随机数生成函数4.应用实例举例5.排队论模拟6.MonteCarlo模拟求解规划问题,引言(Introduction),MonteCarlo方法：,蒙特卡罗方法，又称随机模拟方法，属于计算数学的一个分支，它是在上世纪四十年代中期为了适应当时原子能事业的发展而发展起来的。亦称统计模拟方法，statisticalsimulationmethod利用随机数进行数值模拟的方法,MonteCarlo名字的由来：,MonteCarlo是摩纳哥（monaco)的首都，该城以赌博闻名,NicholasMetropolis(1915-1999),Monte-Carlo,Monaco,MonteCarlo方法的基本思想,蒙特卡罗方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。源于美国在第二次世界大战研制原子弹的“曼哈顿计划”，该计划的主持人之一数学家冯诺伊曼用驰名世界的赌城摩纳哥的MonteCarlo来命名这种方法，为它蒙上了一层神秘色彩。蒙特卡罗方法的基本思想很早以前就被人们所发现和利用。早在17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。19世纪人们用蒲丰投针的方法来计算圆周率，上世纪40年代电子计算机的出现，特别是近年来高速电子计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。,蒲丰投针实验：法国科学家蒲丰(Buffon)在1777年提出的蒲丰投针实验是早期几何概率一个非常著名的例子。蒲丰投针实验的重要性并非是为了求得比其它方法更精确的值，而是它开创了使用随机数处理确定性数学问题的先河，是用偶然性方法去解决确定性计算的前导。由此可以领略到从“概率土壤”上开出的一朵瑰丽的鲜花-蒙特卡罗方法(MC)蒲丰投针实验可归结为下面的数学问题：平面上画有距离为a的一些平行线，向平面上任意投一根长为l(la)的针，假设针落在任意位置的可能性相同，试求针与平行线相交的概率P(从而求),蒲丰投针实验：如右图所示，以M表示针落下后的中点，以x表示M到最近一条平行线的距离，以表示针与此线的交角：针落地的所有可能结果满足：其样本空间视作矩形区域,面积是:针与平行线相交的条件：它是样本空间子集A，面积是：symslphi;int(l/2*sin(phi),phi,0,pi)%ans=l因此，针与平行线相交的概率为：从而有：,蒲丰投针实验的计算机模拟：formatlong;%设置15位显示精度a=1;l=0.6;%两平行线间的宽度和针长figure;axis(0,pi,0,a/2);%初始化绘图板set(gca,nextplot,add);%初始化绘图方式为叠加counter=0;n=2010;%初始化计数器和设定投针次数x=unifrnd(0,a/2,1,n);phi=unifrnd(0,pi,1,n);%样本空间fori=1:nifx(i)l*sin(phi(i)/2%满足此条件表示针与线的相交plot(phi(i),x(i),r.);counter=counter+1;%统计针与线相交的次数frame(counter)=getframe;%描点并取帧endendfren=counter/n;pihat=2*l/(a*fren)%用频率近似计算figure(2)movie(frame,1)%播放帧动画1次,一些人进行了实验，其结果列于下表：,蒙特卡罗投点法是蒲丰投针实验的推广：在一个边长为a的正方形内随机投点，该点落在此正方形的内切圆中的概率应为该内切圆与正方形的面积比值，即n=10000;a=2;m=0;fori=1:nx=rand(1)*a;y=rand(1)*a;if(x-a/2)2+(y-a/2)2MAXP时停止迭代,在Matlab软件包中编程，共需三个文件:randlp.m,mylp.m,lpconst.m.主程序为randlp.m.,%mylp.mfunctionz=mylp(x)%目标函数z=2*x(1)2+x(2)2-x(1)*x(2)-8*x(1)-3*x(2);%转化为求最小值问题,%randlp.mfunctionsol,r1,r2=randlp(a,b,n)%随机模拟解非线性规划debug=1;a=0;%试验点下界b=10;%试验点上界n=1000;%试验点个数r1=unifrnd(a,b,n,1);%a,b均匀分布随机数矩阵r2=unifrnd(a,b,n,1);sol=r1(1)r2(1);z0=inf;fori=1:nx1=r1(i);x2=r2(i);lpc=lpconst(x1x2)；iflpc=1z=mylp(x1x2)；ifzz0z0=z；sol=x1x2；endendend,与MonteCarlo方法相似，但理论基础不同的方法“拟蒙特卡罗方法”(Quasi-MonteCarlo方法)近年来也获得迅速发展。这种方