数学建模10种常用算法
数学建模10种常用算法
1、蒙特卡罗算法(该算法又称随机性模拟算法,是通过计算机仿真来解决问题的算法,同时可以通过模拟可以来检验自己模型的正确性,是比赛时必用的方法)
2、数据拟合、参数估计、插值等数据处理算法(比赛中通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用Matlab 作为工具)
3、线性规划、整数规划、多元规划、二次规划等规划类问 题(建模竞赛大多数问题属于最优化问题,很多时候这些问题可以用数学规划算法来描述,通常使用Lindo 、Lingo 软件实现)
4、图论算法(这类算法可以分为很多种,包括最短路、网络流、二分图等算法,涉及到图论的问题可以用这些方法解决,需要认真准备)
5、动态规划、回溯搜索、分治算法、分支定界等计算机算法(这些算法是算法设计中比较常用的方法,很多场合可以用到竞赛中)
6、最优化理论的三大非经典算法:模拟退火法、神经网络、遗传算法(这些问题是用来解决一些较困难的最优化问题的算法,对于有些问题非常有帮助,但是算法的实现比较困难,需慎重使用)
7、网格算法和穷举法(网格算法和穷举法都是暴力搜索最优点的算法,在很多竞赛题中有应用,当重点讨论模型本身而轻视算法的时候,可以使用这种暴力方案,最好使用一些高级语言作为编程工具)
8、一些连续离散化方法(很多问题都是实际来的,数据可以是连续的,而计算机只认的是离散的数据,因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的)
9、数值分析算法(如果在比赛中采用高级语言进行编程的话,那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用)
10、图象处理算法(赛题中有一类问题与图形有关,即使与图形无关,论文中也应该要不乏图片的,这些图形如何展示以及如何处理就是需要解决的问题,通常使用Matlab 进行处
参数估计
18世
C.F.
20世纪60年代, 随着电子计算机的普及, 参数估计有了飞速的发展。参数估计有多种方法,有最小二乘法、极大似然法、极大验后法、最小风险法和极小化极大熵法等。在一定条件下,后面三个方法都与极大似然法相同。最基本的方法是最小二乘法和极大似然法. 基本介绍
参数估计(parameter estimation
矩估计法
yt 尽可能接近的参数估计值,可用模误差平方和计值。
公式1
计。若线性估计又是一致最小均方误差估计,则称为最优线性无偏估计。如果无偏估计值的-尧不等式的下界, 则称为有效估计值。若 ,则称 为一致性估计值。在一定条件下,最小二乘估计是最优线性无偏估计,它的估计值是有效估计,而且是一致性估计。极大似然估计在一定条件下渐近有效,而且是一致的。 寻求最小二乘估计和极大似然估计的常用方法是将准则对参数θ求导数
公式2
,计算梯度,因而要使用最优化的方法:梯度法、变尺度法、单纯形搜索法、牛顿-拉夫森法等。
点估计
点估计是依据样本估计总体分布中所含的未知参数或未知参数的函数。通常它们是总体
本的量,作为未知参数或未知参数的函数的估计值。例如,设一批产品的废品率为θ。为估计θ,从这批产品中随机地抽出n 个作检查,以X 记其中的废品个数,用X /n 估计θ,这就是一个点估计。构造点估计常用的方法是:①矩估计法。用样本矩估计总体矩,如用样本均值估计总体均值。②最大似然估计法。于
1912R.A. 费希尔提出,利用
函数来求出参数的最大似然估计。③提出的估计法。可以用来估计未知参数的估计量很多,于是产生了怎样选择一个优良估计量的问题。首先必须对优良性定出准则,这种准则是不唯一的,可以根据实际问题和理论研究的方便进行选择。优良性准则有两大类:一类是小样本准则,即在样本大小固定时的优良性准则;另一类是大样本准则,即在样本大小趋于无穷时的优良性准则。最重要的小样本优良性准则是无偏性及与此相关的一致最小方差无偏估计,其次有容许性准则,最小化最大准则,最优同变准则等。大样本优良性准则有相合性、最优渐近正态估计和渐近有效估计等。 区间估计
区间估计是依据抽取的样本,根据一定的正确度与精确度的要求,构造出适当的区间,作为总体分布的未知参数或参数的函数的真值所在范围的估计。例如人们常说的有百分之多少的把握保证某值在某个范围内,即是区间估计的最简单的应用。1934年统计学家J. 奈曼
为了减少计算量,便于在线估计参数,产生了许多递推算法。一般是用递推算法
公式3
估计动态系统的参数。方法是:利用时刻t 上的参数估计 、存储向量xt 与时刻t+1上的输入和输出数据ut+1和yt+1
,计算新的参数值。每一步的计算时间比解一个线性代数方程组要少得多。 最小二乘法和极大似然法都有递推形式,另外还有递推广义最小二乘法、递推辅助变量法和递推增广最小二乘法等,都是递推最小二乘法的改进形式, 可以用来估计带有色噪声干扰的系统。此外,随机逼近算法、卡尔曼滤波法
公式4
和朗道递推估计,是从不同的出发点得到的递推参数估计法(见递推估计算法),大多数递推参数估计算法的一致性, 即, 可以用鞅收敛性、常微分方程稳定性和超稳定性、正实性分别证明。 参数估计的方法很多,如何统一它们,如何在实践中简单有效地判断它们的
公式5
性质以及产生新的方法,都是有待进一步探讨的问题。