【算法学习】蒙特卡洛方法

Li Shen

蒙特卡罗方法也称统计模拟方法,是1940年代中期由于科学技术的发展和电子计算机的发明,而提出的一种以概率统计理论为指导的数值计算方法。是指使用随机数(或更常见的伪随机数)来解决很多计算问题的方法。
20世纪40年代,在冯·诺伊曼,斯塔尼斯拉夫·乌拉姆和尼古拉斯·梅特罗波利斯在洛斯阿拉莫斯国家实验室为核武器计划工作时,发明了蒙特卡罗方法。因为乌拉姆的叔叔经常在摩纳哥的蒙特卡洛赌场输钱得名,而蒙特卡罗方法正是以概率为基础的方法。
与它对应的是确定性算法。

 

由于是以赌场命名,我在学习的过程中也遇到了另一个以赌场命名的算法:拉斯维加斯方法。这两者都是统计方法,之间的区别可以概括为:蒙特卡罗算法:采样越多,越近似最优解;拉斯维加斯算法:采样越多,越有机会找到最优解。通俗易懂的来理解的话,比方说,小孩走丢了,然后发布寻人启事,那么这个时候我们要找的这个人是确定且唯一的(最优解),那么随着采样数量增加,理想情况下我们就越接近我们要找的人。这个场景就类似于拉斯维加斯算法。而当一家公司在招聘员工时,对某个职位有种种要求,随着面试的人越来越多,公司HR就越容易从pool中找到接近“完美”的候选人。这个就类似于蒙特卡洛算法。两种算法应用场景不同,蒙特卡洛算法可以应用于一些模拟过程,民意调查等等,换句话说,我们在这种情况下不是一定需要最优解,或者我们不知道最优解是哪个,我们可能只需要一个范围。而拉斯维加斯算法则侧重于寻找exact存在的最优解。

 

举一个蒙特卡洛方法的一个经典例子,求π。假设我们有一个边长为1的正方形,然后里面有1/4个圆,像这样:

已知正方形的边长和圆的半径为1,圆面积公式为 S = π*R²。 我们知道 S/4:S(正方形) = (π*R²)/4:1。换句话说,如果我们往正方形里随机画点,那么落入1/4圆的点的数量:所有正方形内部的点的数量就等于π/4。那么π = P(点在圆内)*4。随着点的数量增加,π就会越来越精确。 用python实现一下:

 

import math
import random

a = 1   # 边长
r = 1   # 半径
total = 100 # 画点数
counts = 0   
for i in range(total):
    x = random.random()
    y = random.random()
    distance = math.sqrt(x**2+y**2)
    if distance < 1:
        counts+=1
print(4*(counts/total))

# t = 100时, 十个结果为3.12,3.04,3.0,2.96,3.12,3.24,3.6,3.0,3.08,3.32

# t = 10000时, 3.1344, 3.1264, 3.1256, 3.154, 3.1564, 3.1564, 3.1864, 3.1136, 3.1404, 3.1656

# t = 1000000时, 3.14274, 3.144116, 3.14046, 3.143208, 3.140392, 3.142568, 3.140988, 3.140816, 3.144748, 3.14096

用箱线图粗略看一下就可以看出,随着采样量的增加,最终结果也越来越接近3.141......这样一个结果。

125

July 31, 2019, 3:56 a.m.

Comments:

You haven't logged in yet, Please Log in or Signup.

No Comments.