数学建模竞赛中应当掌握十类算法市公开课金奖市赛课一等奖课件.pptx

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