当前位置:首页 >> 理学 >> 数模竞赛常用算法

数模竞赛常用算法


数学建模常用算法
杨蕾

数学建模常用算法/方法
1、数据拟合与插值 2、回归分析法 3、规划/优化问题(线性规划,非线性规划, 整数规划,动态规划,目标规划) 4、图论法 5、聚类分析、判别分析 6、模糊数学相关问题评判方法 7、时间序列方法 8、灰色理论方法 9、先进优化算法(遗传算法,神经网络)

1、数据拟合与插值方法
问题—给定一批数据点(输入变量与输 出变量的数据),需确定满足特定要求 的曲线或曲面 插值问题—要求所求曲线(面)通过所 给所有数据点 数据拟合—不要求曲线(面)通过所有 数据点,而是要求它反映对象整体的变 化趋势

数据拟合
一元函数拟合
多项式拟合 非线性函数拟合

多元函数拟合(回归分析) MATLAB实现 (拟合工具箱cftool) 确定出拟合函数,进而计算任一点的函 数值,可以用于预测

插值方法
一维插值的定义—已知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)

2、回归分析
回归分析—对具有相关关系的现象,根据其关系形 态,选择一个合适的数学模型,用来近似地表示变量 间的平均变化关系的一种统计方法 (一元线性回 归、多元线性回归、非线性回归) 回归分析在一组数据的基础上研究这样几个问题:
建立因变量与自变量之间的回归模型(经验公式) 对回归模型的可信度进行检验 判断每个自变量对因变量的影响是否显著 判断回归模型是否适合这组数据 利用回归模型对进行预报或控制

[b, bint,r,rint,stats]=regress(Y,X,alpha) (线性回归) rstool(x,y,’model’, alpha)(多元二项式回归) [beta,r,J]=nlinfit(x,y,’model’, beta0)(非线性回 归)

逐步回归分析
逐步回归分析—从一个自变量开始,视自变量 作用的显著程度,从大到地依次逐个引入回归 方程
当引入的自变量由于后面变量的引入而变得不显著 时,要将其剔除掉 引入一个自变量或从回归方程中剔除一个自变量, 为逐步回归的一步 对于每一步都要进行值检验,以确保每次引入新的 显著性变量前回归方程中只包含对作用显著的变量 这个过程反复进行,直至既无不显著的变量从回归 方程中剔除,又无显著变量可引入回归方程时为止

stepwise(x,y,inmodel,alpha) SPSS,SAS

3、规划/优化模型分类
线性规划模型(目标函数和约束条件都 是线性函数的优化问题) 非线性规划模型(目标函数或者约束条 件是非线性的函数) 整数规划(决策变量是整数值得规划问 题) 多目标规划(具有多个目标函数的规划 问题) 动态规划(求解多阶段决策问题的最优 化方法)

规划/优化模型四要素
决策变量 目标函数(建模的核心,尽量简单、光滑) 约束条件(建模的关键部分) 求解方法 (MATLAB,LINDO)

规划/优化模型求解(matlab)
无约束规划
fminsearch fminbnd

线性规划
linprog

非线性规划
fmincon

多目标规划(计算有效解)
目标加权、效用函数

动态规划(倒向、正向) 整数规划(分支定界法、枚举法、Lingo、 Lindo)

4、图论方法
最短路问题
两个指定顶点之间的最短路径—给出了一个连接若干 个城镇的铁路网络,在这个网络的两个指定城镇间, 找一条最短铁路线 (Dijkstra算法 ) 每对顶点之间的最短路径 (Dijkstra算法、Floyd算 法)

最小生成树问题
连线问题—欲修筑连接多个城市的铁路设计一个线路 图,使总造价最低(prim算法、Kruskal算法 )

图的匹配问题
人员分派问题:n个工作人员去做件n份工作,每人适 合做其中一件或几件,问能否每人都有一份适合的工 作?如果不能,最多几人可以有适合的工作?(匈牙利 算法)

图论方法
遍历性问题
中国邮递员问题—邮递员发送邮件时,要从 邮局出发,经过他投递范围内的每条街道至 少一次,然后返回邮局,但邮递员希望选择 一条行程最短的路线—旅行商问题

最大流问题
运输问题

最小费用最大流问题
在运输问题中,人们总是希望在完成运输任 务的同时,寻求一个使总的运输费用最小的 运输方案

5、聚类分析
聚类分析—所研究的样本或者变量之间存 在程度不同的相似性,要求设法找出一些 能够度量它们之间相似程度的统计量作为 分类的依据,再利用这些量将样本或者变 量进行分类 系统聚类分析—将n个样本或者n个指标看 成n类,一类包括一个样本或者指标,然 后将性质最接近的两类合并成为一个新 类,依此类推。最终可以按照需要来决定 分多少类,每类有多少样本(指标)

系统聚类分析步骤
系统聚类方法步骤: 1. 计算n个样本两两之间的距离 2. 构成n个类,每类只包含一个样品 3. 合并距离最近的两类为一个新类 4. 计算新类与当前各类的距离(新类与当 前类的距离等于当前类与组合类中包含 的类的距离最小值),若类的个数等于 1,转5,否则转3 5. 画聚类图 6. 决定类的个数和类。

分解聚类
分解聚类:把全部样本作为一类,然后 根据相似性、相邻性分解。 目标函数 两类均值方差 T N1 N 2 E= ( x1 ? x2 ) ( x1 ? x2 ) N N:总样本数, 1 :ω1类样本数 N

x N 2 :ω2类样本数, 1 , x 2 : 两类均值

分解聚类框图:
初始分类

调整分类方案

N

目标函数 达到最优先?

Y

最终结果

K-均值聚类分析
K-means Cluster

又称为快速样本聚类法,是非系统聚类中最常用的聚类 法。 优点: 是占内存少、计算量小、处理速度快,特别适合大样本的 聚类分析。 缺点: 应用范围有限,要求用户制定分类数目(要告知),只能对观 测量(样本)聚类

基本原理
具体做法 1、按照指定的分类数目n,按某种方法选择某些观测量,设为 {Z1,Z2,…Zn},作为初始聚心。 2、计算每个观测量到各个聚心的欧氏距离。即

2 ?m 2? d ij = xi ? z j = ?∑ (xik ? x jk ) ? ? ? k =1

1

按就近原则将每个观测量选入一个类中,然后计算各个类的中 心位置,即均值,作为新的聚心。 3、使用计算出来的新聚心重新进行分类,分类完毕后继续计算 各类的中心位置,作为新的聚心,如此反复操作,直到两次迭 代计算的聚心之间距离的最大改变量小于初始聚类心间最小距 离的倍数时,或者到达迭代次数的上限时,停止迭代。

判别分析
判别分析—在已知研究对象分成若干类型,并已取 得各种类型的一批已知样品的观测数据,在此基础 上根据某些准则建立判别式,然后对未知类型的样 品进行判别分类。 距离判别法—首先根据已知分类的数据,分别计算 各类的重心,计算新个体到每类的距离,确定最短 的距离(欧氏距离、马氏距离) Fisher判别法—利用已知类别个体的指标构造判别 式(同类差别较小、不同类差别较大),按照判别 式的值判断新个体的类别 Bayes判别法—计算新给样品属于各总体的条件概 率,比较概率的大小,然后将新样品判归为来自概 率最大的总体

6、模糊数学相关的问题

模糊数学—研究和处理模糊性现象的数 学 (概念与其对立面之间没有一条明确 的分界线)

6、模糊数学相关的问题
模糊聚类分析—根据研究对象本身的属性构 造模糊矩阵,在此基础上根据一定的隶属度 来确定其分类关系 模糊层次分析法—两两比较指标的确定 模糊综合评判—综合评判就是对受到多个因 素制约的事物或对象作出一个总的评价,如 产品质量评定、科技成果鉴定、某种作物种 植适应性的评价等,都属于综合评判问题。 由于从多方面对事物进行评价难免带有模糊 性和主观性,采用模糊数学的方法进行综合 评判将使结果尽量客观从而取得更好的实际 效果

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个时刻进入系统的扰动存在一定的依存关 系

时间序列建模的基本步骤 (1)
1. 数据的预处理:数据的剔取及提取趋势项 2. 取n=1,拟合ARMA(2n,2n-1)(即ARMA(2,1))

模型

3. n=n+1,拟合ARMA(2n,2n-1)模型
4. 用F准则检验模型的适用性。若检验显著,则

转入第2步。若检验不显著,转入第5步。 5. 检查远端时刻的系数值的值是否很小,其置 信区间是否包含零。若不是,则适用的模型 就是ARMA(2n,2n-1) 。若很小,且其置信区 间包含零,则拟合ARMA(2n-1,2n-2) 。

时间序列建模的基本步骤 (2)
利用F准则检验模型ARMA(2n,2n-1)和 ARMA(2n-1,2n-2) ,若F值不显著,转 入第7步;若F值显著,转入第8步。 7. 舍弃小的MA参数,拟合m<2n-2的模型 ARMA(2n-1,m) ,并用F准则进行检验。 重复这一过程,直到得出具有最小参数 的适用模型为止 8. 舍弃小的MA参数,拟合m<2n-1的模型 ARMA(2n,m) ,并用F准则进行检验。重 复这一过程,直到得出具有最小参数的 适用模型为止。
6.

8、灰色理论
1982年我国学者邓聚龙创立了灰色系统理 论,模糊数学着重研究“认知不确定”问题,概率 统计研究的是“随机不确定”现象的历史统计规 律。 灰色系统研究的是“部分信息明确,部分信息 未知”的“小样本,贫信息”不确定性系统,它通过 对已知“部分”信息的生成去开发了解、认识现实 世界。

灰色预测模型
GM(1,1)预测模型步骤: 1、对于原始数列 X (0) = ( x (0) (1), x (0) (2),L , x (0) (n)) ,做 一次累加得 X (1) = ( x (1) (1), x (1) (2),L , x (1) (n)) ,其中 k
x (1) ( k ) =


i =1

x ( 0 ) (i ), k = 1, 2, L , n;
1 (1) (1) ( x (k ) + x (k ? 1)) 2



2、计算 z 并得到

(1)

(k ) =

k = 2,3Λ , n

? ( 0) (2) ? ? x( 0) ? (3) ? Y = ?x ? Μ ? ? ( 0) ? ? x ( n) ? ? ?

? ? (1) (2) ? z (1) ? (3) B=? z ? Μ ? (1) ? ? z ( n) ?

1? ? 1? ? Μ ? 1? ?

3、计算参数向量 4、将参数a,b代入响应函数,得到累加序列预测值

? = (a,b) = ( BT B) ?1 BT Y a

T

? x

( 1)

( k + 1) = ( x

( 0)

b ? ak b (1) ? ) e + a a
(1)

5、由累加序列得到原始序列预测值

? x

(0)

(k + 1) = x (k + 1) ? x (k ) ? ?
(1) a (0)

= (1 ? e )( x

b ?ak (1) ? ) e a

GM(1,1)主要用于单调序列,灰色预测模型除 GM(1,1)之外,还有: 残差GM(1,1)模型 对于非单调的摆动发展序列或有饱和的S形序 列,可建立GM(2,1),DGM和Verhulst模型 区间预测 灰色灾变预测(波形预测 ) 系统预测

灰色理论除了用于预测之外,还包含: 灰色决策 灰色人工神经网络模型 灰色动态规划 灰 色 控 制 灰色聚类评估

9、先进优化算法
遗传算法 神经网络 微粒群算法PSO 模拟退火算法

关于优化问题

遗传算法

传统的优化方法(局部优化) 共轭梯度法、拟牛顿法、单纯形方法 全局优化方法 漫步法(Random Walk)、模拟退火法、GA

传统的优化方法 比 较: 1)依赖于初始条件。 2)与求解空间有紧密关系,促使较快地收敛到局部 解,但同时对解域有约束,如可微或连续。利用 这些约束,收敛快。 3)有些方法,如Davison-Fletcher-Powell直接依 赖于至少一阶导数; 共轭梯度法隐含地依赖于梯 度。

全局优化方法

1)不依赖于初始条件; 2)不与求解空间有紧密关系,对解域,无可微或连 续的要求。求解稳健,但收敛速度慢。能获得全局 最优。适合于求解空间不知的情况

遗传算法基本原理
模拟自然界优胜劣汰的进化现象,把搜索空间映射为遗传 空间,把可能的解编码成一个向量——染色体,向量的每个 元素称为基因。 通过不断计算各染色体的适应值,选择最好的染色体,获 得最优解。

遗传算法的基本运算 ⑴ 选择运算 ⑵ 交换操作 ⑶ 变异

●选择运算
——从旧的种群中选择适应度高的染色体,放入匹配集(缓冲 区),为以后染色体交换、变异,产生新的染色体作准备。 选择方法——适应度比例法(转轮法) 按各染色体适应度大小比例来决定其被选择数目的多 少。 某染色体被选的概率:Pc

Pc =

f ( xi )



f ( xi )

xi 为种群中第i个染色体,

具体步骤
1)计算各染色体适应度值 2)累计所有染色体适应度值,记录中间累加值S - mid 和最 后累加值 sum = ∑f(xi) 3) 产生一个随机数 N,0〈 N 〈 sum 4) 选择对应中间累加值S - mid 的第一个染色体进入交换集 5) 重复(3)和(4),直到获得足够的染色体。

●交换操作
复制不能创新,交换解决染色体的创新 方法:随机选择二个染色体(双亲染色体),随机指定一点或多 点, 进行交换,可得二个新的染色体(子辈染色体).

新的子辈染色体: A’ B’ ●变异

11010001 01011110

模拟生物在自然界环境变化,引起基因的突变.在染 色体二进制编码中,1变成0;或0变成1.突变产生染色 体的多样性,避免进化中早期成熟,陷入局部极值点, 突变的概率很低.

GA的流程

简单遗传算法(GA)的基本参数
①种群规模 P: 参与进化的染色体总数. ②代沟G: 二代之间不相同的染色体数目,无重叠G = 1; 有重叠 0 < G <1 ③选择方法: 转轮法,精英选择法,竞争法. ④交换率: Pc 一般为60~100%. ⑤变异率: Pm 一般为0.1~10% Matlab已有GA工具箱: Gatool

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

人工神网络基本原理
从具体的一个神经元来说,就是要建立一 个数学模型,描述对输入讯号的整和输出过 程。从全局来看,多个神经元构成一个网络, 必须给出如下三方面的要素:(1)对单个人 工神经给出某种形式定义;(2)决定网络中 神经元的数量及彼此间的联结方式。或者说, 定义网络结构;(3)给出一种方法,决定元 与元之间的联结强度,使网络具有某种预定功 能。

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

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

图1 单层人工神经网络

图2 两层人工神经网络

人工神经网络含有若干个信息输入和一个输出,并含有一个称之为激活函数 的计算单元。典型的激励函数有Sigmoid函数、双曲正切函数、线性函数、阶跃 函数等(如图3),其中Sigmoid函数构成的人工神经网络结构较为复杂,但 Sigmoid函数是递增的,它的导数不为零,因此比其他几种激励函数有更好的特 性。Sigmoid函数在BP学习中是一个强有力的工具。

图3 用于处理单元的几种常用激励函数 (a)线性函数(b)斜坡函数(c)阶跃函数 (d)符号函数(e)Sigmoid函数 (f)双曲正切函数

梯度搜索的步长η,称为学习速率。η越大,权值 修改越剧烈。通常按这样的法则选取η:即在不导致 振荡的前提下尽可能取较大的η。为使η足够大而又不 易产生振荡,常在式中再加一项“惯性项”(momentum item),即:

ΔW ji (t + 1) = ηδ PjOPi + αΔW ji (t ) (14.12)
其中α为一常数,它决定过去的权值变化对当前 权值变化的影响的大小。 下面给出的BP算法是在假定网络为多层前向网络 ,网络激发函数为Sigmoid函数时给出的,并且阈值θ 也作同样的训练。

其他神经网络
RBF神经网络 遗传神经网络

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

人工神经网络的优点:人工神经网络只不过是另一
种计算机建模工具而已,但与一些著名的、传统的计算机建 模方法相比,具有一些明显的优点。这些优点包括: (1)自适应性:人工神经网络具有对周围环境的自适应或学 习的能力。当给人工神经网络以输入-输出模式时,它可以通 过自我调整使误差达到最小,即通过训练进行学习。对于某 些难以参数化的因素,可以通过训练,自动总结规律。

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

?

(4)外推性:人工神经网络有较好的外推性,即从 训练中,从部分样本中学到的知识推广到全体祥 本。 (5)自动抽提功能:人工神经网络能通过采用直接 的(有时是不精确的)数值数据进行训练,并能自动 地确定原因-结果关系。 (6)在线应用的潜力:人工神经网络的训练可能要 花费大量的时间,但训练一旦完成,它们就能从给 定的输入很快地计算出结果。由于训练好的网络能 在不到1s的时间里得出计算结果,所以它有可能在 控制系统中在线使用。但是应该注意,此时的人工 神经网络必须是离线训练好的。

?

?

神经网络的用途
函数拟合逼近 模式识别 分类/判别分析 数据压缩

DNA序列分类题(2000年全国赛A题) 癌症判断题(2001年北京大学数学建模 竞赛) 徽章问题

人工神经网绪的局限性:
(1)训练时间长:人工神经网络需要长时间的训 练,有时可能使之变得不实用。大多数简单问题的网 络训练需要至少上千次迭代,复杂问题的训练可能需 要多达数万次迭代。根据网络的大小,训练过程可能 需要主机时间几个到几十个小时。 (2)需大量训练数据:人工神经网络在很大程度上 取决于训练时关于问题的输入-输出数据,若只有少 量输入-输出数据,一般不考虑使用人工神经网络。 (3)不能保证最佳结果:反向传播是调整网络的一 个富有创造性的方法,但它并不能保证网络能恰当地 工作。训练可能导致网络发生偏离,使之在一些操作 区域内结果准确,而在其他区域则不准确。此外,在 训练过程中,有可能偶尔陷入“局部最小。

(4)不能保证完全可靠:尽管这一点对所有的计 算问题均适用,但对人工神经网络尤其如此。例如 在故障诊断中,对于某些故障,误诊率可能只有 1%,而对同一问题的其他故障,误诊率可能高达 33%。重要的是:事先无法知道(用反向传播训练)哪 些故障比其他故障更易于出现误诊。因此,对于需 要近乎100%可靠的军事问题,在采用人工神经网络 时必须小心谨慎。 另外,对于一些“操作性的”问题,如训练集过 小,由于传感器的故障导致采集到的数据错误等, 这些问题有时能明显影响人工神经网络的使用效 果。

祝大家MCM/ICM 中取得好成绩!


更多相关文档:

数学建模常用的十种算法

数学建模常用的十种算法_工学_高等教育_教育专区。数学建模的十大常用算法 1、 ...(建模竞赛大多数问题属于最优化问题, 很多时候这些问题可 以用数学规划算法来...

数学建模10种常用算法

(建模竞赛大 多数问题属于最优化问题,很多时候这些问题可以用数学规划算法来描述, 通常使用 Lindo、Lingo 软件实现) 4、图论算法(这类算法可以分为很多种,包括最...

数学建模常用的十大算法

数学建模常用的十大算法_数学_自然科学_专业资料。数学建模常用的十大算法==转 ...这些算法算法设计中 比较常用的方法,竞赛中很多场合会用到。 6. 最优化理论...

数学建模常用算法模型

(建模竞赛大多数问题属于最优化问题, 很多时候这些问题可以用数学规划算法 来描述,通常使用 Lindo、Lingo 软件实现) 4、图论算法 (这类算法可以分为很多种,包括最...

数学建模常用算法

数学建模常用算法_数学_自然科学_专业资料。数学建模,建模方法 1、蒙特卡罗算法。...这些算法是算法设计中比较 常用的方法,很多场合可以用到竞赛中。 6、最优化理论...

数学建模十大经典算法

数学建模十大经典算法_数学_自然科学_专业资料。数学建模十大经典算法,算法简单介绍和使用相应算法的各年竞赛的题目 数学建模十大经典算法 1 十类常用算法 1. ...

数学建模常用算法和模型全集

数学建模常用算法和模型全集_理学_高等教育_教育专区。数学建模相关资料一、常用...(网格算法和穷举法都是暴力搜索最优点的算法,在很多竞赛题中有应用, 当重点...

数学建模十大经典算法

建模十大经典算法 1、蒙特卡罗算法。 该算法又称随机性模拟算法, 是通过计算机...这些算法算法设计中比较常用的方法,很多场合可以用到竞赛中。 6、最优化理论...

数学建模算法分类

(建模竞赛大多数问题属于最优化 问题,很多时候这些问题可以用数学规划算法来描述,...分治算法、分支定界等计算机算法(这些算法算法设计中比较常用 的方法,很多场合...

数模十大算法(技巧)

(建模竞赛大多数问题属 于最优化问题,很多时候这些问题可以用数学规划算法来描述...分治算法、分支定界等计算机算法(这些算法算法设计中 比较常用的方法,很多场合...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com