数学建模竞赛中应当掌握十类算法省名师优质课赛课获奖课件市赛课一等奖课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢您,数学建模竞赛中应该掌握十类算法：,1、蒙特卡罗算法（该算法又称随机性模拟算法，是经过计算机仿真来处理问题算法，同时能够经过模拟来检验自己模型正确性，是比赛时必用方法）,2、数据拟合、参数预计、插值等数据处理算法（比赛中通常会碰到大量数据需要处理，而处理数据关键就在于这些算法，通常使用Matlab作为工具）,3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题能够用数学规划算法来描述，通常使用Lindo、Lingo软件实现）,第1页,4、图论算法（这类算法能够分为很各种，包含最短路、网络流、二分图等算法，包括到图论问题能够用这些方法处理，需要认真准备）,5、动态规划、回溯搜索、分支定界等计算机算法（这些算法是算法设计中比较惯用方法，很多场所能够用到竞赛中）,6、最优化理论三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来处理一些较困难最优化问题算法，对于有些问题非常有帮助，不过算法实现比较困难，需慎重使用）,7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法时候，能够使用这种暴力方案，最好使用一些高级语言作为编程工具）,第2页,8、一些连续离散化方法（很多问题都是实际来，数据能够是连续，而计算机只认是离散数据，所以将其离散化后进行差分代替微分、求和代替积分等思想是非常主要）,9、数值分析算法（假如在比赛中采取高级语言进行编程话，那一些数值分析中惯用算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）,10、图象处理算法（赛题中有一类问题与图形相关，即使与图形无关，论文中也应该要不乏图片，这些图形怎样展示以及怎样处理就是需要处理问题，通常使用Matlab进行处理）,第3页,十类算法详细说明,1、蒙特卡罗方法（MC）,（Monte Carlo）：,蒙特卡罗（Monte Carlo）方法，或称计算机随机模拟方法，是一个基于“随机数”计算方法。这一方法源于美国在第二次世界大战进行研制原子弹“曼哈顿计划”。该计划主持人之一、数学家冯诺伊曼用驰名世界赌城摩纳哥Monte Carlo来命名这种方法，为它蒙上了一层神秘色彩。,第4页,蒙特卡罗方法基本原理及思想以下：,当所要求解问题是某种事件出现概率，或者是某个随机变量期望值时，它们能够经过某种“试验”方法，得到这种事件出现频率，或者这个随机变数平均值，并用它们作为问题解。这就是蒙特卡罗方法基本思想。蒙特卡罗方法经过抓住事物运动几何数量和几何特征，利用数学方法来加以模拟，即进行一个数字模拟试验。它是以一个概率模型为基础，按照这个模型所描绘过程，经过模拟试验结果，作为问题近似解。,能够把蒙特卡罗解题归结为三个主要步骤：,结构或描述概率过程；实现从已知概率分布抽样；建立各种预计量。,第5页,例.蒲丰氏问题,为了求得圆周率值，在十九世纪后期，有很多人作了这么试验：将长为,2l,一根针任意投到地面上，用针与一组相间距离为,2a,（,l,a,）平行线相交频率代替概率,P,，再利用准确关系式：,求出值,其中,为投计次数，,n,为针与平行线相交次数。这就是古典概率论中著名蒲丰氏问题。,第6页,一些人进行了试验，其结果列于下表,：,试验者,年份,投计次数,试验值,沃尔弗(Wolf),1850,5000,3.1596,斯密思(Smith),1855,3204,3.1553,福克斯(Fox),1894,1120,3.1419,拉查里尼(Lazzarini),1901,3408,3.1415929,第7页,设针投到地面上位置能够用一组参数（,x,）来描述，,x,为针中心坐标，,为针与平行线夹角，如图所表示。,任意投针，就是意味着,x,与,都是任意取，但,x,范围限于0，,a,，夹角,范围限于0，,。在此情况下，针与平行线相交数学条件是,针在平行线间位置,第8页,怎样产生任意,（,x,）,？,x,在,0，,a,上任意取值，表示,x,在,0，,a,上是均匀分布，其分布密度函数为：,类似地，,分布密度函数为：,所以，产生任意,（,x,）,过程就变成了由,f,1,(,x,)抽样,x,及由,f,2,(,)抽样,过程了。由此得到：,其中,1,，,2,均为（0,1）上均匀分布随机变量。,第9页,每次投针试验，实际上变成在计算机上从两个均匀分布随机变量中抽样得到,（,x,），,然后定义描述针与平行线相交情况随机变量,s,(,x,),，为,假如投针,次，则,是针与平行线相交概率,预计值。实际上，,于是有,第10页,所以，能够通俗地说，蒙特卡罗方法是用随机试验方法计算积分，即将所要计算积分看作服从某种分布密度函数,f,(,r,)随机变量,(,r,)数学期望,经过某种试验，得到,个观察值,r,1,，,r,2,，,r,N,（用概率语言来说，从分布密度函数,f,(,r,)中抽取,个子样,r,1,，,r,2,，,r,N,，），将对应,个随机变量值,g,(,r,1,)，,g,(,r,2,)，,g,(,r,N,)算术平均值,作为积分预计值（近似值）。,第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教授提出，其主要特点是群体搜索策略和群体中个体之间信息交换，搜索不依赖于梯度信息。它尤其适合用于传统搜索方法难于处理复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是21世纪相关智能计算中关键技术之一。,在人工智能领域中，有不少问题需要在复杂和庞大搜索空间中寻找最优解或准最优解。象货郎担问题和规划问题等组合优化问题就是经典例子。在求解这类问题时，若不能利用问题固有知识来缩小搜索空间则会产生搜索组合爆炸。,第15页,所以，研究能在搜索过程中自动获取和积累相关搜索空间知识，并自适应地控制搜索过程，从而得到最优解地通用搜索方法一直是令人瞩目地课题。遗传算法就是这种尤其有效地算法。生物进化是一个奇妙优化过程，它经过选择淘汰，突然变异，基因遗传等规律产生适应环境改变优良物种。遗传算法是依据生物进化思想而启发得出一个全局优化算法。尽管遗传算法本身在理论和应用方法上仍有许多待深入研究地问题，但它已在很多领域地应用中展现了其特色和魅力。,第16页,遗传算法基本概念,遗传算法基本思想是基于Darwin进化论和Mendel遗传学说。,Darwin进化论最主要是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体基本特征由后代所继承，但后代又会产生一些异于父代新改变。在环境改变时，只有那些能适应环境个体特征方能保留下来。,Mendel遗传学说最主要是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊位置并控制某种特殊性质；所以，每个基因产生个体对环境含有某种适应性。基因突变和基因杂交可产生更适应于环境后代。经过存优去劣自然淘汰，适应性高基因结构得以保留下来。,因为遗传算法是由进化论和遗传学机理而产生直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学概念。这些概念以下：,第17页,一、串(String),它是个体(Individual)形式，在算法中为二进制串，而且对应于遗传学中染色体(Chromosome)。,二、群体(Population),个体集合称为群体，串是群体元素,三、群体大小(Population Size),在群体中个体数量称为群体大小。,四、基因(Gene),基因是串中元素，基因用于表示个体特征。比如有一个串S1011，则其中1，0，1，1这4个元素分别称为基因。它们值称为等位基因(Alletes)。,五、基因位置(Gene Position),一个基因在串中位置称为基因位置，有时也简称基因位。基因位置由串左向右计算，比如在串S1101中，0基因位置是3。基因位置对应于遗传学中地点(Locus)。,第18页,六、基因特征值(Gene Feature),在用串表示整数时，基因特征值与二进制数权一致；比如在串S=1011中，基因位置3中1，它基因特征值为2；基因位置1中1，它基因特征值为8。,七、串结构空间SS,在串中，基因任意组合所组成串集合。基因操作是在结构空间中进行。串结构空间对应于遗传学中基因型(Genotype)集合。,八、参数空间SP,这是串空间在物理系统中映射，它对应于遗传学中表现型(Phenotype)集合。,九、非线性,它对应遗传学中异位显性(Epistasis),十、适应度(Fitness),表示某一个体对于环境适应程度。,第19页,遗传算法原理,遗传算法GA把问题解表示成“染色体”，在算法中也即是以二进制编码串。而且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题“环境”中，并按适者生存标准，从中选择出较适应环境“染色体”进行复制，再经过交叉，变异过程产生更适应环境新一代“染色体”群。这么，一代一代地进化，最终就会收敛到最适应环境一个“染色体”上，它就是问题最优解。,第20页,一、遗传算法目标,经典遗传算法CGA(Canonical Genetic Algorithm)通惯用于处理下面这一类静态最优化问题：,考虑对于一群长度为L二进制编码bi，i1，2，n；有,bi0,1,给定目标函数f，有f(bi)，而且,0f(bi),同时f(bi)f(bi+1),求满足下式,maxf(bi)|bi0,1 bi。,很显著，遗传算法是一个最优化方法，它经过进化和遗传机理，从给出原始解群中，不停进化产生新解，最终收敛到一个特定串bi处，即求出最优解。,第21页,二、遗传算法基本原理,长度为Ln个二进制串bi(i1，2，n)组成了遗传算法初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体基因。依据进化术语，对群体执行操作有三种：,1选择(Selection),这是从群体中选择出较适应环境个体。这些选中个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。因为在选择用于繁殖下一代个体时，是依据个体对环境适应度而决定其繁殖量，故而有时也称为非均匀再生(differential reproduction)。,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=100101,S2=010111,选择它们左边3位进行交叉操作，则有,S1=010101,S2=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全局最优收敛(Convergence to the global optimum),当最优个体适应度到达给定阀值，或者最优个体适应度和群体适应度不再上升时，则算法迭代过程收敛、算法结束。不然，用经过选择、交叉、变异所得到新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。,遗传算法基本处理流程图以下：,第27页,二、遗传算法应用关键,遗传算法在应用中最关键问题有以下3个,1串编码方式,这本质是问题编码。普通把问题各种参数用二进制编码，组成子串；然后把子串拼接组成“染色体”串。串长度及编码形式对算法收敛影响极大。,2适应函数确实定,适应函数(fitness function)也称对象函数(object function)，这是问题求解品质测量函数；往往也称为问题“环境”。普通能够把问题模型函数作为对象函数；但有时需要另行结构。,3遗传算法本身参数设定,遗传算法本身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。,群体大小n太小时难以求出最优解，太大则增加收敛时间。普通n30-160。交叉概率Pc太小时难以向前搜索，太大则轻易破坏高适应值结构。普通取Pc=0.25-0.75。变异概率Pm太小时难以产生新基因结构，太大使遗传算法成了单纯随机搜索。普通取Pm00102。,第28页,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指定精度),第29页,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)等同于initializegaoptions参数，第三个参数控制是否输出，普通为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,第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,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次遗传迭代,第31页,运算结果为：x=7.8562 24.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页,所以，问题数学模型是一个双目标优化：,minz,1,=Q(x),minz,2,=-R(x),s.t,第34页,二、模型求解,对于上述双目标优化模型这类问题大多用某种方式化为单目标问题来求解，主要有以下三种：（1）固定风险水平，优化收益；（2）固定赢利水平，极小化风险；（3）确定投资者对风方法险收益相对偏好系数。前（1）、（2）两种方法分别是以牺牲某一目标来到达另一目标优化，而对第三种则因为决议者极难知道偏好系数详细值。故这三种方法都不太理想，下面我们考虑用遗传算法来处理这个问题。,因为在双目标情况下，两目标通常本质上是相互矛盾，最优解需要替换为非劣解，即对于任何目标函数在不牺牲其它目标情况下就不能改进解。,第35页,三个定义,定义1：非劣解：可行解,定义2：正理想解：正理想解由全部可到达最好目标值组成,定义3：负理想解：负理想解由全部可到达最坏目标值组成,我们考虑用遗传算法产生整个非劣解集合，或近似集合，然后让决议者自己来选择最好地表示他对各个目标权衡取舍非劣解。对于这个双目标规划问题可采取自适应移动线技术建立一个求加权和方法，这种方法可迫使遗传搜索去探索目标空间中非劣解集合。,第36页,总步骤：,步骤1：结构染色体，产生初始种群：选取二进制编码，随机产生一组染色体x,k,放入集合E中,步骤2：染色体交叉，对上面产生种群按交叉概率p,c,选择“个体对”进行单点交叉。普通取p,c,从0.25到1.00之间。,步骤3：染色体变异：为使群体保持多样性，可按变异率p,m,进行变异（可随机选择变异点）,步骤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页,