数学建模暑假培训- 数学建模中的一些算法广东工业大学应用数学学院陈学松2010-8-11数学建模竞赛中应当掌握的十类算法 ：v1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计 算机仿真来解决问题的算法，同时可以通过模拟来检验自己 模型的正确性，是比赛时必用的方法）v 2、数据拟合、参数估计、插值等数据处理算法（比赛中通 常会遇到大量的数据需要处理，而处理数据的关键就在于这 些算法，通常使用Matlab作为工具）v 3、线性规划、整数规划、多元规划、二次规划等规划类问 题（建模竞赛大多数问题属于最优化问题，很多时候这些问 题可以用数学规划算法来描述，通常使用Lindo、Lingo软件 实现） v4、图论算法（这类算法可以分为很多种，包括最短路、 网络流、二分图等算法，涉及到图论的问题可以用这些方 法解决，需要认真准备）v5、动态规划、回溯搜索、分支定界等计算机算法（这些 算法是算法设计中比较常用的方法，很多场合可以用到竞 赛中）v6、最优化理论的三大非经典算法：模拟退火法、神经网 络、遗传算法（这些问题是用来解决一些较困难的最优化 问题的算法，对于有些问题非常有帮助，但是算法的实现 比较困难，需慎重使用）v7、网格算法和穷举法（网格算法和穷举法都是暴力搜索 最优点的算法，在很多竞赛题中有应用，当重点讨论模型 本身而轻视算法的时候，可以使用这种暴力方案，最好使 用一些高级语言作为编程工具）v8、一些连续离散化方法（很多问题都是实际来的，数据 可以是连续的，而计算机只认的是离散的数据，因此将其 离散化后进行差分代替微分、求和代替积分等思想是非常 重要的）v9、数值分析算法（如果在比赛中采用高级语言进行编程 的话，那一些数值分析中常用的算法比如方程组求解、矩 阵运算、函数积分等算法就需要额外编写库函数进行调用 ）v10、图象处理算法（赛题中有一类问题与图形有关，即 使与图形无关，论文中也应该要不乏图片的，这些图形如 何展示以及如何处理就是需要解决的问题，通常使用 Matlab进行处理） 十类算法的详细说明v1、蒙特卡罗方法（MC）：v蒙特卡罗（Monte Carlo）方法，或称计算机随机模 拟方法，是一种基于“随机数”的计算方法。这一方 法源于美国在第二次世界大战进行研制原子弹的“曼 哈顿计划”。该计划的主持人之一、数学家冯诺伊 曼用驰名世界的赌城摩纳哥的Monte Carlo来命 名这种方法，为它蒙上了一层神秘色彩。v蒙特卡罗方法的基本原理及思想如下：v当所要求解的问题是某种事件出现的概率，或者是某个随 机变量的期望值时，它们可以通过某种“试验”的方法，得 到这种事件出现的频率，或者这个随机变数的平均值，并 用它们作为问题的解。这就是蒙特卡罗方法的基本思想。 蒙特卡罗方法通过抓住事物运动的几何数量和几何特征， 利用数学方法来加以模拟，即进行一种数字模拟实验。它 是以一个概率模型为基础，按照这个模型所描绘的过程， 通过模拟实验的结果，作为问题的近似解。v可以把蒙特卡罗解题归结为三个主要步骤：构造或描述概率过程；实现从已知概率分布抽样；建立各 种估计量。例. 蒲丰氏问题为了求得圆周率值，在十九世纪后期，有很多人作 了这样的试验：将长为2l的一根针任意投到地面上，用针 与一组相间距离为2a（ la）的平行线相交的频率代替 概率P，再利用准确的关系式：求出值v 其中为投计次数，n为针与平行线相交次数。 这就是古典概率论中著名的蒲丰氏问题。v一些人进行了实验，其结果列于下表 ：实验者年份投计次数的实验值沃尔弗(Wolf)185050003.1596斯密思(Smith)185532043.1553福克斯(Fox)189411203.1419拉查里尼 (Lazzarini)190134083.1415929设针投到地面上的位置可以用一组参数（x,）来描述 ，x为针中心的坐标，为针与平行线的夹角，如图所示 。任意投针，就是意味着x与都是任意取的，但x的范围 限于0，a，夹角的范围限于0，。在此情况下 ，针与平行线相交的数学条件是针在平行线间的位置 如何产生任意的（x,）？x在0，a上任意取值 ，表示x在0，a上是均匀分布的，其分布密度 函数为：类似地，的分布密度函数为：因此，产生任意的（x,）的过程就变成了由 f1(x)抽样x及由f2()抽样的过程了。由此得到：其中1，2均为（0,1）上均匀分布的随机变量。 每次投针试验，实际上变成在计算机上从两个均匀分布 的随机变量中抽样得到（x,），然后定义描述针与平行 线相交状况的随机变量s(x,)，为如果投针次，则是针与平行线相交概率的估计值。事实上， 于是有 因此，可以通俗地说，蒙特卡罗方法是用随机试验的方法 计算积分，即将所要计算的积分看作服从某种分布密度函 数f(r)的随机变量(r)的数学期望 通过某种试验，得到个观察值r1，r2，rN（用概率 语言来说，从分布密度函数f(r)中抽取个子样r1，r2， ，rN，），将相应的个随机变量的值g(r1)，g(r2)， g(rN)的算术平均值作为积分的估计值（近似值）。 v用比较抽象的概率语言描述蒙特卡罗方法解题的 步骤如下：构造一个概率空间(W ,A,P)，其中， W 是一个事件集合，A是集合W 的子集，P是在A 上建立的某个概率测度；在这个概率空间中，选 取一个随机变量q (w ), 使得这个随机变量的期望 值正好是所要求的解Q ，然后用q (w )的简单子 样的算术平均值作为Q 的近似值。v举个例子就是97 年的A 题，每个零件都有自己的 标定值，也都有自己的容差等级，而求解最优的 组合方案将要面对着的是一个极其复杂的公式和 108 种容差选取方案，根本不可能去求解析解， 那如何去找到最优的方案呢？随机性模拟搜索最 优方案就是其中的一种方法，在每个零件可行的 区间中按照正态分布随机的选取一个标定值和选 取一个容差值作为一种方案，然后通过蒙特卡罗 算法仿真出大量的方案，从中选取一个最佳的。v另一个例子就是2003年的彩票问题第二问，要求设计一 种更好的方案，首先方案的优劣取决于很多复杂的因素， 同样不可能刻画出一个模型进行求解，只能靠随机仿真模 拟。v蒙特卡罗方法的计算程序：关于蒙特卡罗方法的计算程序已经有很多，如：EGS4、 FLUKA、ETRAN、ITS、MCNP、GEANT等。这些程序 大多经过了多年的发展，花费了巨大的工作量。除欧洲核 子研究中心（CERN）发行的GEANT主要用于高能物理 探测器响应和粒子径迹的模拟外，其它程序都深入到低能 领域，并被广泛应用。2、最优化理论的三大非经典算法v这十几年来最优化理论有了飞速发展，模拟退火法、神经 网络、遗传算法这三类算法发展很快。近几年的赛题越来 越复杂，很多问题没有什么很好的模型可以借鉴，于是这 三类算法很多时候可以派上用场，比如：97 年A 题的模 拟退火算法，00 年B 题的神经网络分类算法，象01 年B 题这种难题也可以使用神经网络，还有美国竞赛89 年A 题也和BP 算法有关系，当时是86 年刚提出BP 算法，89 年就考了，说明赛题可能是当今前沿科技的抽象体现。目 前算法最佳的是遗传算法。遗传算法简介v遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机 化搜索算法，由美国J.Holland教授提出，其主要特点是群体 搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度 信息。它尤其适用于传统搜索方法难于解决的复杂和非线性 问题，可广泛用于组合优化、机器学习、自适应控制、规划 设计和人工生命等领域，是21世纪有关智能计算中的关键技 术之一。v 在人工智能领域中，有不少问题需要在复杂和庞大的搜 索空间中寻找最优解或准最优解。象货郎担问题和规划问题 等组合优化问题就是典型的例子。在求解此类问题时，若不 能利用问题固有知识来缩小搜索空间则会产生搜索的组合爆 炸。v因此，研究能在搜索过程中自动获取和积累有关搜索空间 的知识，并自适应地控制搜索过程，从而得到最优解地通 用搜索方法一直是令人瞩目地课题。遗传算法就是这种特 别有效地算法。生物的进化是一个奇妙的优化过程，它通 过选择淘汰，突然变异，基因遗传等规律产生适应环境变 化的优良物种。遗传算法是根据生物进化思想而启发得出 的一种全局优化算法。尽管遗传算法本身在理论和应用方 法上仍有许多待进一步研究地问题，但它已在很多领域地 应用中展现了其特色和魅力。遗传算法的基本概念v遗传算法的基本思想是基于Darwin进化论和Mendel的遗 传学说的。vDarwin进化论最重要的是适者生存原理。它认为每一物 种在发展中越来越适应环境。物种每个个体的基本特征由 后代所继承，但后代又会产生一些异于父代的新变化。在 环境变化时，只有那些能适应环境的个体特征方能保留下 来。vMendel遗传学说最重要的是基因遗传原理。它认为遗传 以密码方式存在细胞中，并以基因形式包含在染色体内。 每个基因有特殊的位置并控制某种特殊性质；所以，每个 基因产生的个体对环境具有某种适应性。基因突变和基因 杂交可产生更适应于环境的后代。经过存优去劣的自然淘 汰，适应性高的基因结构得以保存下来。v由于遗传算法是由进化论和遗传学机理而产生的直接搜索 优化方法；故而在这个算法中要用到各种进化和遗传学的 概念。这些概念如下：v一、串(String)它是个体(Individual)的形式，在算法中为二进制串，并且 对应于遗传学中的染色体(Chromosome)。v二、群体(Population)个体的集合称为群体，串是群体的元素v三、群体大小(Population Size)在群体中个体的数量称为群体的大小。v四、基因(Gene)基因是串中的元素，基因用于表示个体的特征。例如有一 个串S1011，则其中的1，0，1，1这4个元素分别称为 基因。它们的值称为等位基因(Alletes)。v五 、基因位置(Gene Position)一个基因在串中的位置称为基因位置，有时也简称基因位 。基因位置由串的左向右计算，例如在串S1101中，0 的基因位置是3。基因位置对应于遗传学中的地点(Locus) 。v六、基因特征值(Gene Feature)在用串表示整数时，基因的特征值与二进制数的权一致； 例如在串S=1011中，基因位置3中的1，它的基因特征值 为2；基因位置1中的1，它的基因特征值为8。v七、串结构空间SS在串中，基因任意组合所构成的串的集合。基因操作是在 结构空间中进行的。串结构空间对应于遗传学中的基因型 (Genotype)的集合。v八、参数空间SP这是串空间在物理系统中的映射，它对应于遗传学中的表 现型(Phenotype)的集合。v九、非线性它对应遗传学中的异位显性(Epistasis)v十、适应度(Fitness)表示某一个体对于环境的适应程度。遗传算法的原理 v遗传算法GA把问题的解表示成“染色体”，在算法中也即 是以二进制编码的串。并且，在执行遗传算法之前，给出 一群“染色体”，也即是假设解。然后，把这些假设解置于 问题的“环境”中，并按适者生存的原则，从中选择出较适 应环境的“染色体”进行复制，再通过交叉，变异过程产生 更适应环境的新一代“染色体”群。这样，一代一代地进化 ，最后就会收敛到最适应环境的一个“染色体”上，它就是 问题的最优解。v三、遗传算法的步骤 v1初始化选择一个群体，即选择一个串或个体的集合bi， i=1，2，.n。这个初始的群体也就是问题假设解 的集合。一般取n30-160。通常以随机方法产生串或个体的集合。问题的最 优解将通过这些初始假设解进化而求出。v2选择根据适者生存原则选择下一代的个体。在选择时 ，以适应度为选择原则。适应度准则体现了适者 生存，不适应者淘汰的自然法则。给出目标函数f，则f(bi)称为个体bi的适应度。以为选中bi为下一代个体的次 数。显然：v(1)适应度较高的个体，繁殖下一