文档库

最新最全的文档下载
当前位置:文档库 > 数学建模中常用的算法

数学建模中常用的算法

数学建模中常用的算法

2009-11-27 18:54

Page 1先讲算法讲义

在本讲义中,我们将着重讲述一些数学建模中常用的算法,包括神经网络算法、遗传算法、模拟退火算法和模糊数学方法。用这些算法可以较容易地解决一些很复杂的,常规算法很难解决的问题。由于这些算法都有着很深的理论背景,因此,本讲义中不可能也没有必要详细地讨论这些算法的理论,我们的目标在于应用,大家只需大概了解这些算法的原理,知道能用这些算法解决一类什么样的问题,并能应用这些算法解决数学建模中的一些问题即可。因为着眼于应用,所以我们还提供了一些程序代码,使用者只需套用这些程序,便可使问题得到很好的解决。

第一节神经网络

1.神经网络的简单原理人工神经网络是根据人的认识过程而开发出的一种算法。假如我们现在只有一些输入和相应的输出,而对如何由输入得到输出的机理并不清楚,那么我们可以把输入与输出之间的未知过程看成是一个“网络”,通过不断地给这个网络输入和相应的输出来“训练”这个网络,网络根据输入和输出不断地调节自己的各节点之间的权值来满足输入和输出。这样,当训练结束后,我们给定一个输入,网络便会根据自己已调节好的权值计算出一个输出。这就是神经网络的简单原理。

2.神经元和神经网络的结构如上所述,神经网络的基本结构如下图所示:神经网络一般都有多层,分为输入层,输出层和隐含层,层数越多,计算结果越精确,但所需的时间也就越长,所以实际应用中要根据要求设计网络层数。神经网络中每一个节点叫做一个人工神经元,他对应于人脑中的神经元,两者的结构比较如下图:

一个人工神经元一般有多个输入和一个输出,另外有一个激发函数,不同的激发函数对应了不同的网络,也决定了网络的用途。

3.神经网络的分类神经网络按照网络结构和激发函数的不同可分为许多种,我们在此只是对感知器和BP 网络进行简介。

感知器:最早也是最简单的一种神经网络,它的神经元激发函数为阶跃函数,其神经元结构如下图:感知器主要用于分类。

BP网络:应用得最为广泛,最为重要的一种神经网络。这种网络一般有多层,网络结构如下:

BP 网络的激发函数一般采用S 型函数,如正切或对数函数,其神经元结构如下:BP 网络的用途十分广泛,可用于以下方面:函数逼近:用输入矢量和相应的输出矢量训练一个网络逼近一个函数模式识别:用一个特定的输出矢量将它与输入矢量联系起来分类:把输入矢量以所定义暮鲜史绞浇蟹掷嗍菅顾酰杭跎偈涑鍪噶课员阌诖浠虼娲?.神经网络在数学建模中的应用数学建模中有很多题目都可以用神经网络加以解决,比较典型的题目有:DNA 序列分类题(2000 年全国赛A 题),癌症判断题(2001 年北京大学数学建模竞赛),乳房癌的诊断题(2001 年全国大学生数学建模夏令营 C 题)。下面我们使用神经网络的方法解决癌症判断题(2001 年北京大学数学建模竞赛),题目如下:附件中的文件给出了一个114个基因, 60个人的基因表达水平的样本. 其中前20个是癌症病人的基因表达水平的样本(其中还可能有子类),其后的是20个正常人的基因表达信息样本, 其余的20个是待检测的样本(未知它们是否正常).

(1).试设法找出描述癌症与正常样本在基因表达水平上的区别, 建立数学模型,及识别方法,去预测待检测样本是癌症还是正常样本.

(2).设计图示(可视化) 方法,使得在你的数学模型下, 尽量清楚地表现癌症与正常样本在基因表达水平上的区别, 以及癌症样本中是否有子类.

这道题是很典型的用神经网络的分类问题,只需用感知器神经网络便能完成此分类工作,我们用前40 组数据对网络进行训练,再用训练号的网络来计算后20 组数据,便能得到分类的结果。详细的程序可参见本讲义附带的Matlab 程序。

5.神经网络的程序设计该讲义附带了如下程序资源:Matlab 神经网络工具箱函数简介癌症判断题(2001 年北京大学数学建模竞赛)的Matlab 程序

第二节遗传算法

1.遗传算法的简单原理遗传算法(Genetic Algorithm, GA)是一种基于自然群体遗传演化机制的高效探索算法,它摒弃了传统的搜索方式,模拟自然界生物进化过程,采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体,并将每一个体编码成符号串形式,模拟达尔文的遗传选择和自然淘汰的生物进化过程,对群体反复进行基于遗传学的操作(遗传,交叉和变异),根据预定的目标适应度函数对每个个体进行评价,依据适者生存,优胜劣汰的进化规则,不断得到更优的群体,同时以全局并行搜索方式来搜索优化群体中的最优个体,求得满足要求的最优解。我们先通过一个例子来了解遗传算法的原理:假定我们要求函数的极大值,其中2)(xxf=x为自然数,0≤x≤31。现在,我们将每一个数看成一个生命体,通过进化,我们看谁能最后生存下来,谁就是我们所寻找的数。

①.编码我们将每一个数作为一个生命体,那么必须给其赋予一定的基因,这个过程叫做编码。我们可以把变量x 编码成5 位长的二进制无符号整数表示形式,比如x=13 可表示为01101 的形式,也就是说,数13 的基因为01101。

②.初始群体的生成由于遗传的需要,我们必须设定一些初始的生物群体,让其作为生物繁殖的第一代,需要说明的是,初始群体的每个个体都是通过随机方法产生的,这样便可以保证生物的多样性和竞争的公平性。

③.适应度评估检测生物的进化服从适者生存,优胜劣汰的进化规则,因此,我们必须规定什么样的基因是“优”的,什么样的基因是“劣”的,在这里,我们称为适应度。显然,由于我们要求的最大值,因此,能使较大的基因是优的,使较小的基因是劣的,因此,我们可以将定义为适应度函数,用来衡量某一生物体的适应程度。2)(xxf=2)(xxf=2)(xxf=2)(xxf=

④.选择接下来,我们便可以进行优胜劣汰的过程,这个过程在遗传算法里叫做选择。注意,选择应该是一个随机的过程,基因差的生物体不一定会被淘汰,只是其被淘汰概率比较大罢了,这与自然界中的规律是相同的。因此,我们可以采取赌论的方式来进行选择。

⑤.交叉操作接下来进行交叉繁殖,随机选出两个生物体,让其交换一部分基因,这样便形成了两个新的生物体,为第二代。

⑥.变异生物界中不但存在着遗传,同时还存在着变异,在这里我们也引入变异,使生物体的基因中的某一位以一定的概率发生变化,这样引入适当的扰动,能避免局部极值的问题。以上的算法便是最简单的遗传算法,通过以上步骤不断地进化,生物体的基因便逐渐地趋向最优,最后便能得到我们想要的结果。

2.遗传算法的步骤从上面的例子中,我们便能得到遗传算法的一般步骤,如下图所示:

3.遗传算法的应用遗传算法主要是用来寻优,它具有很多优点:它能有效地避免局部最优现象,有及其顽强的鲁棒性,并且在寻优过程中,基本不需要任何搜索空间的知识和其他辅助信息等等。为了介绍遗传算法的应用,我们将前面的例子进行完,整个过程如下:初始群体01101 11000 01000 10011 x的值1324819适应度169 576 64 361 2)(xxf=选择概率0.14 0.49 0.06 0.31 选择上的计数(来自赌轮)1 2 0 1 交叉处0110|0 1100|0 11|000 10|011 下一代群体01100 1100 1 11011 10000 x的值12 25 27 16 适应度144 625 729 256 2)(xxf=Page 6…… …… …… …… …… 4.遗传算法的程序设计本讲义提供了遗传算法求的C 语言程

序x2sin

第三节模拟退火算法

1.模拟退火算法的简单原理模拟退火算法主要用于解决组和优化问题,它是模拟物理中晶体物质的退火过程而开发的一种优化算法。在对固体物质进行模拟退火处理时,通常先将它加温熔化,使其中的粒子可自由运动,然后随着温度的逐渐下降,粒子也逐渐形成了低能态的晶格。若在凝结点附近的温度下降速率足够慢,则固体物质一定会形成最低能态的基态。对于组合优化问题来说,它也有这样的类似过程。组合优化问题解空间中的每一点都代表一个具有不同目标函数值的解。所谓优化,就是在解空间中寻找目标函数最小(大)解的过程。若把目标函数看成能量函数,某一控制参数视为温度T,解空间当作形态空间,那么寻找基态的过程也就是求目标函数极小值的优化过程。

2.模拟退火算法的应用如前所述,模拟退火算法主要用于解决组和优化问题,典型的例子是用模拟退火算法来解决TSP 问题,本讲义附带了用模拟退火算法解决TSP 问题的算法,有兴趣的同学可以参考模拟退火算法也经常用在神经网络中,本讲义也附带了一个模拟退火算法用在神经网络中的程序。

第四节模糊数学方法

1.模糊数学的简单原理①.模糊集对于传统集合,一个元素要么属于这个集合,要么不属于这个集合,我们用 1 表示元素属于该集合,用0 表示元素不属于这个集合。模糊集合论认为,一个元素可以不完全属于一个集合,用[0,1]之间的一个数来表示一个元素属于一个集合的程度,这个数叫做该元素属于该集合的隶属度。②.模糊概念的清晰化我们可以设定一个数(比如0.5),当一个元素的隶属度大于这个数时,我们就可以认为该元素属于这个集合,这就是模糊概念的清晰化。

2.模糊数学的应用举例模糊数学在数学建模中主要用于模糊决策,这也是决策论中很重要的一部分内容,我们通过下面的例子来说明。有7 名同学进行了毕业论文的答辩,有10 位教授要对同学的答辩做出评分,评分采取等级制,各等级的分数如下:评分标准一等二等三等四等五等六等分数10 8 6 4 3 1 将参加评选的同学进行两两比较评分,例如x1→x2(以先评价的x2为基准,后评价的x1为对象进行相对比较评分)。比如10 人所给相加的总分为80 分,则学生x1对Page 7x2的优先选择比为80.01008012==r(其中分母100 为10 个教授都给最高分时的总分)相应的x2对x1的优先选择比为2.08.0111221=?=?=rr。利用上面的方法便可以得到下表:一等二等三等四等五等六等分数1086431评选组给被评人总分优先选择比rijx1-> x2343800.80x1-> x31531720.72x1-> x42521760.76x1-> x56211860.86x1-> x63142700.70x1-> x74312780.78x2-> x31432680.68x2-> x4421111700.70x2-> x522321630.63x2-> x65212800.80x2-> x732311710.71x3-> x42341530.53x3-> x523122560.56x3-> x622123410.41x3-> x712322540.54x4-> x62314310.31x4-> x611233340.34x4-> x711233360.36x5-> x6121213460.46x5-> x712313400.40x6-> x712223430.43于是可以得到优先选择矩阵:??????????????????????=157.060.064.046.029.022.043.0154.066.059.020.030.040.046.0169 .044.037.014.036.034.031.0147.030.024.054.041.056.053.0132.028.071.080.063.070.068.0120.07 8.070.086.076.072.080.01)1(R70.0=λ,得λ-截矩阵为:Page 8??????????????????????=1000000010000000100000001000000010011010101111111)1(7.0Rλ-截矩阵的第一行元素都等于1,说明只有的优越度超过了0.70,所以学生为第一优越对象。)1(7.0R1x1x除去)1(R中第一优越对象所在的行和列,得到新的模糊优先关系矩阵1x)2(R

为:????????????????????=157.060.064.046.029.043.0154.066.059.020.040.046.0169.044.037.0 36.034.031.0147.030.054.041.056.053.0132.071.080.063.070.068.01)2(R取63.0=λ,得:

R=, )2(63.0????????????????????100100010100001100000100000010111111λ-截矩阵R的第一行元素都等于1, 应取x2为第二优越对象。)2(63.0除去R中第二优越对象x2 所在的行与列,得到新的模糊优先关系矩阵R 为)2()3(R(3)=????????????????157.060.064.046.043.0154.066.059.040.046.0169.044.036.034.03 1.0147.054.041.056.053.01,取46.0=λ,得Page 9R=, )3(46.0????????????????1111101111011100001110111可知x7 为第三优越对象。除去R 中第二优越对象x7所在的行与列,得到新的模糊优先关系矩阵R 为)3()4(R(4)=, ??????????????154.066.059.046.0169.044.034.031.0147.041.056.053.01取54.0=λ,得R=, )4(54.0??????????????1111011000100101可知x6 为第四优越对象。类似地,可得R(5)为R(5)=, ??????????169.044.031.0147.056.053.01取53.0=λ,得??????????=110010111)5(53.0R可知x3为第五优越对象,同样,????????=169.031.01)6(R 取69.0=λ,得????????=1101)6(69.0R可知x5为第六优越对象,因此7 名同学的排名为:x1, x2, x7, x6, x3, x5, x4

数学建模竞赛中应当掌握的十类算法(上)

1 十类常用算法

1. 蒙特卡罗算法。该算法又称随机性模拟算法,是通过计算机仿真来解决问题的算法,同时可以通过模拟来检验自己模型的正确性,几乎是比赛时必用的方法。

2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用MATLAB 作为工具。

3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题,很多时候这些问题可以用数学规划算法来描述,通常使用Lindo、Lingo 软件求解。

4. 图论算法。这类算法可以分为很多种,包括最短路、网络流、二分图等算法,涉及到图论的问题可以用这些方法解决,需要

认真准备。

5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法,竞赛中很多场合会用到。

6. 最优化理论的三大非经典算法:模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的,对于有些问题非常有帮助,但是算法的实现比较困难,需慎重使用。

7. 网格算法和穷举法。两者都是暴力搜索最优点的算法,在很多竞赛题中有应用,当重点讨论模型本身而轻视算法的时候,可以使用这种暴力方案,最好使用一些高级语言作为编程工具。

8. 一些连续数据离散化方法。很多问题都是实际来的,数据可以是连续的,而计算机只能处理离散的数据,因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。

9. 数值分析算法。如果在比赛中采用高级语言进行编程的话,那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。

10. 图象处理算法。赛题中有一类问题与图形有关,即使问题与图形无关,论文中也会需要图片来说明问题,这些图形如何展示以及如何处理就是需要解决的问题,通常使用MATLAB 进行处理。2.以下将结合历年的竞赛题,对这十类算法进行详细地说明

2.1 蒙特卡罗算法

大多数建模赛题中都离不开计算机仿真,随机性模拟是非常常见的算法之一。

举个例子就是97 年的A 题,每个零件都有自己的标定值,也都有自己的容差等级,而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案,

根本不可能去求解析解,那如何去找到最优的方案呢?随机性模拟搜索最优方案就是其中的一种方法,在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案,然后通过蒙特卡罗算法仿真出大量的方案,从中选取一个最佳的。另一个例子就是去年的彩票第二问,要求设计一种更好的方案,首先方案的优劣取决于很多复杂的因素,同样不可能刻画出一个模型进行求解,只能靠随机仿真模拟。

2.2 数据拟合、参数估计、插值等算法

数据拟合在很多赛题中有应用,与图形处理有关的问题很多与拟合有关系,一个例子就是98 年美国赛A 题,生物组织切片的三维插值处理,94 年A 题逢山开路,山体海拔高度的插值计算,还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法,观察数据的走向进行处理。此类问题在MATLAB中有很多现成的函数可以调用,熟悉MATLAB,这些方法都能游刃有余的用好。