国赛必备算法————蒙特卡洛算法

01

蒙特卡罗方法的基本思想

通常蒙特卡罗方法可以粗略地分成两类:

一类是所求解的问题本身具有内在的随机性，借助计算机的运算能力可以直接模拟这种随机的过程。

例如在核物理研究中，分析中子在反应堆中的传输过程。中子与原子核作用受到量子力学规律的制约，人们只能知道它们相互作用发生的概率，却无法准确获得中子与原子核作用时的位置以及裂变产生的新中子的行进速率和方向。科学家依据其概率进行随机抽样得到裂变位置、速度和方向，这样模拟大量中子的行为后，经过统计就能获得中子传输的范围，作为反应堆设计的依据。

另一种类型是所求解问题可以转化为某种随机分布的特征数。

比如随机事件出现的概率，或者随机变量的期望值。通过随机抽样的方法，以随机事件出现的频率估计其概率,或者以抽样的数字特征估算随机变量的数字特征，并将其作为问题的解。这种方法多用于求解复杂的多维积分问题。

02

随机算法的两类：

• 蒙特卡罗算法:采样越多，越近似最优解;

• 拉斯维加斯算法:采样越多，越有机会找到最优解;

蒙特卡罗算法:假如框里有100个苹果,让我每次闭眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个.....我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法——尽量找好的，但不保证是最好的。

拉斯维加斯算法，则是另-种情况。假如有一把锁，给我100把钥匙，只有1把是对的。于是我每次随机拿1把钥匙去试，打不开就再换1把。我试的次数越多，打开(最优解)的机会就越大，但在打开之前，那些错的钥匙都是没有用的。这个试钥匙的算法，就是拉斯维加斯的——尽量找最好的，但不保证能找到。

03

蒙特卡洛求定积分

蒙特卡洛的一个重要应用就是求定积分。

当我们在[a,b]之间随机取一点x时，它对应的函数值就是f(x)。接下来我们就可以用f(x)*(b-a)来粗略估计曲线下方的面积，也就是我们需要求的积分值，当然这种估计（或近似）是非常粗略的。

在此图中，做了四次随机采样，得到了四个随机样本xl，x2，x3,x4,并且得到了这四个祥本的f(x)的値分別为f(x1)，f(x2)，f(x3)，f(x4).对于这四个样本,毎个样本能求一个近似的面积値，大小为f(xi)*(b-a).对照图下面那部分很容易理解，毎个样本都是对原函数f的近似，所以我们认为f(x)的值一直都等于f(xi)

按照图中的提示，求出上述面积的数学期望，就完成了蒙特卡洛积分。如果用数学公式表达上述过程:

S=1/4*(f(x1)(b-a)+ f(x2)(b-a)+ f(x3)(b -a)+ f(x4)(b- a)

=1/4*(b - a)(f(x1)+ f(x2)+ f(x3)+ f(x4))

=1/4*(b-a)

对于更一般的情况，假设要计算的积分如下：

其中被积函数g(x)在[a,b]内可积，如果选择一个概率密度函数为fx(x)的方式进行抽样，并且满足，那么令g*(x)=g(x)/f(x)，原有的积分可以写成以下形式：

那么我们求积分的步骤应该是：

1. 产生服从分布律Fx的随机变量Xi(i=1,2,....,N)

2. 计算均值

此时有

当然实际应用中，我们最常用的还是取fx为均匀分布

此时

带入积分表达式有：

如果在直观上理解这个式子就非常简洁明了:

在[a,b]区间上按均匀分布取N个随机样本Xi，计算g(Xi)并取均值，得到的相当于Y坐标值，然后乘以(b-a)为X坐标长度，得到的即为对应矩形的面积，即积分值。

04

利用蒙特卡洛模拟解决非线性规划问题

求maxf(x)=x1x2x3的约束条件为：

解：

我们将其转化为三维问题得

maxf(x)=(x2+10)x2x3的约束条件为

MATLAB语句为：（我们让其生成31265个随机数）

n=31625;

x20=[];x30=[];vmax=-inf;

x2=unifrnd(10,20,n,1);

x3=unifrnd(-5,16,n,1);

forj=1:n

fork=1:n

ifx2(j)+2*x3(k)-10>=0 & ...

3*x2(j)+2*x3(k)-62<=0;

v=(x2(j)+10)*x2(j)*x3(k);

ifv>vmax

vmax-x;

x20=x2(j);

x30=x3(k);

end

end

end

x=[x20+10,x20,x30],vmax

通过计算得出以下结果

2.5846 12.5846 2.1230

vmax=

因为蒙特卡洛模拟的随机性，每次得出的结果不尽相同，上面是抽取的一次结果。对于这类问题，求解的方法不唯一，但是大致思路都是产生足够数量的随机数，然后用约束条件检验这些随机数是否符合要求，最后代入目标函数即为所求。

蒙特卡洛模拟的缺点是时间开支大、浪费资源且精度不太高，但蒙特卡洛模拟在很多情况下都是求解问题的唯一方法。

注：文章转载需注明，任何未经允许转载，皆视为侵权

BONUS TIME

数学建模资料、视频讲解、历年赛题

后台回复 【校苑】领取

高教社出版

数学考试分析（2022版）

整书205页

文末附电子版免费领取

话不多说！免费获取方式！

扫描下方公众号二维码，回复：考研

不是留言！不是留言！不是留言！

整理不易！各位宝子们且领且珍惜！

历年赛题的重要性

有了这个！

下一个上岸的就是你！

100G MATLAB资料

后台回复 【干货】领取