神经网络与遗传算法

1、5.4 神经网络与遗传算法简介在本节中，我们将着重讲述一些在网络设计、优化、性能分析、通信路由优化、选择、神经网络控制优化中有重要应用的常用的算法，包括神经网络算法、遗传算法、模拟退火算法等方法。用这些算法可以较容易地解决一些很复杂的，常规算法很难解决的问题。这些算法都有着很深的理论背景，本节不准备详细地讨论这些算法的理论，只对算法的原理和方法作简要的讨论。5.4.1 神经网络1. 神经网络的简单原理 人工神经网络（ Artificial Neural Networks， 简写为ANNs）也简称为神经网络（NNs）或称作连接模型（Connectionist Model） ，是对人脑或自然神经网

2、络（Natural Neural Network）若干基本特性的抽象和模拟。人工神经网络以对大脑的生理研究成果为基础的，其目的在于模拟大脑的某些机理与机制，实现某个方面的功能。所以说, 人工神经网络是由人工建立的以有向图为拓扑结构的动态系统，它通过对连续或断续的输入作出状态相应而进行信息处理。它是根据人的认识过程而开发出的一种算法。假如我们现在只有一些输入和相应的输出，而对如何由输入得到输出的机理并不清楚，那么我们可以把输入与输出之间的未知过程看成是一个“网络”，通过不断地给这个网络输入和相应的输出来“训练”这个网络，网络根据输入和输出不断地调节自己的各节点之间的权值来满足输入和输出。这样，当

3、训练结束后，我们给定一个输入，网络便会根据自己已调节好的权值计算出一个输出。这就是神经网络的简单原理。2. 神经元和神经网络的结构如上所述，神经网络的基本结构如图5.35所示： 图5.35神经网络一般都有多层，分为输入层，输出层和隐含层，层数越多，计算结果越精确，但所需的时间也就越长，所以实际应用中要根据要求设计网络层数。 神经网络中每一个节点叫做一个人工神经元，他对应于人脑中的神经元。人脑神经元由细胞体、树突和轴突三部分组成，是一种根须状蔓延物。神经元的中心有一闭点，称为细胞体，它能对接受到的信息进行处理，细胞体周围的纤维有两类，轴突是较长的神经纤维，是发出信息的。树突的神经纤维较短，而分支

4、众多，是接收信息的。一个神经元的轴突末端与另一神经元的树突之间密切接触，传递神经元冲动的地方称为突触。经过突触的信息传递是有方向性的，不同的突触进行的冲动传递效果不一样，有的使后一神经元发生兴奋，有的使其发生抑制。由人脑神经元的工作机理，人们构造了人工神经元的数学模型，它是人脑的模拟和简化，如图5.36所示。图5.36 McCulloch-Pitts网络在图中，是表示神经元对信息的感知能力，称为关联权，称为输出函数或激活函数，采用激活函数的人工神经网络也称阈网络。McCulloch-Pitts输出函数定义为其中，为符号函数，称为阈值。一般来说，一个人工神经元有多个输入和一个输出，另外有一个激活

5、函数，不同的激发函数对应了不同的网络，也决定了网络的用途。从方程可以看出，当 确定时，任给一组输入，也就很容易得到输出。而现在我们的想法是：对给定的输入，确定权数，使得通过方程计算出来的输出尽可能与实际值吻合，这即是学习的过程。学习也称为训练，指的是通过神经网络所在环境的刺激作用调整神经网络的权数，使得神经网络对外部环境以一种新的方式作出反应。学习分为有指导学习和无监督学习：在有正确输入输出数据条件下调整和确定权数的方法称为有指导学习；而在只知输入数据不知输出结果的前提下确定权数的方法称为无监督学习。人工神经网络的主要工作就是通过学习，建立模型和确定的值。神经网络按照网络结构和激发函数的不同可

6、分为许多种，我们在此只对感知器、BP网络及Hopfield神经网络进行简介。 3感知机首先介绍单层前向神经网络。单层前向神经网络的模型结构如图5.37所示。或用矩阵表示为 其中，为权系数矩阵，分别为输入向量、输出向量及阈值向量。确定权数的基本思想是修正使得输入输出偏差尽可能小。权的修正公式为：，其中，分别表示第组用于学习的输入和期望输出数据，称为学习效率，用于控制调整速度。与权值修正原理类似，阈值修正公式可假设为：，通过更新权数和阈值使得输入输出偏差趋于零。若将激活函数取为阶跃函数，上述思想即是感知机原理。图5.37由此，我们给出感知机学习规则算法步骤为：用表示学习步骤的序号，表示学习前的神经

7、网络的初始状态。第1步：赋初值。给网络上权数和阈值赋初值，如； 第2步：计算样本实际输出。选择一个样本作为网络输入，计算样本在目前神经网络中的实际输出。如，对于第个样本，感知机输出为：， 其中，第3步：计算误差。计算感知机输出的实际结果与期望输出之差：第4步：权数修正。如果，则转第2步，否则调整权值：第5步：若训练样本已完全输入或输出误差小于预设值，则学习结束；否则，转第2步继续学习。如果对给定的两类样本数据(通常就是用于学习的输入数据)，在空间中可以用一条直线（平面）将其分开，则称该样本数据是线性样本，否则称为非线性样本，对样本进行分类或识别即属于人工神经网络的重要应用之一。感知机可以识别二

8、值逻辑加问题，而不能识别异或问题。对于非线性问题，可以用反向传播（BP）模型解决。4. BP网络 图5.38 多层前向神经网络结构BP网络应用得最为广泛，最为重要的一种神经网络。这种网络一般有多层，有输入层，输出层和隐含层，上一层的输出即是下一层的输入，输出层所在的层数就是神经网络的层数。一般的多层前向神经网络结构如图5.38所示。在实际应用中，BP网络的激活函数一般采用S型函数：， 这是因为S型函数有很好的函数特性，其效果又近似于符号函数，现主要讨论采用S型函数的多层前向神经网络的学习方法。假设有一个层的神经网络，从第0层到第1层的原始输入向量、权矩阵、第1层神经元接受向量和第1层输出向量以

9、及它们之间的关系为：，第层到第层的权矩阵、神经元接受向量和输出向量以及它们之间的关系分别为：， 其中，。我们先讨论单样本学习规则。学习规则是：确定，使得最小，其中为理想输出。采用S型函数的前向多层神经网络的反推学习(BP)算法步骤如下：第1步：选定学习的数组，随机确定初始权矩阵；第2步：用学习数据计算；第3步：计算 ，其中，。 ， 时， 其中，。第4步：反向修正，修正公式为：， 其中，。第5步：循环利用个学习样本，重复第2步第4步，对网络权数进行调整，直到整个训练集误差最小（网络达到稳定状态）。当激活函数时，代入、使计算可以得以简化。BP网络的用途十分广泛，可用于以下方面：函数逼近：用输入矢量

10、和相应的输出矢量训练一个网络逼近一个函数；模式识别：用一个特定的输出矢量将它与输入矢量联系起来；分类：把输入矢量以所定义的合适方式进行分类；数据压缩：减少输出矢量维数以便于传输或存储。 5. Hopfield神经网络前面介绍的感知机和BP网络都属于前向网络。前向网络结构简单、易于编程，但计算能力不够强大。反馈神经网络是一个反馈动力学系统，具有更强的计算能力。其一般结构如图5.39所示。图5.39 反馈神经网络的一般结构反馈型神经网络中，神经元之间信息交互关系不再是从一层传递到另一层，而是各神经元之间都存在关系，存在从输出到输入的反馈，所以反馈型神经网络可能是不稳定的。反馈型神经网络有连续型和离

11、散型两类，连续型用微分方程描述，离散型用差分方程描述。J.Hopfield将神经网络和动力学系统研究结合起来，于20世纪80年代提出了一个全新的神经网络模型Hopfield神经网络，并把一个最优化问题的目标函数转换成网络的能量函数，把问题的变量对应于网络的状态，求解出了旅行商问题的准优解。Hopfield神经网络属于反馈型神经网络，若Hopfield神经网络的权数矩阵是对角线元素为0的对称矩阵，即：，则可以证明这种神经网络是稳定网络，即反馈与迭代的计算过程所产生的变动越来越小，一直到达平衡状态。1）离散Hopfield神经网络离散Hopfield神经网络神经元的输出为离散值0和1，分别代表神经

12、元抑制和激活状态，若神经元的输出信息小于阈值，神经元输出值为0；反之输出值为1。对于有个神经元的离散Hopfield神经网络，其权数矩阵为维对称阵，每个神经元都有一个阈值，故有一个维的阈值向量，权数矩阵和阈值矢量就定义了唯一一个个神经元的离散Hopfield神经网络。Hopfield网络中的神经元公式可表示为：其中，表示神经元的初始状态，表示神经元在时刻的状态，同时也是神经元在时刻的输出，表示神经元的阈值。一个个神经元的离散Hopfield网络在时刻的状态可以用一个维向量表示为：。若采用符号激活函数时，将Hopfield网络的能量函数定义为：任意神经元的能量函数为：容易推出从时刻到时刻的能量变

13、化量为由于采用的是符号激活函数，所以无论神经元的状态变化如何，显然有，其中等号仅在神经元的状态不变时成立。又由于神经元的任意性，所以当网络按某一规则进行状态更新后，网络的总能量在减少。这样经过不断的迭代，网络最终达到稳定状态。在算法的构造上可以采用同步和异步两种方式，异步算法就是每次只调节一个神经元，其它神经元保持不变。同步算法就是同一时刻对所有神经元同时调整。下面仅给出Hopfield网络异步算法的基本步骤，对于同步，读者不难自己给出。Hopfield网络异步算法：第1步：初始化。任选一个初始状态；第2步：更新状态。随机选取一个神经元，进行状态更新： 第3步：检验。检验是否为网络的平衡点，若

14、是转第4步；否则，转第2步；第4步：输出。输出。2）连续Hopfield神经网络Hopfield利用模拟电子线路功能构造了反馈型神经网络的电路模型，建立的能量函数表达式为（5-140） 其中，为Sigmoid函数，为神经元和神经元之间的连接权数。，对应电路中的电阻，为神经元的接受值，为外部偏置电流输入值，为增益项。对应的连续Hopfield神经网络状态变化用微分方程表示为（5-141） 其中，是与有关的常数，当时，。（5-140）和（5-141）有如下关系： （5-142）容易证明，若为单调增函数，有：，且当且仅当时，。所以，连续Hopfield神经网络的状态总是向着能量减少的方向运动的，因此

15、网络总能收敛到稳定状态，网络的稳定点同时也是能量的极小点。具体地，Hopfield神经网络的计算步骤：第1步：针对实际的组合优化问题构造能量函数，使得能量函数有好的稳定性；第2步：由能量函数，根据（5-142）的关系求解出Hopfield神经网络状态变化方程（5-141）；第3步：用数值方法（如Matlab软件）求解方程（5-141）得到平衡点，得极小值。需要注意的是： 能量的极小点有局部极小点和全局极小点两类，在具体的数值计算过程中，难免会陷入局部极小，所以有吸引子的热点研究。为了避免局部极小，可以采用多种方法的组合，如与遗传算法、模拟退火等方法的结合。 无论对离散型还是连续型的Hopfie

16、ld神经网络，只要权值矩阵是对称阵，网络就是稳定的，但由于Hopfield神经网络神经元的连接权值在整个计算过程中是不变的，所以Hopfield神经网络不具有学习能力。6. 神经网络算法的应用实例 1）地震级预测表5.3 学习样本集及内符结果频度值值缺震蠕变能量期望输出实际输出震级M0.2700.600.99540.87960.10930.14723.94.00.10.1760.660.97030.82050.64020.22174.84.90.10.1240.760.68570.76050.38020.17984.94.8-0.10.0740.850.79330.6360.94090.426

17、34.04.30.30.1920.630.85070.83530.76050.37034.14.30.20.2350.7110.80480.54400.22154.04.10.10.2120.700.82340.82120.73570.39054.44.70.30.1250.740.70370.75830.37390.17985.04.9-0.10.2100.680.82770.82340.74530.38334.34.70.40.0740.830.79430.6520.94200.42654.04.30.30.0930.570.91060.82370.57070.17213.94.00.10

18、.1610.550.90030.85960.85260.1313.94.10.20.1360.720.87430.74370.28610.51064.14.0-0.10.1780.750.90030.72360.28020.31073.94.20.30.1610.690.78430.78820.57730.55865.55.1-0.40.1430.700.6010.77850.58810.29424.04.40.40.1530.430.809310.40030.23204.14.0-0.10.1860.670.96510.81170.63960.86504.85.00.20.1270.750.

19、71340.73830.29420.59053.74.30.60.2310.6910.80030.53390.21784.04.10.1现选取某地区20组地震数据（每组数据有诸如频度、蠕变、能量、值、缺震、值等具有代表性的六个指标）作为输入，目的是预测震级，因此选择输入层为6个节点，输出层为1个节点，隐层节点确定为2个。用函数作为激活函数。建立神经网络模型，对地震样本数据采用BP算法进行学习，以期对地震级进行有效预测，如表5.3所示。需要注意的是，在隐层结点确定的情况下，由于训练次数过大会使测试误差增大，影响网络的外推能力。故在训练过程中每经过一定训练次数后，要停止训练并测试其测试误差，当发现

20、测试误差开始上升时，网络便达到最佳训练次数，此时网络便具有最佳的外推能力。为检验该网络对预报震级的效能如何，能否达到要求的精度还必须进行内符检验。内符情况如表5.3，可以看出我们所构造的用于该地区地震活动预测的神经网络模型基本能识别训练样本，如果取，内符检验正确率为95%。外推能力检验采用交叉法进行，把同样的训练样本分成7，7，6三个子集，每次抽出一个子集不参加训练，用它来测试外推能力，分析结果如表5.4。可以看出最大预测震级与实际震级之差为0.7，如果限定为预报正确，则预报震级的准确率为85%。表5.4 预测效能分析编号实际震级检验震级震级差M13.93.3-0.624.04.30.334.

21、13.6-0.544.34.60.353.84.00.264.44.10.374.03.7-0.385.04.6-0.493.94.60.7105.15.40.3114.03.6-0.4123.83.6-0.2135.55.4-0.1143.94.1-0.2153.93.5-0.4164.65.20.6173.94.00.4184.94.8-0.1193.94.30.4204.44.0-0.42) 基于Hopfield网络的TSP问题求解TSP（Traveling salesman Problem）问题描述：一个装备保障人员欲到个营区去补给装备，每两个营区和之间的距离为，如何选择一条道路使得装

22、备保障人员每个营区走一遍后回到起点且所走路径最短。如果固定一个营区为起终点，则枚举个营区需要个枚举，若以计算机1秒可以完成24个营区所有路径枚举为单位，则营区数为25时需24秒， 营区数为26时需10分，营区数为时需10.8年，营区数为31时需325年，计算量为，TSP问题属于NP,故枚举法解TSP问题是个不好的方法。下面给出这个问题具体的神经网络求解方法。用一个矩阵表示TSP的解，其第行表示装备保障人员到达该营区的顺序，第行由数字0，1组成一个维向量，其中只能有一个分量为1，1所在的序数表示装备保障人员到达的序数。如向量（00100）表示商人第3个访问该营区。下面的矩阵表示一个五营区TSP问

23、题的一个解。它是一个置换矩阵，表示商人行走的路线为：。由此构造个神经元的神经网络，对应位置的神经元，其输出为，输入为，两个营区和的距离为，各营区距离信息通过建立能量函数表达式产生对突触权值的约束。能量函数为：其中，为惩罚因子，表示城市的第个神经元的状态，表示营区的第个神经元到营区的第个神经元的连接权。第一项表示仅当所有的营区最多只被访问一次时取得极小值0，第二项表示仅当每次最多只被访问一个营区时取得极小值0，第三项表示当且仅当所有的个营区一共被访问次时取得最小值0，第四项表示按照当前的访问路线的安排，所需要走的路径的总长度。相应的连接矩阵城市x在第i个被访问城市x不在第i个被访问对四个惩罚因子

24、，通常取较大正数值。利用Hopfield网络求解TSP问题，可以得到一组接近最优（也包括最优）的解，效果较为满意，表现出引人注目的潜在能力。5.4.2 遗传算法1. 遗传算法的简单原理 遗传算法(Genetic Algorithm，GA)是一种基于自然群体遗传演化机制的高度并行、随机、自适应高效探索算法，它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数

25、对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。由于其具有健壮性，特别适合于处理传统搜索算法解决不好的复杂的和非线性问题。我们先通过一个例子来了解遗传算法的原理： 假定我们要求函数的极大值，其中为自然数，。现在，我们将每一个数看成一个生命体，通过进化，我们看谁能最后生存下来，谁就是我们所寻找的数。 编码 我们将每一个数作为一个生命体，那么必须给其赋予一定的基因，这个过程叫做编码。我们可以把变量编码成5位长的二进制无符号整数表示形式，比如可表示为01101的形式，也就是说，数13的基因为01101。

26、 初始群体的生成 由于遗传的需要，我们必须设定一些初始的生物群体，让其作为生物繁殖的第一代，需要说明的是，初始群体的每个个体都是通过随机方法产生的，这样便可以保证生物的多样性和竞争的公平性。 适应度评估检测 生物的进化服从适者生存，优胜劣汰的进化规则，因此，我们必须规定什么样的基因是“优”的，什么样的基因是“劣”的，在这里，我们称为适应度。显然，由于我们要求的最大值，因此，能使较大的基因是优的，使较小的基因是劣的，因此，我们可以将定义为适应度函数，用来衡量某一生物体的适应程度。 选择 接下来，我们便可以进行优胜劣汰的过程，这个过程在遗传算法里叫做选择。注意，选择应该是一个随机的过程，基因差的生

27、物体不一定会被淘汰，只是其被淘汰概率比较大罢了，这与自然界中的规律是相同的。因此，我们可以采取赌论的方式来进行选择。 交叉操作 接下来进行交叉繁殖，随机选出两个生物体，让其交换一部分基因，这样便形成了两个新的生物体，为第二代。 变异 生物界中不但存在着遗传，同时还存在着变异，在这里我们也引入变异，使生物体的基因中的某一位以一定的概率发生变化，这样引入适当的扰动，能避免局部极值的问题。 以上的算法便是最简单的遗传算法，通过以上步骤不断地进化，生物体的基因便逐渐地趋向最优，最后便能得到我们想要的结果。 2. 基本遗传算法的步骤 从上面的例子中，我们便能得到遗传算法的一般步骤，第1步： 编码。选择问

28、题的一个编码，给出一个有个染色体的初始群体，；第2步： 对群体中的每个染色体，计算它的适应函数；第3步：若停止规则满足，则算法停止；否则，计算概率（5-143）并以概率(5-143)从中随机选一些染色体构成一个种群；第4步：通过交叉，交叉概率为，得到有个染色体的；第5步：以一个较小的概率，使得一个染色体的基因发生变异，形成一个新的群体返回第2步。种群的选取方式（5.143）称为轮盘赌。在实际应用中，交叉概率一般取为： 0.750.95；变异概率取为：0.0050.01。一般流程如图图5.40所示： 图5.40 基本遗传算法的步骤由此也可以看出，与传统的搜索方法相比，遗传算法是采用概率的变迁规则

29、来指导搜索方向，而不采用确定性搜索规则。 对搜索空间没有任何特殊要求（如连通性、凸性等），只利用适应性信息，不需要 导数等其它辅助信息，适应范围更广。搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，并易于并行化。3. 遗传算法的基本特点1）结构特点遗传算法是以适应值提供的启发式信息进行搜索的，与其他启发式(模拟退火、爬山法、神经网络等) 方法相比，在结构和工作过程方面的特点见表5.5。表5.5遗传算法的结构特点适应性结构定长字符串组成的种群系统状态形式种群初始结构选取随机产生个体组成种群循环终止条件设定的可接受水平(代数)适应值度量规范化的适应

30、值函数产生结果方法当前种群中的最好个体变更结构方式复制、交叉、变异及其他控制参数种类， ，2）实验性能方面的特点高效性：遗传算法具有大范围全局搜索的特点，与问题领域无关，前期工作量比少；健壮性：遗传算法的搜索是用种群作为基本单元，采用3个不同作用的基本算子进行搜索的，解的结果随时间增加而趋于稳定，不受初始解的影响，而且不因实例的不同而变；通用性和灵活性：遗传算法可用于多种优化搜索问题， 解题程序可以通用，针对不同的实例，适当调整算子参数， 就可以使算法执行获得最佳的解结果和占用CPU机时的关系。4. 遗传算法的应用 遗传算法主要是用来寻优，它具有很多优点：它能有效地避免局部最优现象，有及其顽强

31、的鲁棒性，并且在寻优过程中，基本不需要任何搜索空间的知识和其他辅助信息等等。 为了理解遗传算法的思想，我们将前面的例子进行完，整个过程如下：初始群体 01101 11000 01000 10011x的值 13 24 8 19适应度 169 576 64 361选择概率 0.14 0.49 0.06 0.31选择上的计数（来自赌轮） 1 2 0 1交叉处 0110|1 1100|0 11|000 10|011下一代群体 01100 11001 11011 10000x的值 12 25 27 16适应度 144 625 729 256下面再看一个基于遗传算法的最短路径求解问题：最短路径问题可以用图

32、论描述，现求解如图5.41所示的图15点加权有向图从顶点1到顶点15的最短路径。图5.41 15点加权有向图用遗传算法求解最短路径需经如下几个步骤：第1步：染色体编码。对于给定的图，将图中各顶点按顶点号自然排序，然后按此顺序将每个待选顶点作为染色体的一个基因，当基因值为1时，表示相应的顶点被选入该条路径中，否则反之。此染色体中的基因排列顺序即为各顶点在此通路中出现的先后顺序，染色体的长度应等于该图中顶点的个数。第2步：计算每个个体适应度。对具有个顶点的图，已知各顶点的边长度，把到间一条通路长度定义为适应函数，求该优化问题就是要寻找解，使最小。第3步：选择操作。选择作为交叉的双亲，是根据前代染色

33、体的适应函数所确定的，质量好的个体，即从起点到终点路径长度最短的个体被选中的概率最大。第4步：交叉与变异操作。将被选中的两个染色体进行交叉操作的过程是先产生一个随机数，确定交叉点位于染色体的第几位基因上，然后在此位置进行部分基因互换。变异操作是将染色体中某位基因逆换，即由1变为0，或反之。变异的意义为在某条路径上去掉或增加某顶点，但这样做的结果不一定能使路径长度减少，也就是说有可能使各代中产生的比较好的方案在遗传过程中丢失，迟缓了获得最优解的速度。为使算法尽可能快地获得更好的解，改善遗传算法的收敛性，在变异操作时，可增加个体寻优的自学习过程，即在某位基因互换后新算法所产生的染色体的适应函数值，若适应函数值更小，即获得路径更短，则保留；否则保持原来的解不变。若有连续次没有得到更好的解，则该过程结束。其中，表示从起点到终点的顶点数。需要注意的是，交叉率不可太小，因为太小会延缓获得最优解的进度；变异率对规模大的优化问题影响较大，取值要小。群体中个体数的选取宜大一些。若太小有可能会得不到最优解。经使用遗传算法，本例的最短路径解集为：最短路径等于14。目前，遗传算法所涉及的主要领域还有自动控制、规划设计、组合优化、图象处理、信号处理等。可见，遗传算法的应用研究已从初期的组合优化求解拓展到了许多更新、更工程化的应用方面，它是现代有关智能计