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

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