20世纪的十大算法

在看周国标的《数值计算》这本书,发现第一章导论里面有一个20世纪十大算法的介绍,所以感兴趣就做了一个小小的摘录和总结,其中的思想我想还是很值得反复推敲的,从下面的这些算法的作者可以得出一个结论:一个优秀的算法设计者必然拥有扎实的数学基础。先拿蒙特卡洛方法开个头,后面会陆续补充上对其他算法详细解释。归纳起来,这些算法既有对过去算法效率的提高,也有对科学计算精度的改进,各有千秋。虽然已经是几十年前的产物了,但是现代科学的各个领域却无不渗透这些算法影子,足见其魅力之大。

本世纪初,美国物理学会(American Institute of Physics)和IEEE计算机社团 (IEEE Computer Society)的一本联合刊物《科学与工程中的计算》发表了由田纳西大学的Jack Dongarra和橡树岭国家实验室的Francis Sullivan 联名撰写的“二十世纪十大算法”一文,该文“试图整理出在20世纪对科学和工程领域的发展产生最大影响力的十大算法”。作者苦于“任何选择都将是充满争议的,因为实在是没有最好的算法”,他们只好用编年顺序依次列出了这十项算法领域人类智慧的巅峰之作——给出了一份没有排名的算法排行榜。有趣的是,该期杂志还专门邀请了这些算法相关领域的“大拿”为这十大算法撰写十篇综述文章,实在是蔚为壮观。本文的目的,便是要带领读者走马观花,一同回顾当年这一算法界的盛举。

一、1946 蒙特卡洛方法
[1946: John von Neumann, Stan Ulam, and Nick Metropolis, all at the Los Alamos Scientific Laboratory, cook up the Metropolis algorithm, also known as the Monte Carlo method.]

1946年,美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis共同发明,被称为蒙特卡洛方法。

1.历史起源

蒙特卡罗方法于20世纪40年代美国在第二次世界大战中研制原子弹的“曼哈顿计划”计划的成员S.M.乌拉姆和J.冯·诺伊曼首先提出。数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的Monte Carlo—来命名这种方法,为它蒙上了一层神秘色彩。在这之前,蒙特卡罗方法就已经存在。1777年,法国Buffon提出用投针实验的方法求圆周率∏。这被认为是蒙特卡罗方法的起源。

2.   蒙特卡罗方法的基本思想

这个问题最初的模型是:
在广场上画一个边长一米的正方形,在正方形内部随意用粉笔画一个不规则的形状,现在要计算这个不规则图形的面积,怎么计算呢?蒙特卡洛(Monte Carlo)方法告诉我们,均匀的向该正方形内撒N(N 是一个很大的自然数)个黄豆,随后数数有多少个黄豆在这个不规则几何形状内部,比如说有M个,那么,这个奇怪形状的面积便近似于M/N,N越大,算出来的值便越精确。在这里我们要假定豆子都在一个平面上,相互之间没有重叠。

一个很有趣的例子是:蒙特卡洛方法可用于近似计算圆周率:让计算机每次随机生成两个0到1之间的数,看这两个实数是否在单位圆内。生成一系列随机点,统计单位圆内的点数与总点数,(圆面积和正方形面积之比为PI:1,PI为圆周率),当随机点取得越多(但即使取10的9次方个随机点时,其结果也仅在前4位与圆周率吻合)时,其结果越接近于圆周率。

这种方法是以概率统计理论为指导的一类非常重要的数值计算方法,同时也依赖于电子计算机的发明和发展而逐步成熟。因为其中涉及到很多的随机过程,因此必须依赖高效准确的随机数生成方法或者程序。(如果大家对随机数的研究感兴趣的话,可以参考这篇文章

蒙特卡罗方法的解题过程可以归结为三个主要步骤:构造或描述概率过程;实现从已知概率分布抽样;建立各种估计量
蒙特卡罗方法解题过程的三个主要步骤:
(1)构造或描述概率过程
对于本身就具有随机性质的问题,如粒子输运问题,主要是正确描述和模拟这个概率过 程,对于本来不是随机性质的确定性问题,比如计算定积分,就必须事先构造一个人为的概率过程,它的某些参量正好是所要求问题的解。即要将不具有随机性质的问题转化为随机性质的问题。
(2)实现从已知概率分布抽样
构造了概率模型以后,由于各种概率模型都可以看作是由各种各样的概率分布构成的,因此产生已知概率分布的随机变量(或随机向量),就成为实现蒙特卡罗方法模拟实验的基本手段,这也是蒙特卡罗方法被称为随机抽样的原因。最简单、最基本、最重要的一个概率分布是(0,1)上的均匀分布(或称矩形分布)。随机数就是具有这种均匀分布的随机变量。随机数序列就是具有这种分布的总体的一个简单子样,也就是一个具有这种分布的相互独立的随机变数序列。产生随机数的问题,就是从这个分布的抽样问题。在计算机上,可以用物理方法产生随机数,但价格昂贵,不能重复,使用不便。另一种方法是用数学递推公式产生。这样产生的序列,与真正的随机数序列不同,所以称为伪随机数,或伪随机数序列。不过,经过多种统计检验表明,它与真正的随机数,或随机数序列具有相近的性质,因此可把它作为真正的随机数来使用。由已知分布随机抽样有各种方法,与从(0,1)上均匀分布抽样不同,这些方法都是借助于随机序列来实现的,也就是说,都是以产生随机数为前提的。由此可见,随机数是我们实现蒙特卡罗模拟的基本工具。
(3)建立各种估计量
一般说来,构造了概率模型并能从中抽样后,即实现模拟实验后,我们就要确定一个随机变量,作为所要求的问题的解,我们称它为无偏估计。建立各种估计量,相当于对模拟实验的结果进行考察和登记,从中得到问题的解。
借助计算机技术,蒙特卡罗方法实现了两大优点:
一是简单,省却了繁复的数学推导和演算过程,使得一般人也能够理解和掌握
二是快速。简单和快速,是蒙特卡罗方法在现代项目管理中获得应用的技术基础。
蒙特卡罗方法有很强的适应性,问题的几何形状的复杂性对它的影响不大。该方法的收敛性是指概率意义下的收敛,因此问题维数的增加不会影响它的收敛速度,而且存贮单元也很省,这些是用该方法处理大型复杂问题时的优势。因此,随着电子计算机的发展和科学技术问题的日趋复杂,蒙特卡罗方法的应用也越来越广泛。它不仅较好地解决了多重积分计算、微分方程求解、积分方程求解、特征值计算和非线性方程组求解等高难度和复杂的数学计算问题,而且在统计物理、核物理、真空技术、系统科学 、信息科学、公用事业、地质、医学,可靠性及计算机科学等广泛的领域都得到成功的应用。

3. 蒙特卡罗方法的特点

1)能够比较逼真地描述具有随机性质的事物的特点及物理实验过程

从这个意义上讲,蒙特卡罗方法可以部分代替物理实验,甚至可以得到物理实验难以得到的结果。用蒙特卡罗方法解决实际问题,可以直接从实际问题本身出发,而不从方程或数学表达式出发。它有直观、形象的特点。

2)收敛速度与问题的维数无关

由误差定义可知,在给定置信水平情况下,蒙特卡罗方法的收敛速度与问题本身的维数无关。维数的变化,只引起抽样时间及估计量计算时间的变化,不影响误差。也就是说,使用蒙特卡罗方法时,抽取的子样总数N与维数s无关。维数的增加,除了增加相应的计算量外,不影响问题的误差。这一特点,决定了蒙特卡罗方法对多维问题的适应性。而一般数值方法,比如计算定积分时,计算时间随维数的幂次方而增加,而且,由于分点数与维数的幂次方成正比,需占用相当数量的计算机内存,这些都是一般数值方法计算高维积分时难以克服的问题。

3)具有同时计算多个方案与多个未知量的能力

对于那些需要计算多个方案的问题,使用蒙特卡罗方法有时不需要像常规方法那样逐个计算,而可以同时计算所有的方案,其全部计算量几乎与计算一个方案的计算量相当。例如,对于屏蔽层为均匀介质的平板几何,要计算若干种厚度的穿透概率时,只需计算最厚的一种情况,其他厚度的穿透概率在计算最厚一种情况时稍加处理便可同时得到。

另外,使用蒙特卡罗方法还可以同时得到若干个所求量。例如,在模拟粒子过程中,可以同时得到不同区域的通量、能谱、角分布等,而不像常规方法那样,需要逐一计算所求量。

4)误差容易确定

对于一般计算方法,要给出计算结果与真值的误差并不是一件容易的事情,而蒙特卡方法则不然。根据蒙特卡罗方法的误差公式,可以在计算所求量的同时计算出误差。对干很复杂的蒙特卡罗方法计算问题,也是容易确定的。一般计算方法常存在着有效位数损失问题,而要解决这一问题有时相当困难,蒙特卡罗方法则不存在这一问题。

4.蒙特卡罗方法的主要应用范围

蒙特卡罗方法所特有的优点,使得它的应用范围越来越广。它的主要应用范围包括:粒子输运问题,统计物理,典型数学问题,真空技术,激光技术以及医学,生物,探矿等方面。随着科学技术的发展,其应用范围将更加广泛。

蒙特卡罗方法在粒子输运问题中的应用范围主要包括:实验核物理,反应堆物理,高能物理等方面。

蒙特卡罗方法在实验核物理中的应用范围主要包括:通量及反应率,中子探测效率,光子探测效率,光子能量沉积谱及响应函数,气体正比计数管反冲质子谱,多次散射与通量衰减修正等方面。

总结一下,蒙特卡洛方法最核心的思想就是将难以精确计算的问题,通过随机数来推算其概率密度分布函数,然后通过期望来估计要计算的值。蒙特卡洛最主要的优势是在多重积分计算的时候,可以保持线性复杂度,虽然常规数值积分在精度上会高于蒙特卡洛方法,但是随着被积函数维度的增加,复杂度会指数增长,这时蒙特卡洛方法的优势就突显了。当年冯诺依曼在主导曼哈顿计划的时候就大力推广这种方法,足见其在大型工程计算上的优势。

发表评论

电子邮件地址不会被公开。 必填项已用*标注