神经网络与遗传算法

5.4神经网络与遗传算法简介在本节中，我们将着重讲述一些在网络设计、优化、性能分析、通信路由优化、选择、神经网络控制优化中有重要应用的常用的算法，包括神经网络算法、遗传算法、模拟退火算法等方法。用这些算法可以较容易地解决一些很复杂的，常规算法很难解决的问题。这些算法都有着很深的理论背景，本节不准备详细地讨论这些算法的理论，只对算法的原理和方法作简要的讨论。5.4.1神经网络1.神经网络的简单原理人工神经网络（ArtificialNeuralNetworks，简写为ANNs）也简称为神经网络（NNs）或称作连接模型（ConnectionistModel），是对人脑或自然神经网络（NaturalNeuralNetwork）若干基本特性的抽象和模拟。人工神经网络以对大脑的生理研究成果为基础的，其目的在于模拟大脑的某些机理与机制，实现某个方面的功能。所以说,人工神经网络是由人工建立的以有向图为拓扑结构的动态系统，它通过对连续或断续的输入作出状态相应而进行信息处理。它是根据人的认识过程而开发出的一种算法。假如我们现在只有一些输入和相应的输出，而对如何由输入得到输出的机理并不清楚，那么我们可以把输入与输出之间的未知过程看成是一个“网络”，通过不断地给这个网络输入和相应的输出来“训练”这个网络，网络根据输入和输出不断地调节自己的各节点之间的权值来满足输入和输出。这样，当训练结束后，我们给定一个输入，网络便会根据自己已调节好的权值计算出一个输出。这就是神经网络的简单原理。2.神经元和神经网络的结构如上所述，神经网络的基本结构如图5.35所示：输入层输出层1隐层隐层2图5.35神经网络一般都有多层，分为输入层，输出层和隐含层，层数越多，计算结果越精确，但所需的时间也就越长，所以实际应用中要根据要求设计网络层数。神经网络中每一个节点叫做一个人工神经元，他对应于人脑中的神经元。人脑神经元由细胞体、树突和轴突三部分组成，是一种根须状蔓延物。神经元的中心有一闭点，称为细胞体，它能对接受到的信息进行处理，细胞体周围的纤维有两类，轴突是较长的神经纤维，是发出信息的。树突的神经纤维较短，而分支众多，是接收信息的。一个神经元的轴突末端与另一神经元的树突之间密切接触，传递神经元冲动的地方称为突触。经过突触的信息传递是有方向性的，不同的突触进行的冲动传递效果不一样，有的使后一神经元发生兴奋，有的使其发生抑制。由人脑神经元的工作机理，人们构造了人工神经元的数学模型，它是人脑的模拟和简化，如图5.36所示。1x2xnx1w2wnwiizwx()fzy树突突触细胞体轴突图5.36McCulloch-Pitts网络在图中，iw是表示神经元对信息ix的感知能力，称为关联权，fz称为输出函数或激活函数，采用激活函数的人工神经网络也称阈网络。McCulloch-Pitts输出函数定义为1sgn(),niiiyfzwx其中，sgn()为符号函数，称为阈值。一般来说，一个人工神经元有多个输入和一个输出，另外有一个激活函数，不同的激发函数对应了不同的网络，也决定了网络的用途。从方程可以看出，当iw确定时，任给一组输入1,,ixin，，也就很容易得到输出。而现在我们的想法是：对给定的输入，确定权数iw，使得通过方程计算出来的输出尽可能与实际值吻合，这即是学习的过程。学习也称为训练，指的是通过神经网络所在环境的刺激作用调整神经网络的权数iw，使得神经网络对外部环境以一种新的方式作出反应。学习分为有指导学习和无监督学习：在有正确输入输出数据条件下调整和确定权数iw的方法称为有指导学习；而在只知输入数据不知输出结果的前提下确定权数的方法称为无监督学习。人工神经网络的主要工作就是通过学习，建立模型和确定iw的值。神经网络按照网络结构和激发函数的不同可分为许多种，我们在此只对感知器、BP网络及Hopfield神经网络进行简介。3．感知机首先介绍单层前向神经网络。单层前向神经网络的模型结构如图5.37所示。或用矩阵表示为()TYfWX其中，()ijmnWw为权系数矩阵，XY，，分别为输入向量、输出向量及阈值向量。确定权数ijw的基本思想是修正ijw使得输入输出偏差尽可能小。权的修正公式为：(1)()(),()(())ijWtWtWtWtwt，()(()())()ijtjjimnwtdtytxt，其中，()()1,,1,,ijxtdtimjn，，，分别表示第t组用于学习的输入和期望输出数据，t称为学习效率，用于控制调整速度。与权值修正原理类似，阈值修正公式可假设为：1(1)()(),()(()())tjjnttttdtyt，通过更新权数和阈值使得输入输出偏差趋于零。若将激活函数()f取为阶跃函数，上述思想即是感知机原理。1xmx2x1z2znz1yny2y11w12w21w22w1nw2nwmnw1mw2mw输入层输出层图5.37由此，我们给出感知机学习规则算法步骤为：用t表示学习步骤的序号，0t表示学习前的神经网络的初始状态。第1步：赋初值。给网络上权数和阈值赋初值，如00ijiw，；第2步：计算样本实际输出。选择一个样本作为网络输入，计算样本在目前神经网络中的实际输出。如，对于第p个样本，感知机输出为：1()(()())nYpYpYp，，，其中，()()1,,iijjiYpfwxin，第3步：计算误差。计算感知机输出的实际结果与期望输出之差：tDpYp第4步：权数修正。如果0t，则转第2步，否则调整权值：(1)()(),()iiiitiWpWpWpWpx第5步：若训练样本已完全输入或输出误差小于预设值，则学习结束；否则，转第2步继续学习。如果对给定的两类样本数据(通常就是用于学习的输入数据)，在空间中可以用一条直线（平面）将其分开，则称该样本数据是线性样本，否则称为非线性样本，对样本进行分类或识别即属于人工神经网络的重要应用之一。感知机可以识别二值逻辑加问题，而不能识别异或问题。对于非线性问题，可以用反向传播（BP）模型解决。4.BP网络ijijwk第层1k第层1k第－层图5.38多层前向神经网络结构BP网络应用得最为广泛，最为重要的一种神经网络。这种网络一般有多层，有输入层，输出层和隐含层，上一层的输出即是下一层的输入，输出层所在的层数就是神经网络的层数。一般的多层前向神经网络结构如图5.38所示。在实际应用中，BP网络的激活函数一般采用S型函数：1()1zfze，这是因为S型函数有很好的函数特性，其效果又近似于符号函数，现主要讨论采用S型函数的多层前向神经网络的学习方法。假设有一个K层的神经网络，从第0层到第1层的原始输入向量、权矩阵、第1层神经元接受向量和第1层输出向量以及它们之间的关系为：012nxxXx，0111()ijnnWw，11112111TnzzZWXz，11112111()nyyYfZy第1k层到第k层的权矩阵、神经元接受向量和输出向量以及它们之间的关系分别为：1()ijkkkknnWw，121kkkTkkkknzzZWYz，12()kkkkkknyyYfZy其中，()kkiiyfz。我们先讨论单样本学习规则。学习规则是：确定W，使得()()()TKKFWDYDY最小，其中12()KTnDddd，，，为理想输出。采用S型函数的前向多层神经网络的反推学习(BP)算法步骤如下：第1步：选定学习的数组{()()}1,2,,XtDttT，，，随机确定初始权矩阵(0)W；第2步：用学习数据()Xt计算12()()()kYtYtYt，，，；第3步：计算①1111121()2()KKKKKTKKijnnKnyyFWBwy，121112,,,KKKKKnKKKKKKndydydyBdiagWBdzdzdz其中，111221,,,,KKTKKKKnnKBdydydyWI。②2112122212()2()KKKKKTKKijnnKnyyFWBwy，111112111112,,,KKKKKnKKKKKKndydydyBdiagWBdzdzdz③2kK时，1111121()2()kkkkkTkkijnnknyyFWBwy，其中，121112,,,kkkkknkkkkkkndydydyBdiagWBdzdzdz。第4步：反向修正()Wt，修正公式为：(1)()(),1,,1kkkWtWtWtkKK，，其中，1111121()()1()()()(())2()kkkkkTkttkkijnnknytytFWWttBtwyt。第5步：循环利用T个学习样本，重复第2步～第4步，对网络权数进行调整，直到整个训练集误差最小（网络达到稳定状态）。当激活函数1()1xfxe时，1()(1())1,,1,,kjkkjjkkkjdyfzfzinjndz，，，代入①、②、③使计算可以得以简化。BP网络的用途十分广泛，可用于以下方面：①函数逼近：用输入矢量和相应的输出矢量训练一个网络逼近一个函数；②模式识别：用一个特定的输出矢量将它与输入矢量联系起来；③分类：把输入矢量以所定义的合适方式进行分类；④数据压缩：减少输出矢量维数以便于传输或存储。5.Hopfield神经网络前面介绍的感知机和BP网络都属于前向网络。前向网络结构简单、易于编程，但计算能力不够强大。反馈神经网络是一个反馈动力学系统，具有更强的计算能力。其一般结构如图5.39所示。ijijw图5.39反馈神经网络的一般结构反馈型神经网络中，神经元之间信息交互关系不再是从一层传递到另一层，而是各神经元之间都存在关系，存在从输出到输入的反馈，所以反馈型神经网络可能是不稳定的。反馈型神经网络有连续型和离散型两类，连续型用微分方程描述，离散型用差分方程描述。J.Hopfield将神经网络和动力学系统研究结合起来，于20世纪80年代提出了一个全新的神经网络模型—Hopfield神经网络，并把一个最优化问题的目标函数转换成网络的能量函数，把问题的变量对应于网络的状态，求解出了旅行商问题的准优解。Hopfield神经网络属于反馈型神经网络，若Hopfield神经网络的权数矩阵是对角线元素为0的对称矩阵，即：0ijw，ijjiww，则可以证明这种神经网络是稳定网络，即反馈与迭代的计算过程所产生的变动越来越小，一直到达平衡状态。1）离散Hopfield神经网络离散Hopfield神经网络神经元的输出为离散值0和1，分别代表神经元抑制和激活状态，若神经元的输出信息小于阈值，神经元输出值为0；反之输出值为1。对于有n个神经元的离散Hopfield神经网络，其权数矩阵为nn维对称阵，每个神经元都有一个阈值，故有一个n维的阈值向量，权数矩阵和阈值矢量就定义了唯一一个n个神经元的离散Hopfield神经网络。Hopfield网络中的神经元公式可表示为：(0)iiyx1()()nijiijhtwyt(1)(())iiiytfht其中，(0)iy表示神经元i的初始状态，(1)iyt表示神经元i在1t时刻的状态，同时也是神经元i在1t时刻的输出，i表示神经元i的阈值。一个n个神经元的离散Hopfield网络在t时刻的状态可以用一个n维向量表示为：12()