016先进算法讲义

《016先进算法讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、程而开发出的一种算法。假如我们现在只有一些输入和相应的输出，而对如何由输入得到输出的机理并不清楚，那么我们可以把输入与输出之间的未知过程看成是一个“网络”，通过不断地给这个网络输入和相应的输出来“训练”这个网络，网络根据输入和输出不断地调节自己的各节点之间的权值来满足输入和输出。这样，当训练结束后，我们给定一个输入，网络便会根据自己已调节好的权值计算出一个输出。这就是神经网络的简单原理。2．神经元和神经网络的结构如上所述，神经网络的基本结构如下图所示：神经网络一般都有多层，分为输入层，输出层和隐含层，层数越多，计算结果越精确，但所需的时间也就越长，所以实际应用中要

3、根据要求设计网络层数。神经网络中每一个节点叫做一个人工神经元，他对应于人脑中的神经元，两者的结构比较如下图：一个人工神经元一般有多个输入和一个输出，另外有一个激发函数，不同的激发函数对应了不同的网络，也决定了网络的用途。3．神经网络的分类神经网络按照网络结构和激发函数的不同可分为许多种，我们在此只是对感知器和BP网络进行简介。感知器：最早也是最简单的一种神经网络，它的神经元激发函数为阶跃函数，其神经元结构如下图：感知器主要用于分类。BP网络：应用得最为广泛，最为重要的一种神经网络。这种网络一般有多层，网络结构如下：BP网络的激发函数一般采用S型函数，如正切或对数函

4、数，其神经元结构如下：BP网络的用途十分广泛，可用于以下方面：函数逼近：用输入矢量和相应的输出矢量训练一个网络逼近一个函数模式识别：用一个特定的输出矢量将它与输入矢量联系起来分类：把输入矢量以所定义的合适方式进行分类数据压缩：减少输出矢量维数以便于传输或存储4．神经网络在数学建模中的应用数学建模中有很多题目都可以用神经网络加以解决，比较典型的题目有：DNA序列分类题（2000年全国赛A题），癌症判断题（2001年北京大学数学建模竞赛），乳房癌的诊断题（2001年全国大学生数学建模夏令营C题）。下面我们使用神经网络的方法解决癌症判断题（2001年北京大学数学建模竞赛

5、），题目如下：附件中的文件给出了一个114个基因,60个人的基因表达水平的样本.其中前20个是癌症病人的基因表达水平的样本(其中还可能有子类),其后的是20个正常人的基因表达信息样本,其余的20个是待检测的样本(未知它们是否正常).(1).试设法找出描述癌症与正常样本在基因表达水平上的区别,建立数学模型,及识别方法,去预测待检测样本是癌症还是正常样本.(2).设计图示(可视化)方法,使得在你的数学模型下,尽量清楚地表现癌症与正常样本在基因表达水平上的区别,以及癌症样本中是否有子类.这道题是很典型的用神经网络的分类问题，只需用感知器神经网络便能完成此分类工作，我们用

6、前40组数据对网络进行训练，再用训练号的网络来计算后20组数据，便能得到分类的结果。详细的程序可参见本讲义附带的Matlab程序。5．神经网络的程序设计该讲义附带了如下程序资源：Matlab神经网络工具箱函数简介癌症判断题（2001年北京大学数学建模竞赛）的Matlab程序第二节遗传算法1．遗传算法的简单原理遗传算法(GeneticAlgorithm,GA)是一种基于自然群体遗传演化机制的高效探索算法，它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号

7、串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。我们先通过一个例子来了解遗传算法的原理：2假定我们要求函数f(x)=x的极大值，其中x为自然数，0≤x≤31。现在，我们将每一个数看成一个生命体，通过进化，我们看谁能最后生存下来，谁就是我们所寻找的数。①．编码我们将每一个数作为一个生命体，那么必须给其赋予一定的基因，这个过程叫做编码。我们可以

8、把变量x编