先进算法讲义 在本讲义中,我们将着重讲述一些数学建模中常用的算法,包括神经网络算法、遗传算 法、模拟退火算法和模糊数学方法。用这些算法可以较容易地解决一些很复杂的,常规算法 很难解决的问题。由于这些算法都有着很深的理论背景,因此,本讲义中不可能也没有必要 详细地讨论这些算法的理论,我们的目标在于应用,大家只需大概了解这些算法的原理,知 道能用这些算法解决一类什么样的问题,并能应用这些算法解决数学建模中的一些问题即 因为着眼于应用,所以我们还提供了一些程序代码,使用者只需套用这些程序,便可使 问题得到很好的解决。 第一节神经网络 神经网络的简单原理 人工神经网络是根据人的认识过程而开发出的一种算法。假如我们现在只有一些 输入和相应的输出,而对如何由输入得到输出的机理并不清楚,那么我们可以把输入 与输出之间的未知过程看成是一个“网络”,通过不断地给这个网络输入和相应的输 出来“训练”这个网络,网络根据输入和输出不断地调节自己的各节点之间的权值来 满足输入和输出。这样,当训练结束后,我们给定一个输入,网络便会根据自己已调 节好的权值计算出一个输出。这就是神经网络的简单原理。 2.神经元和神经网络的结构 如上所述,神经网络的基本结构如下图所示: 层 输出层 隐层 神经网络一般都有多层,分为输入层,输出层和隐含层,层数越多,计算结果越 精确,但所需的时间也就越长,所以实际应用中要根据要求设计网络层数 神经网络中每一个节点叫做一个人工神经元,他对应于人脑中的神经元,两者的 结构比较如下图
先进算法讲义 在本讲义中，我们将着重讲述一些数学建模中常用的算法，包括神经网络算法、遗传算 法、模拟退火算法和模糊数学方法。用这些算法可以较容易地解决一些很复杂的，常规算法 很难解决的问题。由于这些算法都有着很深的理论背景，因此，本讲义中不可能也没有必要 详细地讨论这些算法的理论，我们的目标在于应用，大家只需大概了解这些算法的原理，知 道能用这些算法解决一类什么样的问题，并能应用这些算法解决数学建模中的一些问题即 可。 因为着眼于应用，所以我们还提供了一些程序代码，使用者只需套用这些程序，便可使 问题得到很好的解决。 第一节 神经网络 1． 神经网络的简单原理 人工神经网络是根据人的认识过程而开发出的一种算法。假如我们现在只有一些 输入和相应的输出，而对如何由输入得到输出的机理并不清楚，那么我们可以把输入 与输出之间的未知过程看成是一个“网络”，通过不断地给这个网络输入和相应的输 出来“训练”这个网络，网络根据输入和输出不断地调节自己的各节点之间的权值来 满足输入和输出。这样，当训练结束后，我们给定一个输入，网络便会根据自己已调 节好的权值计算出一个输出。这就是神经网络的简单原理。 2． 神经元和神经网络的结构 如上所述，神经网络的基本结构如下图所示： 神经网络一般都有多层，分为输入层，输出层和隐含层，层数越多，计算结果越 精确，但所需的时间也就越长，所以实际应用中要根据要求设计网络层数。 神经网络中每一个节点叫做一个人工神经元，他对应于人脑中的神经元，两者的 结构比较如下图：
来自其他神经轴 末梢 末梢 树突 胞体 由突 突触 生物神经元 输入-y1 权值 神经元状态 ∑( 输出 y 加权求和國值 激发函数 神经元模型 个人工神经元一般有多个输入和一个输出,另外有一个激发函数,不同的激发 函数对应了不同的网络,也决定了网络的用途 3.神经网络的分类 神经网络按照网络结构和激发函数的不同可分为许多种,我们在此只是对感知器 和BP网络进行简介。 感知器 最早也是最简单的一种神经网络,它的神经元激发函数为阶跃函数,其神经元结 构如下图 XI X2~W2 ∑Xiwi)·y X 感知器主要用于分类 BP网络: 应用得最为广泛,最为重要的一种神经网络。这种网络一般有多层,网络结构如下
一个人工神经元一般有多个输入和一个输出，另外有一个激发函数，不同的激发 函数对应了不同的网络，也决定了网络的用途。 3． 神经网络的分类 神经网络按照网络结构和激发函数的不同可分为许多种，我们在此只是对感知器 和 BP 网络进行简介。 感知器： 最早也是最简单的一种神经网络，它的神经元激发函数为阶跃函数，其神经元结 构如下图： 感知器主要用于分类。 BP 网络： 应用得最为广泛，最为重要的一种神经网络。这种网络一般有多层，网络结构如下：
output Units Hidden units d888 BP网络的激发函数一般采用S型函数,如正切或对数函数,其神经元结构如下: XI w X W2 ∑Xiwi y n X BP网络的用途十分广泛,可用于以下方面: 函数逼近:用输入矢量和相应的输出矢量训练一个网络逼近一个函数 模式识别:用一个特定的输出矢量将它与输入矢量联系起来 分类:把输入矢量以所定义的合适方式进行分类 数据压缩:减少输出矢量维数以便于传输或存储 4.神经网络在数学建模中的应用 数学建模中有很多题目都可以用神经网络加以解决,比较典型的题目有:DNA序 列分类题(2000年全国赛A题),癌症判断题(2001年北京大学数学建模竞赛),乳 房癌的诊断题(2001年全国大学生数学建模夏令营C题)。下面我们使用神经网络的 方法解决癌症判断题(2001年北京大学数学建模竞赛),题目如下 所件中的文件给出了一个114个基因,60个人的基因表达水平的样本其中前20个是 癌症病人的基因表达水平的样本其中还可能有子类,其后的是20个正常人的基因表 达信息样本其余的20个是待检测的样本(未知它们是否正常 (1).试设法找出描述癌症与正常样本在基因表达水平上的区别建立数学模型及识别 方法去预测待检测样本是癌症还是正常样本 (2).设计图示(可视化方法,使得在你的数学模型下,尽量清楚地表现癌症与正常样 本在基因表达水平上的区别以及癌症样本中是否有子类
BP 网络的激发函数一般采用 S 型函数，如正切或对数函数，其神经元结构如下： BP 网络的用途十分广泛，可用于以下方面： 函数逼近：用输入矢量和相应的输出矢量训练一个网络逼近一个函数 模式识别：用一个特定的输出矢量将它与输入矢量联系起来 分类：把输入矢量以所定义的合适方式进行分类 数据压缩：减少输出矢量维数以便于传输或存储 4． 神经网络在数学建模中的应用 数学建模中有很多题目都可以用神经网络加以解决，比较典型的题目有：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)是一种基于自然群体遗传演化机制的高效探索 算法,它摒弃了传统的搜索方式,模拟自然界生物进化过程,采用人工进化的方式对 目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体, 并将每一个体编码成符号串形式,模拟达尔文的遗传选择和自然淘汰的生物进化过 程,对群体反复进行基于遗传学的操作(遗传,交叉和变异),根据预定的目标适应 度函数对每个个体进行评价,依据适者生存,优胜劣汰的进化规则,不断得到更优的 群体,同时以全局并行搜索方式来搜索优化群体中的最优个体,求得满足要求的最优 我们先通过一个例子来了解遗传算法的原理: 假定我们要求函数f(x)=x2的极大值,其中x为自然数,0≤x≤31。现在,我 们将每一个数看成一个生命体,通过进化,我们看谁能最后生存下来,谁就是我们所 寻找的数。 ①.编码 我们将每一个数作为一个生命体,那么必须给其赋予一定的基因,这个过程 叫做编码。我们可以把变量ⅹ编码成5位长的二进制无符号整数表示形式,比如 x=13可表示为01101的形式,也就是说,数13的基因为01101。 ②.初始群体的生成 由于遗传的需要,我们必须设定一些初始的生物群体,让其作为生物繁殖的 第一代,需要说明的是,初始群体的每个个体都是通过随机方法产生的,这样便 可以保证生物的多样性和竞争的公平性 ③.适应度评估检测 生物的进化服从适者生存,优胜劣汰的进化规则,因此,我们必须规定什么 样的基因是“优”的,什么样的基因是“劣”的,在这里,我们称为适应度。显 然,由于我们要求f(x)=x2的最大值,因此,能使f(x)=x2较大的基因是优 的,使∫(x)=x2较小的基因是劣的,因此,我们可以将∫(x)=x2定义为适应 度函数,用来衡量某一生物体的适应程度。 ④.选择 接下来,我们便可以进行优胜劣汰的过程,这个过程在遗传算法里叫做选择 意,选择应该是一个随机的过程,基因差的生物体不一定会被淘汰,只是其被 淘汰概率比较大罢了,这与自然界中的规律是相同的。因此,我们可以采取赌论 的方式来进行选择
这道题是很典型的用神经网络的分类问题，只需用感知器神经网络便能完成此分类工 作，我们用前 40 组数据对网络进行训练，再用训练号的网络来计算后 20 组数据，便能得到 分类的结果。详细的程序可参见本讲义附带的 Matlab 程序。 5． 神经网络的程序设计 该讲义附带了如下程序资源： Matlab 神经网络工具箱函数简介 癌症判断题（2001 年北京大学数学建模竞赛）的 Matlab 程序 第二节 遗传算法 1． 遗传算法的简单原理 遗传算法(Genetic Algorithm, GA)是一种基于自然群体遗传演化机制的高效探索 算法，它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对 目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体， 并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过 程，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应 度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的 群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优 解。 我们先通过一个例子来了解遗传算法的原理： 假定我们要求函数 的极大值，其中 2 f (x) = x x 为自然数，0≤x≤31。现在，我 们将每一个数看成一个生命体，通过进化，我们看谁能最后生存下来，谁就是我们所 寻找的数。 ①．编码 我们将每一个数作为一个生命体，那么必须给其赋予一定的基因，这个过程 叫做编码。我们可以把变量 x 编码成 5 位长的二进制无符号整数表示形式，比如 x=13 可表示为 01101 的形式，也就是说，数 13 的基因为 01101。 ②．初始群体的生成 由于遗传的需要，我们必须设定一些初始的生物群体，让其作为生物繁殖的 第一代，需要说明的是，初始群体的每个个体都是通过随机方法产生的，这样便 可以保证生物的多样性和竞争的公平性。 ③．适应度评估检测 生物的进化服从适者生存，优胜劣汰的进化规则，因此，我们必须规定什么 样的基因是“优”的，什么样的基因是“劣”的，在这里，我们称为适应度。显 然，由于我们要求 的最大值，因此，能使 较大的基因是优 的，使 较小的基因是劣的，因此，我们可以将 定义为适应 度函数，用来衡量某一生物体的适应程度。 2 f (x) = x 2 f (x) = x 2 f (x) = x 2 f (x) = x ④．选择 接下来，我们便可以进行优胜劣汰的过程，这个过程在遗传算法里叫做选择。 注意，选择应该是一个随机的过程，基因差的生物体不一定会被淘汰，只是其被 淘汰概率比较大罢了，这与自然界中的规律是相同的。因此，我们可以采取赌论 的方式来进行选择
⑤.交叉操作 接下来进行交叉繁殖,随机选出两个生物体,让其交换一部分基因,这样便 形成了两个新的生物体,为第二代。 ⑥.变异 生物界中不但存在着遗传,同时还存在着变异,在这里我们也引入变异,使 生物体的基因中的某一位以一定的概率发生变化,这样引入适当的扰动,能避免 局部极值的问题 以上的算法便是最简单的遗传算法,通过以上步骤不断地进化,生物体的基因便 逐渐地趋向最优,最后便能得到我们想要的结果。 2.遗传算法的步骤 从上面的例子中,我们便能得到遗传算法的一般步骤,如下图所示 编码和初始群体的形成 适应度的检测评估 选择 叉 变异 3.遗传算法的应用 遗传算法主要是用来寻优,它具有很多优点:它能有效地避免局部最优现象,有 及其顽强的鲁棒性,并且在寻优过程中,基本不需要任何搜索空间的知识和其他辅助 信息等等。 为了介绍遗传算法的应用,我们将前面的例子进行完,整个过程如下: 初始群体 ONol l000 0I000 100ll 的值 适应度f(x)=x2 选择概率 0.l4 0.49 0.06 0.31 选择上的计数(来自赌轮)1 交叉处 011010 110010 1000 101011 下一代群体 0l00 00l l01 l0000 x的值 适应度∫(x)=x2 l44 625 729 256
⑤．交叉操作 接下来进行交叉繁殖，随机选出两个生物体，让其交换一部分基因，这样便 形成了两个新的生物体，为第二代。 ⑥．变异 生物界中不但存在着遗传，同时还存在着变异，在这里我们也引入变异，使 生物体的基因中的某一位以一定的概率发生变化，这样引入适当的扰动，能避免 局部极值的问题。 以上的算法便是最简单的遗传算法，通过以上步骤不断地进化，生物体的基因便 逐渐地趋向最优，最后便能得到我们想要的结果。 2． 遗传算法的步骤 从上面的例子中，我们便能得到遗传算法的一般步骤，如下图所示： 3． 遗传算法的应用 遗传算法主要是用来寻优，它具有很多优点：它能有效地避免局部最优现象，有 及其顽强的鲁棒性，并且在寻优过程中，基本不需要任何搜索空间的知识和其他辅助 信息等等。 为了介绍遗传算法的应用，我们将前面的例子进行完，整个过程如下： 初始群体 01101 11000 01000 10011 x 的值 13 24 8 19 适应度 169 576 64 361 2 f (x) = x 选择概率 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 f (x) = x