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