没有合适的资源?快使用搜索试试~ 我知道了~
首页蒙特卡罗算法、最优化算法
资源详情
资源推荐
建模十大算法总结:
1、蒙特卡罗算法。该算法又称随机性模拟算法,是通过计算机仿真来解决问题的算法,同
时通过模拟可以来检验自己模型的正确性。
2、数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理,
而处理数据的关键就在于这些算法,通常使用 Matlab 作为工具。
3、线性规划、整数规划、多元规划、二次规划等规划类问题。建模竞赛大多数问题属
于最优化问题,很多时候这些问题可以用数学规划算法来描述,通常使用 Lindo、Lingo、
MATLAB 软件实现。
4、图论算法。这类算法可以分为很多种,包括最短路、网络流、二分图等算法,涉及到
图论的问题可以用这些方法解决,需要认真准备。
5、动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比
较常用的方法,很多场合可以用到竞赛中。
6、最优化理论的三大非经典算法:模拟退火法、神经网络、遗传算法。这些问题是用来
解决一些较困难的最优化问题的算法,对于有些问题非常有帮助,但是算法的实现比较困难,
需慎重使用。
7、网格算法和穷举法。网格算法和穷举法都是暴力搜索最优点的算法,在很多竞赛题中有
应用,当重点讨论模型本身而轻视算法的时候,可以使用这种暴力方案,最好使用一些高级
语言作为编程工具。
8、一些连续离散化方法。很多问题都是实际来的,数据可以是连续的,而计算机只认的
是离散的数据,因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。
9、数值分析算法。如果在比赛中采用高级语言进行编程的话,那一些数值分析中常用的
算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。
10、图象处理算法。赛题中有一类问题与图形有关,即使与图形无关,论文中也应该要不
乏图片的,这些图形如何展示以及如何处理就是需要解决的问题,通常使用 Matlab 进行处
理。
从历年竞赛题来看,常用的方法:
线性规划 整数规划 非线性规划 动态规划 层次分析法
图论方法 拟合方法 插值方法 随机方法 微分方程方法
一、蒙特卡洛算法
1、含义的理解
以概率和统计理论方法为基础的一种计算方法。也称统计模拟方法,是指使用随机数(或更
常见的伪随机数)来解决很多计算问题的方法,它是将所求解的问题同一定的概率模型相
联系,用计算机实现统计模拟或抽样,以获得问题的近似解。
2、算法实例(有很多相似的例题,包括平行线等)
在数值积分法中,利用求单位圆的 1/4 的面积来求得 Pi/4 从而得到 Pi。单位圆的 1/4 面积是
一个扇形,它是边长为 1 单位正方形的一部分。只要能求出扇形面积 S1 在正方形面积 S 中
占的比例 K=S1/S 就立即能得到 S1,从而得到 Pi 的值。怎样求出扇形面积在正方形面积中
占的比例 K 呢?一个办法是在正方形中随机投入很多点,使所投的点落在正方形中每一个
位置的机会相等看其中有多少个点落在扇形内。将落在扇形内的点数 m 与所投点的总数 n
的比 m/n 作为 k 的近似值。P 落在扇形内的充要条件是
22
1xy
。
已知:K=
1s
s
,K
m
n
,s=1,s1=
4
Pi
,求 Pi。
由
1sm
sn
,知 s1
*
m
s
n
=
m
n
,
而 s1=
4
Pi
,则 Pi=
*4
m
n
程序:(该算法可以修改后用 Mathematica 计算或者 Matlab)
/* 利用蒙特卡洛算法近似求圆周率 Pi*/
/*程序使用:VC++6.0 */
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define COUNT 800 /*循环取样次数,每次取样范围依次变大*/
void main()
{
double x,y;
int num=0;
int i;
for(i=0;i<COUNT;i++)
{
x=rand()*1.0/RAND_MAX;/*RAND_MAX=32767,包含在<stdio.h>中*/
y=rand()*1.0/RAND_MAX;
if((x*x+y*y)<=1)
num++; /*统计落在四分之一圆之内的点数*/
}
printf("Pi 值等于:%f\n",num*4.0/COUNT);
}
结果:
测试 6 次的结果显示:
循环取样次数
求得的 Pi 值
800
3.085000
8000
3.110000
80000
3.135200
800000
3.139150
8000000
3.141393
80000000
3.141321
可以看出:随着点数的增加,求得的 Pi 值渐渐接近真实值。
如果加入程序:srand(time(NULL)); ,同时循环取样次数一定,让取样结果随时间变化,当
取样次数为 80000000 时,可得 6 次的结果显示:
3.141290 3.141400 3.141268 3.141484 3.141358 3.141462
3、应用的范围
蒙特·卡罗方法在金融工程学,宏观经济学,计算物理学(如粒子输运
计算、量子热力学计算、空气动力学计算)等领域应用广泛。
4、参考书籍
[1]蒙特卡罗方法及其在粒子输运问题中的应用 [2]蒙特卡罗方法引论
二、数据拟合、参数估计、插值等数据处理算法
(1)数据拟合
在 Mathematica 中,用 Fit 对数据进行最小二乘拟合:Fit[data,funs,vars]
在 Matlab 中,工具箱(toolboxes)中有曲线拟合工具(curve Fitting)。
实例:
2010 年苏北赛 B 题 温室中的绿色生态臭氧病虫害防治 中关于中华稻蝗密度与水稻减产
率之间的关系可以通过数据拟合来观察(简单举例,没有考虑全部数据)
数据:
密度(头/m
2
)
3
10
20
30
40
减产率(%)
2.4
12.9
16.3
20.1
26.8
程序(Mathematica):
data={{3,2.4},{10,12.9},{20,16.3},{30,20.1},{40,26.8}};
a1=Fit[data,{1,x,x^2,x^3},x]
Show[ListPlot[data,Filling->Axis],Plot[{a1},{x,0,60}]]
结果:
-3.68428+2.38529 x-0.0934637 x
2
+0.00132433 x
3
(2)参数估计(参考书:概率论与数理统计)
参数估计为统计推断的基本问题,分为点估计和区间估计。
点估计:
①矩估计法
X 连续型随机变量,概率密度
12
( ; , , )
n
fx
X 为离散型随机变量 分布律
12
{ } ( ; , , , )
k
P X x p x
12
, , ,
k
为待估参数,
12
,,
n
X X X
是来自 X 的样本,假设总体 X 的前
k
阶矩存在,为
12
( ) ( ; , , )
ll
ln
E X x f x dx
(X 连续型)
或
12
( ) ( ; , , , )
X
ll
lk
xR
E X x p x
(X 离散型)
1,2, ,lk
(其中
X
R
是 X 可能取
值的范围)。一般来说,它们是
12
, , ,
k
的函数。基于样本矩
1
1
n
l
li
i
AX
n
依概率收敛
于相应的总体矩
( 1,2, )
l
lk
,样本矩的连续函数依概率收敛于相应的总体矩的连续函
数,我们就用样本矩作为相应的总体矩的估计量,而以样本矩的连续函数作为相应的总体矩
的连续函数的估计量。这种估计方法成为矩估计法。
②最大似然估计法
X 连续型随机变量 似然函数
12
1
( ) ( , , , ; ) ( ; )
n
ni
i
L L x x x f x
其中
1
( ; )
n
i
i
fx
是来自 X 的样本
12
,,
n
X X X
的联合密度。
X 为 离 散 型随 机 变 量 似然函数
12
1
( ) ( , , , ; ) ( ; ),
n
ni
i
L L x x x p x
其中
1
( ; )
n
i
i
px
是来自 X 的样本
12
,,
n
X X X
的联合分布律。
若
1 2 1 2
ˆ
( ) ( , , , ; ) max ( , , , ; )
nn
L L x x x L x x x
则称
12
ˆ
( , , , )
n
x x x
为
的最大似然估计值,称
12
ˆ
( , , , )
n
X X X
为
的最大似然估计量。
这样,确定最大似然估计量的问题就归结为微分学中的求最大值的问题了。
估计量的评选标准为:(1)无偏性(2)有效性(3)相合性
区间估计:
对于一个未知量,人们在测量或计算时,常不以得到近似值为满足,还需要估计误差,即要
求知道近似值的精确程度(亦即所求真值所在的范围)。这样的范围常以区间的形式给出,
同时还给出此区间包含参数真值的可信度,这种形式的估计称为区间估计,这样的区间即所
谓置信区间。
正态总体均值、方差的置信区间与单侧置信限(置信水平为 1-
)
一
个
正
态
总
体
未知参数
其他参数
枢轴量的分布
置信区间
2
已知
(0,1)
/
X
ZN
n
/2
()Xz
n
2
未知
( 1)
/
X
t t n
Sn
/2
( ( 1))
S
X z n
n
2
未知
2
22
2
( 1)
( 1)
nS
n
22
22
/2 1 / 2
( 1) ( 1)
( , )
( 1) ( 1)
n S n S
nn
另外还包括两个正态总体的情况,
其他区间估计:(0-1)分布参数的区间估计
(3)插值
1、含义的理解
在离散数据的基础上补插连续函数,使得这条连续曲线通过全部给定的离散数据点。插值是
离散函数逼近的重要方法,利用它可通过函数在有限个点处的取值状况,估算出函数在其他
点处的近似值(与拟合的不同点在于拟合的函数不需通过每一个离散点)。
插值问题的提法是:假定区间[a,b]上的实值函数 f(x)在该区间上 n+1 个互不相
同点 x0,x1…xn 处的值是 f [x0], …f(xn),要求估算 f(x)在[a,b]中某点的值。
其做法是:在事先选定的一个由简单函数构成的有 n+1 个参数 C0,C1,…Cn 的函
数类 Φ(C0,C1,…Cn)中求出满足条件 P(xi)=f(xi)( i=0,1,… n)的函数 P(x),
并以 P()作为 f()的估值。此处 f(x)称为被插值函数,x0,x1,…xn 称为插值结(节)
点,Φ(C0,C1,…Cn)称为插值函数类,上面等式称为插值条件,Φ(C0,…Cn)中
满足上式的函数称为插值函数,R(x)= f(x)-P(x)称为插值余项。当估算点
属于包含 x0,x1…xn 的最小闭区间时,相应的插值称为内插,否则称为外插。
2、基本类型
多项式插值
在一般插值问题中,若选取 Φ 为 n 次多项式类,由插值条件可以唯一确定一个 n 次插
值多项式满足上述条件。拉格朗日插值和牛顿插值都属于多项式插值。
拉格朗日插值:
设连续函数 y = f(x)在[a, b]上对给定 n + 1 个不同结点:
01
, , ,
n
x x x
分别取函数值
01
, , ,
n
y y y
其中
()
ii
y f x
0,1, ,in
(1)
试构造一个次数不超过 n 的插值多项式
2
0 1 2
()
n
nn
P x a a x a x a x
(2)
使之满足条件
()
n i i
P x y
0,1,2, ,in
(3)
构造 n 次多项式
()
k
lx
0,1, ,kn
使
()
k
lx
=
1, k=i
0, k i
(4)
剩余33页未读,继续阅读
CurseOnU
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功