数学建模常见算法编程实现PPT课件.pptx

1、数学建模常见算法及其实现数学建模常见算法及其实现单击此处添加副标题CONTENTS目录1评价与分类算法概述及实现层次分析法、神经网络、模糊综合2数据预处理算法概述及实现插值、拟合、异常值提取3预测类赛题算法概述及实现灰色预测算法、时间序列预测、小波预测4优化类赛题算法概述及实现线性规划、智能呢个算法1ONE评价类赛题算法概述及实现1.1 层次分析法基本思想：是定性与定量相结合的多准则决策、评价方法。将决策的有关元素分解成目标层、准则层和方案层，并通过人们的判断对决策方案的优劣进行排序，在此基础上进行定性和定量分析。它把人的思维过程层次化、数量化，并用数学为分析、决策、评价、预报和控制提供定量的

2、依据。 基本步骤：构建层次结构模型；构建成对比较矩阵；层次单排序及一致性检验（即判断主观构建的成对比较矩阵在整体上是否有较好的一致性）；层次总排序及一致性检验（检验层次之间的一致性）典型赛题：小美同学因为魅力比较大，追他的男生比较多，他就陷入了选择纠结中，你能否帮助他找出你认为最合适的伴侣？解题引导：（1）何时用层次分析法？（2）层次分析法到底是啥步骤？（3）如何实现？1.1 层次分析法（1）何时用层次分析法？层次分析法主要适用于比较简单的评价类问题，问题已经给出若干可供选择的对象，评价标准体系比较模糊，并没有形成统一的标准，或者标准不唯一，标准体系中指标数据不易定量获取（2）层次分析法到底是

3、啥步骤？第一步：选择好评价对象和指标体系第二步：构建判断矩阵第三步：计算得出结果（3）如何实现？编程和软件实现1.1 层次分析法案例解决：（1）选择好评价对象和指标体系待选对象：小李、小张、小王评价指标：财富、人品、成绩、健康水平、长相、身高（2）构建判断矩阵第一个判断矩阵：指标体系之间的第二个判断矩阵：针对某个指标各对象之间的（3）编程实现，相乘即可1.1 层次分析法注意点： 当遇到因素众多，规模较大的评价问题时，该模型容易出现问题，它要求评价者对问题的本质、包含的要素及其相互之间的逻辑关系能掌握得十分透彻，否则评价结果就不可靠和准确。 如果评价指标个数过多（一般超过9个），利用层次分析法所

4、得到的权重就有一定的偏差，继而组合评价模型的结果就不再可靠。可以根据评价对象的实际情况和特点，利用一定的方法，将各原始指标分层和归类，使得每层各类中的指标数少于9个。1.1 层次分析法基本思想：是以模糊数学为基础，应用模糊关系合成的原理，将一些边界不清、不易定量的因素定量化，从多个因素对被评价事物隶属等级（或称为评语集）状况进行综合性评价的一种方法。综合评判对评判对象的全体，根据所给的条件，给每个对象赋予一个非负实数评判指标，再据此排序择优。 基本步骤：确定因素集、评语集；构造模糊关系矩阵；确定指标权重；进行模糊合成和做出评价。 1.2 模糊综合评价法典型问题：某同学想购买一台电脑，他关心电脑

5、的以下几个指标：“运算功能（数值、图形等）”；“存储容量（内、外存）”；“运行速度（CPU、主板等）”；“外设配置（网卡、调制调解器、多媒体部件等）”；“价格”。于是请同宿舍同学一起去买电脑。 1.2 模糊综合评价法（1）何时用模糊综合评价法？模糊综合评价法主要适用于评价结果并无明显的量级之分，评价标准也相对模糊，它具有结果清晰,系统性强的特点,能较好地解决模糊的、 难以量化的问题,适合各种非确定性问题的解决。（2）模糊综合评价法到底是啥步骤？第一步：建立综合评价因素集及评价结果集第二步：通过调查获得因素评价集和结果集的权重第三步：计算得出结果（3）如何实现？编程和软件实现1.2 模糊综合评价

6、法案例解决：（1）建立综合评价因素集及评价结果集评价因素集：运算功能、存储容量、运行速度、外设配置、价格评价结果集：很受欢迎、较受欢迎、不太受欢迎、不受欢迎（2）进行单因素模糊评价，获得评价矩阵第一步构建单因素模糊评价矩阵B：仅仅靠点评实现第二步构建各因素权重A：靠常识构建（3）B*A即可1.2 模糊综合评价法基本思想：是一种交互式的评价方法，它可以根据用户期望的输出不断修改指标的权值，直到用户满意为止。因此，一般来说，人工神经网络评价方法得到的结果会更符合实际情况。 基本步骤：神经网络主要分为训练与仿真两部分，训练指的是利用已知标签数据训练神经网络的连接权重，构建稳定的传输关系；仿真指的是当

7、获取了一个未知标签的新样本后，利用前面已经训练好的稳定的传输关系得出标签结果。1.3 BP神经网络综合评价法典型问题：已知北京电影学院的女生魅力值主要由三部分构成，成绩、人品和颜值，目前计算机学院准备开发一款魅力值自动评估软件，已知若干历届魅力大赛评估得到的数据，请根据该数据实现对小美、小丽、小花的评估。1.3 BP神经网络综合评价法选手成绩人品颜值结果A909070女神B8010090女神C1007070靓妹D708070靓妹E607060大妈F506070大妈（1）何时用BP神经网络算法？神经网络评价模型具有自适应能力、可容错性，能够处理非线性、非局域性的大型复杂系统。在对学习样本训练中，

8、无需考虑输入因子之间的权系数，ANN通过输入值与期望值之间的误差比较，沿原连接权自动地进行调节和适应，因此该方法体现了因子之间的相互作用。（2）模糊综合评价法到底是啥步骤？第一步：先找到评价数据里面的指标层和目标层第二步：利用带标签的数据进行网络的训练第三步：将未知标签数据带入训练好的网络中仿真即可（3）如何实现？编程和工具箱实现1.3 BP神经网络综合评价法案例解决：（1）评价数据里面的指标层和目标层指标层：成绩、人品和颜值目标层：女神、靓妹、大妈（2）利用带标签的数据进行网络的训练训练时首先进行数据归一化处理，然后判断输入层神经元、隐层神经元和输出层神经元个数，最后对各类参数进行设置即可（

9、3）将小美、小丽、小花数据进行评估即可1.3 BP神经网络综合评价法 “类”指的是具有相似性的集合。聚类是指将数据集划分为若干类，使得类内之间的数据最为相似，各类之间的数据相似度差别尽可能大。聚类分析就是以相似性为基础，对数据集进行聚类划分，属于无监督学习。 监督学习知道从对象（数据）中学习什么，而无监督学习无需知道所要搜寻的目标，它是根据算法得到数据的共同特征。比如用分类和聚类来说，分类事先就知道所要得到的类别，而聚类则不一样，只是以相似度为基础，将对象分得不同的簇。 基本思想：开始将每个样本自成一类，然后求两两之间的距离。将距离最近的一类分成一类。如此重复，直到所有样本都合为一类为止。1.

10、4 距离聚类18d1k2jkikji)xx()x,x(dd1kjkikjixx)x,x(dq/1d1kqjkikji)xx()x,x(d1.4 连续型属性的相似性计算方法q=2q=1欧氏距离（Euclidean distance）欧氏距离（Euclidean distance）欧氏距离（Euclidean distance）k-means算法是一种简单的迭代型聚类算法，采用距离作为相似性指标，从而发现给定数据集中的K个类，且每个类的中心是根据类中所有值的均值得到，每个类用聚类中心来描述。对于给定的一个包含n个d维数据点的数据集X以及要分得的类别K,选取欧式距离作为相似度指标，聚类目标是使得各类

11、的聚类平方和最小，即最小化1.5 K-均值聚类K-means是一个反复迭代的过程，算法分为四个步骤：1） 选取数据空间中的K个对象作为初始中心，每个对象代表一个聚类中心；2） 对于样本中的数据对象，根据它们与这些聚类中心的欧氏距离，按距离最近的准则将它们分到距离它们最近的聚类中心（最相似）所对应的类；3） 更新聚类中心：将每个类别中所有对象所对应的均值作为该类别的聚类中心，计算目标函数的值；4） 判断聚类中心和目标函数的值是否发生改变，若不变，则输出结果，若改变，则返回2）。1.5 K-均值聚类 在实际中，常常要处理由实验或测量所得到的一些离散数据。插值与拟合方法就是要通过这些数据去确定某一类

12、已知函数的参数或寻求某个近似函数，使所得到的近似函数与已知数据有较高的拟合精度。 如果要求这个近似函数（曲线或曲面）经过所已知的所有数据点，则称此类问题为插值问题。 （不需要函数表达式） 如果不要求近似函数通过所有数据点，而是要求它能较好地反映数据变化规律的近似函数的方法称为数据拟合。（必须有函数表达式） 近似函数不一定（曲线或曲面）通过所有的数据点。1.6 数据的补全Matlab 实现：实现分段线性插值不需要编制函数程序，它自身提供了内部的功能函数 interp1(一维插值) intep2(二维) interp3(三维) intern(n维) 1.6 数据的补全 突变信号又称奇异信号，突变信

13、号的突变点经常携带比较重要的信息,是信号的重要特征之一。在数字信号处理和数字图像处理中具有非常重要的作用和地位，信号的突变性检测是先对原信号在不同尺度上进行“磨光”，再对磨光后信号的一阶或二阶倒数检测其极值点或过零点。对信号进行磨光处理，主要是为了消除噪声而不是边缘。 传统的信号突变检测方法是基于傅立叶变换的，由某一函数的傅立叶变换趋近于零的快慢来推断该函数是否具有突变性，但它只能反映信号的整体突变性，而对信号的局部突变则无法描述。这样我们就引入小波变换算法。1.7 数据异常值的提取先讲一下傅里叶变换1.7 数据异常值的提取先讲一下傅里叶变换1.7 数据异常值的提取先讲一下傅里叶变换1.74

14、数据异常值的提取先讲一下傅里叶变换1.7 数据异常值的提取小波变换1.7 数据异常值的提取3ONE预测类赛题算法概述及实现3.1 灰色预测算法灰色预测就是在灰色系统中所作的预测。那什么是灰色系统呢？所谓的灰色系统其实就是夹杂在白色系统和黑色系统之中的一种系统，而白色系统就是全部信息已知的系统，黑色系统就是全部信息未知的系统。所以，夹在这两种系统中间的灰色系统就是部分信息已知，而部分信息也是未知的系统。所以灰色预测就是通过这样的信息前提下做的一种预测分析。灰色预测通过鉴别个因素之间的差异程度，进行关联分析，对原始数据处理后生成一定规律性的序列，然后建立相应的微分方程模型，从而预测事物未来的发展趋

15、势，最后得到其发展的模型。3.1 灰色预测算法（1）何时用灰色预测算法？适用范围：预测模型是一个指数函数，如果待测量是以某一指数规律发展的，则可望得到较高精度的预测结果。影响模型预测精度及其适应性的关键因素，是模型中背景值的构造及预测公式中初值的选取。（2）灰色预测算法到底是啥步骤？第一步：找到原始的预测序列第二步：带入程序替换即可第三步：计算得出结果（3）如何实现？编程和软件实现3.1 灰色预测算法经典案例随着生产的发展、消费的扩大，市场需求通常总是增加的，一个商店、一个地区的销售额常常呈增长趋势. 因此，这些数据符合建立灰色预测模型的要求。表7.2列出了某公司19992003年逐年的销售额

16、.试用建立预测模型，预测2004年的销售额，要求作精度检验。GM(1,1)的建模步骤如下：3.1 灰色预测算法3.2 时间序列分析算法基本思想：把预测对象的历史数据按一定的时间间隔进行排列，构成一个随时间变化的统计序列，建立相应的数据随时间变化的变化模型，并将该模型外推到未来进行预测。 适用范围：此方法有效的前提是过去的发展模式会延续到未来，因而这种方法对短期预测效果比较好，而不适合作中长期预测。一般来说，若影响预测对象变化各因素不发生突变，利用时间序列分析方法能得到较好的预测结果；若这些因素发生突变，时间序列法的预测结果将受到一定的影响。3.2 时间序列预测算法（1）时间序列预测算法特点？序

17、列中的数据或数据点的位置依赖于时间，即数据的取值依赖于时间的变化，但不一定是时间t的严格函数。每一时刻的取值或数据点的位置具有一定的随机性，不可能完全准确地用历史数据预测。前后时刻（不一定是相邻时刻）的数值或数据点的位置有一定的相关性，这种相关性就是系统的动态规律性。从整体上看，时间序列往往呈现出某种趋势性或出现周期性变化的现象。 因此，建立时间序列模型，首先应当仔细分析对象性质，判断其是否满足建模的基本条件。若不满足，应做适当调整。3.2 时间序列预测算法（1）时间序列的常用模型AR（自回归）模型MA（移动平均）模型ARMA（自回归移动平均）模型ARIMA（求和自回归移动平均）模型3.2 时

18、间序列预测算法（1）时间序列预测算法解题步骤？1.获取被观测系统时间序列数据；2.对数据绘图，观测是否为平稳时间序列；对于非平稳时间序列要先进行d阶差分运算，化为平稳时间序列；3.经过第二步处理，已经得到平稳时间序列。要对平稳时间序列分别求得其自相关系数ACF 和偏自相关系数PACF ，通过对自相关图和偏自相关图的分析，得到最佳的阶层 p 和阶数 q4.检验模型的有效性。如果拟合模型通不过检验，转向步骤3，重新选择模型再拟合。5.模型优化。如果拟合模型通过检验，仍转向步骤2，充分考虑各种可能，建立多个拟合模型，从所有通过检验的拟合模型中选择最优模型。6.利用拟合模型，预测序列的将来走势。3.3

19、 小波神经网络预测算法小波变换：一种数学分析的工具 小波变换+人工神经网络=小波神经网络小波神经网络是一种以BP神经网络拓扑结构为基础，把小波基函数作为隐含层结点的传递函数，信号前向传播的同时误差反向传播的神经网络。3.1 小波神经网络预测算法 在传统的神经网络中，存在隐层单元数目难以确定的不足，而小波神经网络的隐层单元数目则可以 按如下方法自适应地确定： 首先取小波神经网络的隐层单元数目M为1，学习迭代若干次后，如满足误差条件，则停止迭带，若达到最大学习次数后，仍不满足误差条件，则小波变换单元数目增加1，重复上述过程，直到满足误差条件为止。这样就可以根据具体的问题自适应地确定小波变化单元个数

20、，从而克服传统神经网络的不足。3.1 小波神经网络预测算法(1)小波变换通过尺度伸缩和平移对信号进行多尺度分析，能有效提取信号的局部信息(2)神经网络具有自学习、自适应和容错性等特点，并且是一类通用函数逼近器。(3)小波神经网络的基元和整个结构是依据小波分析理论确定的，可以避免BP神经网络等结构设计上的盲目性(4)小波神经网络有更强的学习能力，精度更高对同样的学习任务，小波神经网络结构更简单，收敛速度更快4ONE优化类赛题算法概述及实现4.1 基本规划性模型最优化是企业运作、科技研发和工程设计中常见的问题。要表述一个最优化问题（即建立数学模型），应明明确三样东西：决策变量、约束条件 和目标函数

21、决策变量：它们是决策者（你）所控制的那些数量，它们取什么数值需要决策者来决策，最优化问题的求解就是找出决策变量的最优取值。约束条件：它们是决策变量在现实世界中所受到的限制，或者说决策变量在这些限制范围之内取值才有实际意义。 目标函数：它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数。44引例引例单耗 甲 乙 丙限额材料工时工人 2 3 1 3 2 1.5 3 2 5343640利润(元/件) 4 3 2在一定的条件下，问生产数量为多少时, 利润达到最大？数据表生产计划问题生产计划问题45生产计划问题生产计划问题max cTxs.t. Axb x0矩阵形式：TT123c4, 3,

22、 2, ,2 3134A3 2 1.5 ,b363 2540 x x xx123123123123123max4322334321.536. .32540,0Zxxxxxxxxxstxxxx x x利润材料工时人力线性规划模型462002.5.命令linprog的基本调用格式 如果没有等式约束,就在相应位置输入空数组 , 不等式约束和上下界也类似.最后的输入项若没有,则可省略.x = linprog(c, A, b, Aeq,beq ,VLB, VUB)等式约束决策变量上下界不等式约束目标函数最优解MATLABMATLAB软件求解软件求解47看一个小例子 程序: c=-5,3; A=2,1;1

23、,2; b=40,50; L=0, 0; x,fmin=linprog(c,A,b,L); Pmax=-fmin x1=x(1), x2=x(2) 输出结果: Pmax=110, x1=10, x2=20.模型: max P=5 X1 + 3 X2 s.t. 2 X1 + X2 40 X1 + 2 X2 50 X10, X20 MATLABMATLAB软件求解软件求解 设想这样一个场景：设想这样一个场景：一群鸟在随机搜索食物一群鸟在随机搜索食物 在这块区域里只有一块食物在这块区域里只有一块食物; 所有的鸟都不知道食物在哪里所有的鸟都不知道食物在哪里; 但它们能感受到当前的位置离食物还有多远但它

24、们能感受到当前的位置离食物还有多远. 已知已知那么那么:找到食物的最优策略是什么呢？找到食物的最优策略是什么呢？ 搜寻目前离食物最近的鸟的周围区域搜寻目前离食物最近的鸟的周围区域 根据自己飞行的经验判断食物的所在。根据自己飞行的经验判断食物的所在。PSO正是从这种模型中得到了启发正是从这种模型中得到了启发 PSO的基础的基础: 信息的社会共享信息的社会共享 4.2 粒子群算法模型算法流程1 初始化粒子群体（群体规模为n），包括随机位置和速度2 评价每个粒子的适应度。3 对每个粒子，将其当前适应值与其个体历史最佳位置（pbest）对应的适应值做比较，如果当前的适应值更高，则将用当前位置更新历史最

25、佳位置pbest。4 对每个粒子，将其当前适应值与全局最佳位置（gbest）对应的适应值做比较，如果当前的适应值更高，则将用当前粒子的位置更新全局最佳位置gbest。4根据公式更新每个粒子的速度与位置。5 如未满足结束条件，则返回步骤2,通常算法达到最大迭代次数 或者最佳适应度值的增量小于某个给定的阈值时算法停止。粒子群优化算法流程图粒子群优化算法流程图 开始初始化粒子群计算每个粒子的适应度根据适应度更新pbest、gbest，更新粒子位置速度结束noyes达到最大迭代次数或全局最优位置满足最小界限？遗传算法(Genetic Algorithm)遵循适者生存、优胜劣汰的原则，是一类借鉴生物界自

26、然选择和自然遗传机制的随机化搜索算法。遗传算法模拟一个人工种群的进化过程，通过选择(Selection)、交叉(Crossover)以及变异(Mutation)等机制，在每次迭代中都保留一组候选个体，重复此过程，种群经过若干代进化后，理想情况下其适应度达到*近似最优*的状态。自从遗传算法被提出以来，其得到了广泛的应用，特别是在函数优化、生产调度、模式识别、神经网络、自适应控制等领域，遗传算法发挥了很大的作用，提高了一些问题求解的效率。4.3 遗传算法算法模型标准遗传算法的基本流程实际问题参数集实际问题参数集参数编码成为染色体参数编码成为染色体初始化群体初始化群体计算每一个体的计算每一个体的适应

27、度适应度对染色体进行解对染色体进行解码码满足终止满足终止条件？条件？得到问题最优解得到问题最优解进行遗传操作进行遗传操作群体群体新群体新群体P(t)P(t+1)1、选择、选择2、交叉、交叉3、变异、变异4.3 遗传算法算法模型 遗传算法具体步骤 选择选择编码编码策略，把参数集合（可行解集合）转换染色体结构空间；策略，把参数集合（可行解集合）转换染色体结构空间； 定义适应度定义适应度函数，便于计算适应值；函数，便于计算适应值； 确定遗传策略，包括选择群体大小，确定遗传策略，包括选择群体大小，选择、交叉、变异方法选择、交叉、变异方法以及以及确定交叉概率、变异概率等确定交叉概率、变异概率等遗传参数遗传参数； 随机产生随机产生初始化群体初始化群体； 计算群体中的个体或染色体计算群体中的个体或染色体解码后的适应值解码后的适应值； 按照遗传策略，运用按照遗传策略，运用选择、交叉和变异算子选择、交叉和变异算子作用于群体，形成下作用于群体，形成下一代群体；一代群体； 判断群体性能是否判断群体性能是否满足某一指标满足某一指标，或者已完成预定的，或者已完成预定的迭代次数迭代次数，不满足则返回第五步，或者修改遗传策略再返回第六步不满足则返回第五步，或者修改遗传策略再返回第六步4.3 遗传算法算法模型THANKS