数学建模竞赛中应当掌握的十类算法ppt课件

数学建模暑假培训 - 数学建模中的一些算法,数学建模竞赛中应当掌握的十类算法 ：,1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，是比赛时必用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现）,2,4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具）,3,8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理）,4,十类算法的详细说明,1、蒙特卡罗方法（MC）： 蒙特卡罗（Monte Carlo）方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第二次世界大战进行研制原子弹的“曼哈顿计划”。该计划的主持人之一、数学家冯诺伊曼用驰名世界的赌城摩纳哥的Monte Carlo来命名这种方法，为它蒙上了一层神秘色彩。,5,蒙特卡罗方法的基本原理及思想如下： 当所要求解的问题是某种事件出现的概率，或者是某个随机变量的期望值时，它们可以通过某种“试验”的方法，得到这种事件出现的频率，或者这个随机变数的平均值，并用它们作为问题的解。这就是蒙特卡罗方法的基本思想。蒙特卡罗方法通过抓住事物运动的几何数量和几何特征，利用数学方法来加以模拟，即进行一种数字模拟实验。它是以一个概率模型为基础，按照这个模型所描绘的过程，通过模拟实验的结果，作为问题的近似解。 可以把蒙特卡罗解题归结为三个主要步骤： 构造或描述概率过程；实现从已知概率分布抽样；建立各种估计量。,6,例. 蒲丰氏问题,为了求得圆周率值，在十九世纪后期，有很多人作了这样的试验：将长为2l的一根针任意投到地面上，用针与一组相间距离为2a（ la）的平行线相交的频率代替概率P，再利用准确的关系式： 求出值 其中为投计次数，n为针与平行线相交次数。这就是古典概率论中著名的蒲丰氏问题。,7,一些人进行了实验，其结果列于下表 ：,8,设针投到地面上的位置可以用一组参数（x,）来描述，x为针中心的坐标，为针与平行线的夹角，如图所示。 任意投针，就是意味着x与都是任意取的，但x的范围限于0，a，夹角的范围限于0，。在此情况下，针与平行线相交的数学条件是,针在平行线间的位置,9,如何产生任意的（x,）？x在0，a上任意取值，表示x在0，a上是均匀分布的，其分布密度函数为： 类似地，的分布密度函数为： 因此，产生任意的（x,）的过程就变成了由f1(x)抽样x及由f2()抽样的过程了。由此得到： 其中1，2均为（0,1）上均匀分布的随机变量。,10,每次投针试验，实际上变成在计算机上从两个均匀分布的随机变量中抽样得到（x,），然后定义描述针与平行线相交状况的随机变量s(x,)，为 如果投针次，则 是针与平行线相交概率的估计值。事实上， 于是有,11,因此，可以通俗地说，蒙特卡罗方法是用随机试验的方法计算积分，即将所要计算的积分看作服从某种分布密度函数f(r)的随机变量(r)的数学期望 通过某种试验，得到个观察值r1，r2，rN（用概率语言来说，从分布密度函数f(r)中抽取个子样r1，r2，rN，），将相应的个随机变量的值g(r1)，g(r2)，g(rN)的算术平均值 作为积分的估计值（近似值）。,12,用比较抽象的概率语言描述蒙特卡罗方法解题的步骤如下：构造一个概率空间(W ,A,P)，其中，W 是一个事件集合，A是集合W 的子集，P是在A上建立的某个概率测度；在这个概率空间中，选取一个随机变量q (w ), 使得这个随机变量的期望值正好是所要求的解Q ，然后用q (w )的简单子样的算术平均值作为Q 的近似值。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。,13,另一个例子就是2003年的彩票问题第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 蒙特卡罗方法的计算程序： 关于蒙特卡罗方法的计算程序已经有很多，如：EGS4、FLUKA、ETRAN、ITS、MCNP、GEANT等。这些程序大多经过了多年的发展，花费了巨大的工作量。除欧洲核子研究中心（CERN）发行的GEANT主要用于高能物理探测器响应和粒子径迹的模拟外，其它程序都深入到低能领域，并被广泛应用。,14,2、最优化理论的三大非经典算法,这十几年来最优化理论有了飞速发展，模拟退火法、神经网络、遗传算法这三类算法发展很快。近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场，比如：97 年A 题的模拟退火算法，00 年B 题的神经网络分类算法，象01 年B 题这种难题也可以使用神经网络，还有美国竞赛89 年A 题也和BP 算法有关系，当时是86 年刚提出BP 算法，89 年就考了，说明赛题可能是当今前沿科技的抽象体现。目前算法最佳的是遗传算法。,15,遗传算法简介,遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，由美国J.Holland教授提出，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它尤其适用于传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是21世纪有关智能计算中的关键技术之一。 在人工智能领域中，有不少问题需要在复杂和庞大的搜索空间中寻找最优解或准最优解。象货郎担问题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，若不能利用问题固有知识来缩小搜索空间则会产生搜索的组合爆炸。,16,因此，研究能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程，从而得到最优解地通用搜索方法一直是令人瞩目地课题。遗传算法就是这种特别有效地算法。生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。尽管遗传算法本身在理论和应用方法上仍有许多待进一步研究地问题，但它已在很多领域地应用中展现了其特色和魅力。,17,遗传算法的基本概念,遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。 Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来。 Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：,18,一、串(String) 它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。 二、群体(Population) 个体的集合称为群体，串是群体的元素 三、群体大小(Population Size) 在群体中个体的数量称为群体的大小。 四、基因(Gene) 基因是串中的元素，基因用于表示个体的特征。例如有一个串S1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。 五 、基因位置(Gene Position) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。,19,六、基因特征值(Gene Feature) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。 七、串结构空间SS 在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。 八、参数空间SP 这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。 九、非线性 它对应遗传学中的异位显性(Epistasis) 十、适应度(Fitness) 表示某一个体对于环境的适应程度。,20,遗传算法的原理,遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。,21,三、遗传算法的步骤 1初始化 选择一个群体，即选择一个串或个体的集合bi，i=1，2，.n。这个初始的群体也就是问题假设解的集合。一般取n30-160。 通常以随机方法产生串或个体的集合。问题的最优解将通过这些初始假设解进化而求出。 2选择 根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。 给出目标函数f，则f(bi)称为个体bi的适应度。以 为选中bi为下一代个体的次数。,22,显然： (1)适应度较高的个体，繁殖下一代的数目较多。 (2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。 这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。 选择的方法有： 适应度比例法 期望值法 排位次法 精华保存法,23,3交叉 对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。 例如有个体 S1=100101 S2=010111 选择它们的左边3位进行交叉操作，则有 S1=010101 S2=100111 一般而言，交叉概率P，取值为0.250.75。,24,4变异 根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。 例如有个体S101011。 对其的第1，4位置的基因进行变异，则有 S=001111 单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。,25,5全局最优收敛(Convergence to the global optimum) 当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。 遗传算法基本处理流程图如下：,26,二、遗传算法的应用关键 遗传算法在应用中最关键的问题有如下3个 1串的编码方式 这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。 2适应函数的确定 适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。 3遗传算法自身参数设定 遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。 群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm00102。,27,matlab遗传算法工具箱函数及实例讲解,核心函数： (1)function pop=initializega(num,bounds,eevalFN,eevalOps,options)-初始种群的生成函数 【输出参数】 pop-生成的初始种群 【输入参数】 num-种群中的个体数目 bounds-代表变量的上下界的矩阵 eevalFN-适应度函数 eevalOps-传递给适应度函数的参数 options-选择编码形式(浮点编码或是二进制编码)precision F_or_B,如 precision-变量进行二进制编码时指定的精度 F_or_B-为1时选择浮点编码，否则为二进制编码,由precision指定精度),28,2)function x,endPop,bPop,traceInfo = ga(bounds,evalFN,evalOps,startPop,opts,. termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)-遗传算法函数 【输出参数】 x-求得的最优解 endPop-最终得到的种群 bPop-最优种群的一个搜索轨迹 【输入参数】 bounds-代表变量上下界的矩阵 evalFN-适应度函数 evalOps-传递给适应度函数的参数 startPop-初始种群 optsepsilon prob_ops display-opts(1:2)等同于initializega的options参数，第三个参数控制是否输出，一般为0。如1e-6 1 0 termFN-终止函数的名称,如maxGenTerm termOps-传递给终止函数的参数,如100 selectFN-选择函数的名称,如normGeomSelect selectOps-传递给选择函数的参数,如0.08 xOverFNs-交叉函数名称表，以空格分开，如arithXover heuristicXover simpleXover xOverOps-传递给交叉函数的参数表，如2 0;2 3;2 0 mutFNs-变异函数表，如boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation mutOps-传递给交叉函数的参数表,如4 0 0;6 100 3;4 100 3;4 0 0,29,【问题】求f(x)=x+10*sin(5x)+7*cos(4x)的最大值，其中0=x=9 【分析】选择二进制编码，种群中的个体数目为10，二进制编码长度为20，交叉概率为0.95,变异概率为0.08 【程序清单】 %编写目标函数 functionsol,eval=fitness(sol,options) x=sol(1); eval=x+10*sin(5*x)+7*cos(4*x); %把上述函数存储为fitness.m文件并放在工作目录下 initPop=initializega(10,0 9,fitness);%生成初始种群，大小为10 x endPop,bPop,trace=ga(0 9,fitness,initPop,1e-6 1 1,maxGenTerm,25,normGeomSelect,. 0.08,arithXover,2,nonUnifMutation,2 25 3) %25次遗传迭代,30,运算结果为：x = 7.8562 24.8553(当x为7.8562时，f（x）取最大值24.8553) 注：1、遗传算法一般用来取得近似最优解，而不是最优 解。 2、matlab工具箱函数必须放在工作目录下,31,3、数据拟合、参数估计、插值等算法,数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的走向进行处理。此类问题在MATLAB中有很多现成的函数可以调用，熟悉MATLAB，这些方法都能游刃有余的用好。,32,4、规划类问题算法,竞赛中很多问题都和数学规划有关，可以说不少的模型都可以归结为一组不等式作为约束条件、几个函数表达式作为目标函数的问题，遇到这类问题，求解就是关键了，比如98年B 题，用很多不等式完全可以把问题刻画清楚，因此列举出规划后用Lindo、Lingo 等软件来进行解决比较方便，所以还需要熟悉这两个软件。,33,例：2009年“电工杯”A题,34,5、图论问题,98 年B 题、00 年B 题、95 年锁具装箱等问题体现了图论问题的重要性，这类问题算法有很多，包括：最大流，二分匹配等问题。每一个算法都应该实现一遍，否则到比赛时再写就晚了。,35,6、计算机算法设计中的问题,计算机算法设计包括很多内容：动态规划、回溯搜索、分治算法、分支定界。比如92 年B 题用分枝定界法，97 年B 题是典型的动态规划问题，此外98 年B 题体现了分治算法。这方面问题和ACM 程序设计竞赛中的问题类似，推荐看一下计算机算法设计与分析（电子工业出版社）等与计算机算法有关的书。,36,7、网格算法和穷举算法,网格算法和穷举法一样，只是网格法是连续问题的穷举。比如要求在N 个变量情况下的最优化问题，那么对这些变量可取的空间进行采点，计算量很大。比如97 年A 题、99 年B 题都可以用网格法搜索，这种方法最好在运算速度较快的计算机中进行，还有要用高级语言来做，最好不要用MATLAB 做网格，否则会算很久的。,37,8、一些连续数据离散化的方法,大部分物理问题的编程解决，都和这种方法有一定的联系。物理问题是反映我们生活在一个连续的世界中，计算机只能处理离散的量，所以需要对连续量进行离散处理。这种方法应用很广，而且和上面的很多算法有关。事实上，网格算法、蒙特卡罗算法、模拟退火都用了这个思想。,38,9、数值分析算法,这类算法是针对高级语言而专门设的，如果你用的是MATLAB、Mathematica，大可不必准备，因为象数值分析中有很多函数一般的数学软件是具备的,39,10、图象处理算法,01 年A 题中需要你会读BMP 图象、美国赛98 年A 题需要你知道三维插值计算，03 年B 题要求更高，不但需要编程计算还要进行处理，而数模论文中也有很多图片需要展示，因此图象处理就是关键。做好这类问题，重要的是把MATLAB 学好，特别是图象处理的部分。,40,