数学建模常用算法

数学建模常用算法第1页，课件共63页，创作于2023年2月数学建模常用算法/方法1、数据拟合与插值2、回归分析法3、规划/优化问题（线性规划，非线性规划，整数规划，动态规划，目标规划）4、图论法5、聚类分析、判别分析6、模糊数学相关问题评判方法7、时间序列方法8、灰色理论方法9、先进优化算法（遗传算法，神经网络）第2页，课件共63页，创作于2023年2月1、数据拟合与插值方法问题—给定一批数据点（输入变量与输出变量的数据），需确定满足特定要求的曲线或曲面插值问题—要求所求曲线（面）通过所给所有数据点数据拟合—不要求曲线（面）通过所有数据点，而是要求它反映对象整体的变化趋势第3页，课件共63页，创作于2023年2月数据拟合一元函数拟合多项式拟合非线性函数拟合多元函数拟合（回归分析）MATLAB实现(拟合工具箱cftool)确定出拟合函数，进而计算任一点的函数值，可以用于预测第4页，课件共63页，创作于2023年2月插值方法一维插值的定义—已知n个节点，求任意点处的函数值。分段线性插值多项式插值样条插值y=interp1(x0,y0,x,'method')二维插值—节点为网格节点z=interp2(x0,y0,z0,x,y,'method')pp=csape({x0,y0},z0,conds,valconds)二维插值—节点为散点z1=griddata(x,y,z,x1,y1)

第5页，课件共63页，创作于2023年2月2、回归分析回归分析—对具有相关关系的现象，根据其关系形态，选择一个合适的数学模型，用来近似地表示变量间的平均变化关系的一种统计方法（一元线性回归、多元线性回归、非线性回归）回归分析在一组数据的基础上研究这样几个问题：建立因变量与自变量之间的回归模型（经验公式）对回归模型的可信度进行检验判断每个自变量对因变量的影响是否显著判断回归模型是否适合这组数据利用回归模型对进行预报或控制[b,bint,r,rint,stats]=regress(Y,X,alpha)（线性回归）rstool（x，y，’model’,alpha）（多元二项式回归）[beta,r,J]=nlinfit（x，y，’model’,beta0）（非线性回归）第6页，课件共63页，创作于2023年2月逐步回归分析逐步回归分析—从一个自变量开始，视自变量作用的显著程度，从大到地依次逐个引入回归方程当引入的自变量由于后面变量的引入而变得不显著时，要将其剔除掉引入一个自变量或从回归方程中剔除一个自变量，为逐步回归的一步对于每一步都要进行值检验，以确保每次引入新的显著性变量前回归方程中只包含对作用显著的变量这个过程反复进行，直至既无不显著的变量从回归方程中剔除，又无显著变量可引入回归方程时为止stepwise(x,y,inmodel,alpha)SPSS,SAS第7页，课件共63页，创作于2023年2月3、规划/优化模型分类线性规划模型（目标函数和约束条件都是线性函数的优化问题）非线性规划模型（目标函数或者约束条件是非线性的函数）整数规划（决策变量是整数值得规划问题）多目标规划（具有多个目标函数的规划问题）动态规划（求解多阶段决策问题的最优化方法）

第8页，课件共63页，创作于2023年2月规划/优化模型四要素决策变量目标函数（建模的核心，尽量简单、光滑）约束条件（建模的关键部分）求解方法（MATLAB,LINDO）第9页，课件共63页，创作于2023年2月规划/优化模型求解(matlab)无约束规划fminsearchfminbnd线性规划linprog 非线性规划fmincon多目标规划（计算有效解）目标加权、效用函数动态规划（倒向、正向）整数规划（分支定界法、枚举法、Lingo、Lindo）第10页，课件共63页，创作于2023年2月4、图论方法最短路问题两个指定顶点之间的最短路径—给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线（Dijkstra算法）每对顶点之间的最短路径（Dijkstra算法、Floyd算法）最小生成树问题连线问题—欲修筑连接多个城市的铁路设计一个线路图，使总造价最低（prim算法、Kruskal算法）图的匹配问题人员分派问题：n个工作人员去做件n份工作，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？(匈牙利算法)第11页，课件共63页，创作于2023年2月图论方法遍历性问题中国邮递员问题—邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线—旅行商问题最大流问题运输问题最小费用最大流问题在运输问题中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案第12页，课件共63页，创作于2023年2月5、聚类分析聚类分析—所研究的样本或者变量之间存在程度不同的相似性，要求设法找出一些能够度量它们之间相似程度的统计量作为分类的依据，再利用这些量将样本或者变量进行分类系统聚类分析—将n个样本或者n个指标看成n类，一类包括一个样本或者指标，然后将性质最接近的两类合并成为一个新类，依此类推。最终可以按照需要来决定分多少类，每类有多少样本（指标）第13页，课件共63页，创作于2023年2月系统聚类分析步骤系统聚类方法步骤：计算n个样本两两之间的距离构成n个类，每类只包含一个样品合并距离最近的两类为一个新类计算新类与当前各类的距离（新类与当前类的距离等于当前类与组合类中包含的类的距离最小值），若类的个数等于1，转5，否则转3画聚类图决定类的个数和类。第14页，课件共63页，创作于2023年2月分解聚类分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。目标函数两类均值方差

N：总样本数，：ω1类样本数：ω2类样本数，第15页，课件共63页，创作于2023年2月分解聚类框图：初始分类调整分类方案最终结果目标函数达到最优先？第16页，课件共63页，创作于2023年2月K-均值聚类分析K-meansCluster

又称为快速样本聚类法，是非系统聚类中最常用的聚类法。优点：是占内存少、计算量小、处理速度快，特别适合大样本的聚类分析。缺点：应用范围有限，要求用户制定分类数目(要告知)，只能对观测量（样本）聚类第17页，课件共63页，创作于2023年2月基本原理具体做法1、按照指定的分类数目n，按某种方法选择某些观测量，设为{Z1，Z2，…Zn}，作为初始聚心。2、计算每个观测量到各个聚心的欧氏距离。即按就近原则将每个观测量选入一个类中，然后计算各个类的中心位置，即均值，作为新的聚心。3、使用计算出来的新聚心重新进行分类，分类完毕后继续计算各类的中心位置，作为新的聚心，如此反复操作，直到两次迭代计算的聚心之间距离的最大改变量小于初始聚类心间最小距离的倍数时，或者到达迭代次数的上限时，停止迭代。第18页，课件共63页，创作于2023年2月判别分析判别分析—在已知研究对象分成若干类型，并已取得各种类型的一批已知样品的观测数据，在此基础上根据某些准则建立判别式，然后对未知类型的样品进行判别分类。距离判别法—首先根据已知分类的数据，分别计算各类的重心，计算新个体到每类的距离，确定最短的距离（欧氏距离、马氏距离）Fisher判别法—利用已知类别个体的指标构造判别式（同类差别较小、不同类差别较大），按照判别式的值判断新个体的类别Bayes判别法—计算新给样品属于各总体的条件概率，比较概率的大小，然后将新样品判归为来自概率最大的总体第19页，课件共63页，创作于2023年2月6、模糊数学相关的问题模糊数学—研究和处理模糊性现象的数学（概念与其对立面之间没有一条明确的分界线）第20页，课件共63页，创作于2023年2月6、模糊数学相关的问题模糊聚类分析—根据研究对象本身的属性构造模糊矩阵，在此基础上根据一定的隶属度来确定其分类关系模糊层次分析法—两两比较指标的确定模糊综合评判—综合评判就是对受到多个因素制约的事物或对象作出一个总的评价，如产品质量评定、科技成果鉴定、某种作物种植适应性的评价等，都属于综合评判问题。由于从多方面对事物进行评价难免带有模糊性和主观性，采用模糊数学的方法进行综合评判将使结果尽量客观从而取得更好的实际效果第21页，课件共63页，创作于2023年2月第22页，课件共63页，创作于2023年2月第23页，课件共63页，创作于2023年2月第24页，课件共63页，创作于2023年2月第25页，课件共63页，创作于2023年2月第26页，课件共63页，创作于2023年2月第27页，课件共63页，创作于2023年2月7、时间序列分析建模时间序列是按时间顺序排列的、随时间变化且相互关联的数据序列—通过对预测目标自身时间序列的处理，来研究其变化趋势（长期趋势变动、季节变动、循环变动、不规则变动）自回归模型一般自回归模型AR(n)—系统在时刻t的响应X(t)仅与其以前时刻的响应X(t-1),…，X(t-n)有关，而与其以前时刻进入系统的扰动无关移动平均模型MA(m)—系统在时刻t的响应X(t)

，与其以前任何时刻的响应无关，而与其以前时刻进入系统的扰动a(t-1),…,a(t-m)存在着一定的相关关系自回归移动平均模型

ARMA(n,m)—系统在时刻t的响应X(t)，不仅与其前n个时刻的自身值有关，而且还与其前m个时刻进入系统的扰动存在一定的依存关系第28页，课件共63页，创作于2023年2月时间序列建模的基本步骤（1）数据的预处理：数据的剔取及提取趋势项取n=1，拟合ARMA(2n,2n-1)（即ARMA(2,1)）模型n=n+1，拟合ARMA(2n,2n-1)模型用F准则检验模型的适用性。若检验显著，则转入第2步。若检验不显著，转入第5步。检查远端时刻的系数值的值是否很小，其置信区间是否包含零。若不是，则适用的模型就是ARMA(2n,2n-1)

。若很小，且其置信区间包含零，则拟合ARMA(2n-1,2n-2)

。第29页，课件共63页，创作于2023年2月时间序列建模的基本步骤（2）利用F准则检验模型ARMA(2n,2n-1)和ARMA(2n-1,2n-2)，若F值不显著，转入第7步；若F值显著，转入第8步。舍弃小的MA参数，拟合m<2n-2的模型ARMA(2n-1,m)

，并用F准则进行检验。重复这一过程，直到得出具有最小参数的适用模型为止舍弃小的MA参数，拟合m<2n-1的模型ARMA(2n,m)

，并用F准则进行检验。重复这一过程，直到得出具有最小参数的适用模型为止。第30页，课件共63页，创作于2023年2月8、灰色理论

1982年我国学者邓聚龙创立了灰色系统理论，模糊数学着重研究“认知不确定”问题，概率统计研究的是“随机不确定”现象的历史统计规律。灰色系统研究的是“部分信息明确，部分信息未知”的“小样本，贫信息”不确定性系统，它通过对已知“部分”信息的生成去开发了解、认识现实世界。第31页，课件共63页，创作于2023年2月灰色预测模型GM(1,1)预测模型步骤：1、对于原始数列，做一次累加得，其中2、计算并得到，

第32页，课件共63页，创作于2023年2月3、计算参数向量4、将参数a,b代入响应函数，得到累加序列预测值5、由累加序列得到原始序列预测值第33页，课件共63页，创作于2023年2月GM(1,1)主要用于单调序列，灰色预测模型除GM(1,1)之外，还有:残差GM(1,1)模型对于非单调的摆动发展序列或有饱和的S形序列，可建立GM(2,1)，DGM和Verhulst模型区间预测灰色灾变预测(波形预测)系统预测

第34页，课件共63页，创作于2023年2月灰色理论除了用于预测之外，还包含:灰色决策灰色人工神经网络模型灰色动态规划灰色控制灰色聚类评估

第35页，课件共63页，创作于2023年2月9、先进优化算法遗传算法神经网络微粒群算法PSO模拟退火算法

第36页，课件共63页，创作于2023年2月遗传算法传统的优化方法（局部优化）共轭梯度法、拟牛顿法、单纯形方法全局优化方法漫步法（RandomWalk）、模拟退火法、GA关于优化问题比较：传统的优化方法

1）依赖于初始条件。

2）与求解空间有紧密关系，促使较快地收敛到局部解，但同时对解域有约束，如可微或连续。利用这些约束，收敛快。

3）有些方法，如Davison-Fletcher-Powell直接依赖于至少一阶导数；共轭梯度法隐含地依赖于梯度。第37页，课件共63页，创作于2023年2月全局优化方法1）不依赖于初始条件；2）不与求解空间有紧密关系，对解域，无可微或连续的要求。求解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况第38页，课件共63页，创作于2023年2月⑴选择运算⑵交换操作⑶变异遗传算法的基本运算遗传算法基本原理模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量——染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。第39页，课件共63页，创作于2023年2月●选择运算——从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。选择方法——适应度比例法（转轮法）按各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率：Pcxi为种群中第i个染色体，第40页，课件共63页，创作于2023年2月具体步骤1）计算各染色体适应度值2）累计所有染色体适应度值，记录中间累加值S-mid和最后累加值sum=∑f(xi)3）产生一个随机数N，0〈N〈sum4）选择对应中间累加值S-mid的第一个染色体进入交换集

5）重复（3）和（4），直到获得足够的染色体。第41页，课件共63页，创作于2023年2月●交换操作

方法:随机选择二个染色体(双亲染色体),随机指定一点或多点,进行交换,可得二个新的染色体(子辈染色体).新的子辈染色体:A’11010001B’01011110模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低.●变异复制不能创新,交换解决染色体的创新第42页，课件共63页，创作于2023年2月GA的流程第43页，课件共63页，创作于2023年2月简单遗传算法（GA）的基本参数①种群规模P:参与进化的染色体总数.②代沟G:二代之间不相同的染色体数目,无重叠G=1;

有重叠0<G<1③选择方法:转轮法,精英选择法,竞争法.④交换率:Pc一般为60~100%.⑤变异率:Pm一般为0.1~10%

Matlab已有GA工具箱:Gatool第44页，课件共63页，创作于2023年2月人工神经网络

二十世纪八十年代，人工神经网络取得了重大进展，发展成为一门介于物理、数学、计算机科学、神经生物学之间的交叉学科。这门学科的发展对目前和未来的科学技术的发展将有重要的影响。

第45页，课件共63页，创作于2023年2月人工神网络基本原理

从具体的一个神经元来说，就是要建立一个数学模型，描述对输入讯号的整和输出过程。从全局来看，多个神经元构成一个网络，必须给出如下三方面的要素：（1）对单个人工神经给出某种形式定义；（2）决定网络中神经元的数量及彼此间的联结方式。或者说，定义网络结构；（3）给出一种方法，决定元与元之间的联结强度，使网络具有某种预定功能。第46页，课件共63页，创作于2023年2月多层前馈BP神经网络

单个处理单元可以执行简单的功能，更强的识别处理能力却来自多个结点“连成”的网络，也就是人工神经网络。最简单的网络是把一组几个结点形成一层，图1中，左边的黑色圆点只起着分配输入信号的作用，没有计算作用，所以不看作网络的一层，右边用圆圈表示的一组结点则被看作一层。输入信号可表示为行向量X=（x1，x3，...xn），其中每一分量通过加权连接到各结点。每一结点均可产生一个输入的加权和。一般，大而复杂的网络能提供更强的计算能力。虽然目前已构成了很多模型，但它们的结点都是按层排列的，这一点正是模仿了大脑皮层中的网络模块。构成多层网络，只要将单层网络进行级联就可以了，即一层的输出作为下一层的输入。图2是两层网络。

第47页，课件共63页，创作于2023年2月对于一个多层网络，如何求得一组恰当的权值，使网络具有特定的功能，在很长一段时间内，曾经是使研究工作者感到困难的一个问题，直到1985年，美国加州大学的一个研究小组提出了多层前传网络的向后传播算法（Back—Propagation），使问题有了重大进展。下面介绍这一算法。

图1单层人工神经网络图2两层人工神经网络第48页，课件共63页，创作于2023年2月人工神经网络含有若干个信息输入和一个输出，并含有一个称之为激活函数的计算单元。典型的激励函数有Sigmoid函数、双曲正切函数、线性函数、阶跃函数等（如图3），其中Sigmoid函数构成的人工神经网络结构较为复杂，但Sigmoid函数是递增的，它的导数不为零，因此比其他几种激励函数有更好的特性。Sigmoid函数在BP学习中是一个强有力的工具。图3用于处理单元的几种常用激励函数（a）线性函数（b）斜坡函数（c）阶跃函数（d）符号函数（e）Sigmoid函数（f）双曲正切函数第49页，课件共63页，创作于2023年2月第50页，课件共63页，创作于2023年2月第51页，课件共63页，创作于2023年2月梯度搜索的步长，称为学习速率。越大，权值修改越剧烈。通常按这样的法则选取：即在不导致振荡的前提下尽可能取较大的。为使足够大而又不易产生振荡，常在式中再加一项“惯性项”(momentumitem)，即：（14.12）其中为一常数，它决定过去的权值变化对当前权值变化的影响的大小。下面给出的BP算法是在假定网络为多层前向网络，网络激发函数为Sigmoid函数时给出的，并且阈值也作同样的训练。

第52页，课件共63页，创作于2023年2月第53页，课件共63页，创作于2023年2月第54页，课件共63页，创作于2023年2月其他神经网络RBF神经网络遗传神经网络第55页，课件共63页，创作于2023年2月人工神经网络的优点及局限性

与其他类型的计算方法，人工神经网络具有一些明显的优点，但它并不是万能的。对于一个明智的工程技术人员来讲，在应用人工神经网络时，应同时了解其优点与局限性，以便能更好地确定人工神经网络对特定问题的适用性。

人工神经网络的优点：人工神经网络只不过是另一种计算机建模工具而已，但与一些著名的、传统的计算机建模方法相比，具有一些明显的优点。这些优点包括：

(1)自适应性：人工神经网络具有对周围环境的自适应或学习的能力。当给人工神经网络以输入-输出模式时，它可以通过自我调整使误差达到最小，即通过训练进行学习。对于某些难以参数化的因素，可以通过训练，自动总结规律。第56页，课件共63页，创作于2023年2月

(2)容错性：在输入-输出模式中混入错误信息，对整体不会带来严重的影响。与传统的经验曲线拟合模型相比，人工神经网络对噪声和不完整信息的敏感程度要低。原因是：在经验模型中，每一自变量通常都起重要作用，但在人工神经网络中，每一个节点只反映问题的一个微特征，因此，如果某一节点的输入不完整或带有噪声，这一输入在人工神经网络中所体现出的影响不会那么严重。人工神经网络能够处理不完善的问题，能比其他适用性差的经验模型更有效地归纳、得出实质性结论。

(3)模式识别性能：人工神经网络能够很好地完成多变量模式识别。第57页，课件共63页，创作于2023年2月

(4)外推性：人工神经网络有较好的外推性，即从训练中，从部分样本中学到