1、第第7章章 智能最优化算法智能最优化算法 随着仿生学、遗传学和人工智能科学的发展，从随着仿生学、遗传学和人工智能科学的发展，从20世世纪纪70年代以来，科学家相继将遗传学、神经网络科学的原年代以来，科学家相继将遗传学、神经网络科学的原理和方法应用到最优化领域，形成了一系列新的最优化方理和方法应用到最优化领域，形成了一系列新的最优化方法，如法，如遗传算法、神经网络算法、蚁群算法遗传算法、神经网络算法、蚁群算法等。等。这些算法不需要构造精确的数学搜索方向，不需要进这些算法不需要构造精确的数学搜索方向，不需要进行繁杂的一维搜索，而是通过大量简单的信息传播和演变行繁杂的一维搜索，而是通过大量简单的信息
2、传播和演变方法，得到问题的最优解。方法，得到问题的最优解。遗传算法是模拟生物在自然环境中的遗传和进化过程而遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局最优化概率搜索算法。形成的一种自适应全局最优化概率搜索算法。7.1 遗传算法遗传算法7.1.1 生物的遗传与进化生物的遗传与进化 生物从其亲代继承特性或形状的现象称为遗传；生物从其亲代继承特性或形状的现象称为遗传；生物在其延续生存的过程中生物在其延续生存的过程中,逐渐适应生存环境，使其品逐渐适应生存环境，使其品质不断得到改良，这种生命现象称进化。质不断得到改良，这种生命现象称进化。构成生物的基本结构和功能单元是细胞构成生物
3、的基本结构和功能单元是细胞 细胞中含有一种微小的丝状化合物称染色体细胞中含有一种微小的丝状化合物称染色体 染色体主要由一种叫做核糖核酸染色体主要由一种叫做核糖核酸(简称简称DNA)的物质构成的物质构成 DNA按一定规则排列的长连称基因按一定规则排列的长连称基因 基因是遗传的基本单位基因是遗传的基本单位 另外，在进行细胞复制时，也可能产生某些差错，从而另外，在进行细胞复制时，也可能产生某些差错，从而使使DNA发生某种变异，产生新的染色体。发生某种变异，产生新的染色体。可见，同源染色体之间的复制、交叉或变异会使基因或可见，同源染色体之间的复制、交叉或变异会使基因或染色体发生各种各样的变化，从而，使
4、生物呈现新的性状，染色体发生各种各样的变化，从而，使生物呈现新的性状，产生新的物种。产生新的物种。细胞在分裂时，遗传物质细胞在分裂时，遗传物质DNA通过复制转移到新的细通过复制转移到新的细胞中，新细胞就继承了旧细胞的基因。胞中，新细胞就继承了旧细胞的基因。有性生殖生物在繁殖下一代时，两个同源染色体之间有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉而重组，即在两个染色体的某一相同位置处通过交叉而重组，即在两个染色体的某一相同位置处DNA被切断，然后分别交叉组合形成两个新的染色体。被切断，然后分别交叉组合形成两个新的染色体。7.1.2 基本遗传算法基本遗传算法X可以看作由可以看作由 n 个
5、遗传个遗传基因组成的染色体，也称基因组成的染色体，也称个体个体。最简单的等位基因由最简单的等位基因由0和和1这两个整数组成，相应的染色这两个整数组成，相应的染色体或个体就是体或个体就是一个二进制符号串一个二进制符号串。12,TnXxx Lx12nX:X,X LX 在遗传算法中，将设计变量在遗传算法中，将设计变量用符号串用符号串 表示。表示。由由 m 个个体组成一个个个体组成一个群体，记作群体，记作()P t 这种编码所形成的符号串称这种编码所形成的符号串称个体的基因型个体的基因型，与之对应的，与之对应的值称值称个体的表现型个体的表现型。把其中每一个把其中每一个 看作一个遗传基因，它的所有可能看
6、作一个遗传基因，它的所有可能的取值称的取值称等位基因等位基因。iX（1）遗传编码）遗传编码 遗传算法的运行不直接对设计变量本身进行操作，遗传算法的运行不直接对设计变量本身进行操作，而是对表示可行解的个体编码进行而是对表示可行解的个体编码进行选择选择、交叉交叉和和变异变异等遗传运算。等遗传运算。在遗传算法中把原问题的可行解转化为个体符在遗传算法中把原问题的可行解转化为个体符号串的方法称号串的方法称编码编码。现有的编码方法可以分为三类，它们是现有的编码方法可以分为三类，它们是二进制二进制编码、编码、浮点数编码浮点数编码和符号编码。和符号编码。二进制编码所用的符号集是由二进制编码所用的符号集是由 0
7、 和和 1 组成的二值符号集，组成的二值符号集，它所构成的个体基因型是一个它所构成的个体基因型是一个二进制符号串二进制符号串。符号串的长度与所要求的求解精度有关。符号串的长度与所要求的求解精度有关。minmax,UUl2l 假设某一参数的取值范围是假设某一参数的取值范围是，若用长度为，若用长度为的二进制符号串来表示，总共能够产生的二进制符号串来表示，总共能够产生 个编码。个编码。编码精度为编码精度为21maxminlUU（7-1）这里介绍常用的二进制编码方法。这里介绍常用的二进制编码方法。1221:lllXb bbb b假设某一个体的编码是假设某一个体的编码是：(7-2)11221maxmin
8、minliiliUUxUb则对应的解码公式为则对应的解码公式为(7-3)就表示一个个体，称就表示一个个体，称个体的基因型个体的基因型，对应的十进制，对应的十进制数数175就是个体的表现型，编码精度为0 1023,x例如，对于变量例如，对于变量10210240 0 1 0 1 0 1 1 1 1:X若采用若采用10位二进制编码时，可代表位二进制编码时，可代表个不同的个体。如个不同的个体。如 在研究生物的遗传和进化现象时，生物学家使用在研究生物的遗传和进化现象时，生物学家使用适应度适应度这个术语来度量物种对生存环境的适应程度。这个术语来度量物种对生存环境的适应程度。（2）个体适应度）个体适应度 在
9、遗传算法中使用适应度这个概念来度量群体中在遗传算法中使用适应度这个概念来度量群体中个体的优劣程度。适应度较高的个体遗传到下一代的个体的优劣程度。适应度较高的个体遗传到下一代的概率较大，反之则较小。概率较大，反之则较小。度量个体适应度的函数称度量个体适应度的函数称适应度函数适应度函数 ，一般，一般由由目标函数目标函数 或或惩罚函数惩罚函数 转换而来转换而来。()F X()f X(,)kX r 以目标函数为例，常用的转换关系如下：以目标函数为例，常用的转换关系如下：max()f X对于极大化问题对于极大化问题：000minminmin(),()(),()f XCiff XCF Xiff XC(7-
10、4)minC式中式中为为一适当小的正数适当小的正数。min()f X 对于极小化问题对于极小化问题：0maxmaxmax(),()(),()Cf Xiff XCF Xiff XC(7-5)maxC为一较大的正数较大的正数。式中，式中，生物的进化是以生物的进化是以集团集团为主体进行的。与此对应，为主体进行的。与此对应，遗传算法的运算对象也是由遗传算法的运算对象也是由M个个体所组成的集合，个个体所组成的集合，称称群体群体。第。第t 代群体记作代群体记作 P（t），），遗传算法的运算就遗传算法的运算就是群体的反复演变过程。是群体的反复演变过程。（3）遗传运算）遗传运算 遗传算法将染色体中基因的复制、
11、交叉和变异归遗传算法将染色体中基因的复制、交叉和变异归结为各自的结为各自的运算规则运算规则或或遗传算子遗传算子，并反复将这些遗传，并反复将这些遗传算子作用于算子作用于群体群体 P（t），），对其进行选择、交叉和变对其进行选择、交叉和变异运算，以求得到最优的个体，即问题的最优解。异运算，以求得到最优的个体，即问题的最优解。生物的进化过程主要是通过生物的进化过程主要是通过染色体染色体之间的之间的复制复制、交叉交叉和和变异变异来完成的。来完成的。1）选择运算）选择运算 遗传算法使用选择算子来对群体中的个体进行优遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作。适应度较高的个体有较大的概率遗传到胜
12、劣汰操作。适应度较高的个体有较大的概率遗传到下一代。下一代。11 2(,)MisiiiPffiM 设群体的大小为设群体的大小为M，个体，个体 i 的适应度为的适应度为fi，则个体，则个体 i 被选中的概率被选中的概率Pis为为：目前常用比例选择运算。其基本的操作是：目前常用比例选择运算。其基本的操作是：个体个体被选中并遗传到下一代的概率与它的适应度的大小成被选中并遗传到下一代的概率与它的适应度的大小成正比。正比。每个概率值组成一个区间，全部概率值之和为每个概率值组成一个区间，全部概率值之和为1。2）交叉运算）交叉运算 交配重组是生物遗传进化过程中的一个重要环交配重组是生物遗传进化过程中的一个重
13、要环节。模仿这一过程，节。模仿这一过程，遗传算法使用遗传算法使用交叉运算交叉运算，即在，即在两个相互配对的个体间按某种方式两个相互配对的个体间按某种方式交换其部分基因交换其部分基因，从而从而形成两个新生的个体形成两个新生的个体。运算前需对群体中的个体进行随机配对，然后运算前需对群体中的个体进行随机配对，然后以不同的方式确定配对个体交叉点的位置，并在这以不同的方式确定配对个体交叉点的位置，并在这些位置上进行部分基因的交换，形成不同的交叉运些位置上进行部分基因的交换，形成不同的交叉运算方法。目前最常用的是算方法。目前最常用的是单点交叉运算单点交叉运算。产生一个产生一个0到到1之间的随机数，依据概率
14、值所出现之间的随机数，依据概率值所出现的区间来决定对应的个体被选中的次数，此法亦称的区间来决定对应的个体被选中的次数，此法亦称轮轮盘法盘法。110000 0001000101 0011父个体父个体1父个体父个体2110001 0001000100 0011子个体子个体1子个体子个体2交叉运算交叉运算交叉点交叉点交叉点交叉点 单点交叉又称简单交叉，它是在个体编码串中单点交叉又称简单交叉，它是在个体编码串中随机地设置一个交叉点，并在该交叉点上相互交换随机地设置一个交叉点，并在该交叉点上相互交换两个配对个体的基因，如下所示：两个配对个体的基因，如下所示：3）变异运算）变异运算 生物的遗传和进化过程中
15、，在细胞的分裂和复制生物的遗传和进化过程中，在细胞的分裂和复制环节上可能产生一些差错，从而导致生物的某些基因环节上可能产生一些差错，从而导致生物的某些基因发生某种变异，产生出新的染色体，表现出新的生物发生某种变异，产生出新的染色体，表现出新的生物性状。性状。模仿这一过程，遗传算法采用模仿这一过程，遗传算法采用变异运算变异运算，将个，将个体编码串中的某些基因座上的基因值用它的不同等体编码串中的某些基因座上的基因值用它的不同等位基因来替换，从而产生新的个体。位基因来替换，从而产生新的个体。有很多变异运算方法，最简单的是有很多变异运算方法，最简单的是基本位变异基本位变异。基本位变异操作是在个体编码串
16、中依变异概率基本位变异操作是在个体编码串中依变异概率Ps随随机指定某一位或某几位基因座上的基因值作变异运机指定某一位或某几位基因座上的基因值作变异运算，算，如下所示：如下所示：11000100011100011001变异运算变异运算编码，构成初始群体P(t)计算P(t)中各个体的适应度图图7-1 遗传算法的运算流程图遗传算法的运算流程图给定T、置t=0t=t+1得到新的群体 p(t+1)变异运算交叉运算选择运算 Y取最大适应度的个体解码输出终止tT遗传算法的运算流程图如下遗传算法的运算流程图如下：N2212max()f Xxx例例 用用遗传算法遗传算法求如下函数的全局最大值求如下函数的全局最大
17、值 s.t.xi 1,2,7 (i=1,2)由此开始的遗传算法求解过程如表所示。由此开始的遗传算法求解过程如表所示。解，由于变量的取值上限为解，由于变量的取值上限为7下限为下限为0，故对，故对1x2x和和均采用均采用3位二进制编码位二进制编码。0.230.210.420.14(16)53509834适应度适应度 f(xf(x1 1,x,x2 2)(15)7,27,17,73,5变量变量 x x1 1,x,x2 2(14)子代群体子代群体 P P（1 1）(13)111010111001111111011101变异结果(12)6254变异点变异点(11)111011101001111101011
18、001交叉结果交叉结果(10)54交叉点交叉点 (9)3-41-2配对情况配对情况 (8)111001101011111001011101选择结果选择结果 (7)2011选择次数选择次数 (6)0.350.170.240.24 (5)50253434适应度适应度 f(xf(x1 1,x,x2 2)(4)7,13,45,33,5变量变量 x x1 1,x,x2 2(3)111001011100101011011101初始群体初始群体 P(0)P(0)(2)4321个体编号个体编号 i i (1)/iiff/iiff 需要说明的是，需要说明的是，表中第表中第、12 12 栏栏的数据是应该随机产生的
19、的数据是应该随机产生的，这里特意选择了一些较好，这里特意选择了一些较好的数据以便尽快得到较好的结果。的数据以便尽快得到较好的结果。实际运算中一般需求经过多次进化才能得到这样实际运算中一般需求经过多次进化才能得到这样的最优结果。的最优结果。从表中可以看出，群体经过一代进化后，其适应从表中可以看出，群体经过一代进化后，其适应度的最大值和平均值都得到了明显的改进。实际上已度的最大值和平均值都得到了明显的改进。实际上已经找到了最佳的个体经找到了最佳的个体“111111”以及对应的最优解：以及对应的最优解：X 7,7 T,f(X)=987.2 神经网络算法神经网络算法7.2.1 人工神经元与神经网络人工
20、神经元与神经网络 人的大脑中有人的大脑中有100多亿个神经细胞。一个神经细胞主要由多亿个神经细胞。一个神经细胞主要由细胞体细胞体、树突树突、轴突轴突和和突触突触组成。组成。树突树突伸向四方，其作用是收集四周神经细胞的信息。伸向四方，其作用是收集四周神经细胞的信息。突触突触是两个神经细胞之间起连接作用的部分。树突将收集是两个神经细胞之间起连接作用的部分。树突将收集到的信息经过到的信息经过轴突轴突输出，传给其他细胞。输出，传给其他细胞。突触有突触有兴奋性兴奋性和和抑止性抑止性两种状态。兴奋性突触在脉冲的刺两种状态。兴奋性突触在脉冲的刺激下能使下一个神经细胞产生兴奋性激下能使下一个神经细胞产生兴奋性
21、膜电位膜电位，很多细胞通过各，很多细胞通过各自的突触对某一个神经细胞发生作用，使其膜电位发生变化，自的突触对某一个神经细胞发生作用，使其膜电位发生变化，当膜电位的累加值超过某一当膜电位的累加值超过某一阈值阈值时，就会使该细胞产生一个新时，就会使该细胞产生一个新的的脉冲脉冲。一个神经细胞周围大约有一个神经细胞周围大约有1001000个其他细胞，神经细胞个其他细胞，神经细胞的信息就是这样从一个细胞传递给另外一个细胞的，从一个的信息就是这样从一个细胞传递给另外一个细胞的，从一个神经网络传到另一个神经网络。神经网络传到另一个神经网络。1943年，美国心理学家年，美国心理学家 W.McCllochhe
22、和数学家和数学家 W.pitts根根据生物神经元的基本特性，提出据生物神经元的基本特性，提出MP神经元模型神经元模型，开创了人工，开创了人工神经元研究的新纪元。神经元研究的新纪元。MP神经元模型如图所示神经元模型如图所示 图图7-2 MP神经元模型神经元模型wj1x2xnwj2wjnjf()ujyjx1 图图7-3 MP模型的激活函数模型的激活函数ujff(uj)1其符号的其符号的正负正负表示产生的作用是表示产生的作用是兴兴奋性奋性的或的或抑止性抑止性的，其数值的的，其数值的大小大小表达作用的表达作用的强弱强弱；j j表示神经元表示神经元的阈值（触发值）的阈值（触发值）ju代表神经元代表神经元
23、的总输入的总输入，jjy表示神经元表示神经元的状态或输出的状态或输出。j 图图7-2 MP神经元模型神经元模型wj1x2xnwj2wjnjf()ujyjx1其中其中个神经元对第个神经元对第 个个jiwij表示第表示第神经元的作用神经元的作用权值权值，1()njjiijijjuw xyf u 于是一个神经元在某时刻的状态或输出可用下面的数学于是一个神经元在某时刻的状态或输出可用下面的数学表达式加以描述表达式加以描述（7-7）()f其中其中称激活函数。称激活函数。1000,sgn(),jjjjuyuu (7-8)时，神经元的状态是总输入时，神经元的状态是总输入ju的双值函数的双值函数。当激活函数取
24、如图当激活函数取如图7-3所示的所示的符号函数符号函数ju0jy 当当小于零时小于零时，表示神经元表示神经元未被触发未被触发，保持保持原来的状态不变原来的状态不变。这与生物神经细胞对信息的反应和传递是一致的，因此这与生物神经细胞对信息的反应和传递是一致的，因此它也成为人工神经元及其所构成的神经网络最基本的数学描它也成为人工神经元及其所构成的神经网络最基本的数学描述。述。除除符号函数符号函数之外，常用的激活函数还有如图之外，常用的激活函数还有如图7-4所示的所示的线性函数线性函数和和 S 型函数型函数等。等。ju1jy 当当大于零时大于零时，表示神经元表示神经元被触发被触发产生产生一个新的一个新
25、的脉冲脉冲。11,(),jajjjajajauuyf uuuuuuu（a）线性函数）线性函数0 ua1-ua-1yjuj图图7-4 激活函数激活函数(b)S型函数型函数11()jjjuyf ue 01-1yjuj 目前提出的人工神经网络模型已有目前提出的人工神经网络模型已有40 多种多种按按网络结构网络结构分为分为前馈型前馈型和和反馈型反馈型；按按网络性能网络性能分为分为连续型连续型、离散型离散型、确定型确定型和和随机型随机型；按按学习方式学习方式分为分为有导师型有导师型和和无导师型无导师型；按按突触连接性质突触连接性质分为分为一阶线性型一阶线性型和和高阶非线性型高阶非线性型等。等。人工神经网
26、络是将上述人工神经元以某种方式组合起来人工神经网络是将上述人工神经元以某种方式组合起来的网络结构。的网络结构。人工神经网络通过某种学习（训练）方法模拟生物体中神人工神经网络通过某种学习（训练）方法模拟生物体中神经网络的某些结构与功能，从而用以解决不同的工程实际问题。经网络的某些结构与功能，从而用以解决不同的工程实际问题。目前目前常用的常用的 BP 网络和网络和 RBF 网络属网络属前馈型前馈型神经网络，神经网络，Hopfield 网络网络属属反馈型反馈型网络。网络。BP网络由多个输入结点、多个隐含层和一个输出层组网络由多个输入结点、多个隐含层和一个输出层组成。每层包含多个神经元（结点）。前后层
27、之间实现全连接成。每层包含多个神经元（结点）。前后层之间实现全连接，层内各结点之间无连接。，层内各结点之间无连接。7.2.2 BP网络网络 BP网络是一种输入信号前向传播、误差信号反向传播的网络是一种输入信号前向传播、误差信号反向传播的多层前馈型网络多层前馈型网络。（1）BP网络结构网络结构 BP网络中，隐含层神经元的激活函数一般采用网络中，隐含层神经元的激活函数一般采用Sigmoid型型的对数函数或正切函数，输出层神经元通常采用线性激活函的对数函数或正切函数，输出层神经元通常采用线性激活函数。数。图图7-5所示为单隐层所示为单隐层BP网络的结。网络的结。(a)结构图隐层（n个神经元）输出层（
28、m个神经元）x1x2x3xn1w 111w1n,n1w1n,3u1unu2v1v2vnh1h2hny1y2yn1f2f1112 1n21212nw 112w2m,nw211图图7-5 单隐层单隐层BP网络网络输输 入入W1W2隐隐 含含 层层输输 出出 层层 线性激活函数线性激活函数S型激活函数型激活函数(b)结构简图结构简图12Xn11n1n1u1f2fyvhm1mnn1nn1m1(c)网络结构示意图网络结构示意图 XW1JHLYW2网络中隐含层和输出层神经元的输出为网络中隐含层和输出层神经元的输出为1111122211 21 2,njjiijinll jjljhfw xjnyfw hlm
29、(7-9)若将神经元的阈值也视为一个连接权值，即令若将神经元的阈值也视为一个连接权值，即令112200001,jjllwwxh 则上式可写成如下形式则上式可写成如下形式1111022201 21 2(),(),njjjiiinlll jjjhf ufw xjnyf vfw hlm （7-10）（2）BP学习算法学习算法 BP网络的学习训练过程分为网络的学习训练过程分为两个阶段两个阶段。第一阶段。第一阶段正向正向传播传播。若在输出层得不到希望的结果，则转入第二阶段。若在输出层得不到希望的结果，则转入第二阶段反向反向传播传播，将误差信号沿原来的神经元连接通路返回，通过修改，将误差信号沿原来的神经元
30、连接通路返回，通过修改各层神经元的权值，使得误差信号不断减小，最后达到误差各层神经元的权值，使得误差信号不断减小，最后达到误差允许的范围。允许的范围。12,NXXX设共有设共有 N N 个个学习样本学习样本：12,Nd dd对应的对应的输出期望值输出期望值为：为：1 2(,)plylm 若给定网络的所有连接权值的初始值。将第若给定网络的所有连接权值的初始值。将第P P个样本个样本输入后，输入后，网络的输出网络的输出是是 将将N个样本全部输入，并按式（个样本全部输入，并按式（7-9）作正向传递运算后，）作正向传递运算后，网络的总误差网络的总误差为为211112()NNmpppllpplEEdy（
31、7-13）若此误差值大于给定的精度若此误差值大于给定的精度，则要设法改变网络的各个，则要设法改变网络的各个连接权值，以使网络误差减小，并最终满足给定的精度要求。连接权值，以使网络误差减小，并最终满足给定的精度要求。取误差函数的负梯度作为误差函数的调整方向，对于任取误差函数的负梯度作为误差函数的调整方向，对于任意权系数意权系数uvw，权值的调整量和新的权值分别为权值的调整量和新的权值分别为11()()()()uvuvuvNpuvpuvwnwnwnEwnw 2112()mppplllEdy(7-12)与期望值相比与期望值相比输出误差输出误差为为 其中其中n代表修正或调整的次数代表修正或调整的次数。
32、这就是。这就是BP网络学习训练网络学习训练的基本思想，由此得到的算法称的基本思想，由此得到的算法称BP算法算法。（3）BP 算法的计算公式算法的计算公式 对输出层的对输出层的权值权值2ljw2221121()()ljljlppNNppllppppljllNpppplljpEEyvwwyvwdyfvh （716）22()()pppplllldyfv 令令 （718）221ljNPpljpwh （717）和权值的修正算式和权值的修正算式 得得222111 21 2()(),(,;,)ljNPpljljpwnwnhjn lm（718）2pl pplldy0.011.0其中其中称称等效误差等效误差，为
33、为实际误差实际误差，为为学习速率学习速率，通常取通常取同理，对于同理，对于隐含层权值隐含层权值1jiw有有1111122110()()()jijijppppNNppjjllpppppplljjjiNmpppppllll jiplEEhuyvwwyvhuwdyfvwfux 令等效误差令等效误差21121()ljmpppjjllfuw 多个隐含层多个隐含层BP网络中，其他隐含层的权值修正式可按同网络中，其他隐含层的权值修正式可按同样方法推出。样方法推出。综上所述，综上所述，BP算法的执行步骤如下：算法的执行步骤如下：隐含层的权值调整量和权值的修正算式分别为隐含层的权值调整量和权值的修正算式分别为（
34、720）111jiNppjipwx111111 211 2()(),(,;,)jijiNppjipwnwnxinjm10()w、20()w10()、20()给定给定初始权值矩阵初始权值矩阵和和阈值向量阈值向量为为小的随机数向量小的随机数向量，给定给定计算精度计算精度；pX1 2(,)pdpN 输入输入训练样本训练样本和和期望输出期望输出；对各个样本，按式（对各个样本，按式（79）或式（）或式（710）计算网络隐含层）计算网络隐含层 的状态和输出层的输出；的状态和输出层的输出；(1,2,;1,2,)pplldypNlm成立，则网络的学习完成。否则转；成立，则网络的学习完成。否则转；精度判断：若有
35、精度判断：若有按式按式(7-17)和式（和式（7-19）计算输出层和隐含层的等效误差、并）计算输出层和隐含层的等效误差、并按式（按式（7-18）和式（）和式（7-20）对所有权值进行修正后转。）对所有权值进行修正后转。综上所述，综上所述，BP算法算法是以梯度法寻求误差函数极小化的迭代算法。是以梯度法寻求误差函数极小化的迭代算法。训练依据是给定的某一过程若干组数据构成的试验样本训练依据是给定的某一过程若干组数据构成的试验样本(x,d)训练结果是一组符合该过程运行规律的网络权值训练结果是一组符合该过程运行规律的网络权值W和阈值。和阈值。有了这一组权值和阈值，就可以方便地模拟和仿真该过程，有了这一组
36、权值和阈值，就可以方便地模拟和仿真该过程，得到任意一组给定数据所对应的预测结果。得到任意一组给定数据所对应的预测结果。Hopfield人工神经网络是一种人工神经网络是一种单层对称全反馈式网络单层对称全反馈式网络，7.2.3 Hopfield网络网络 Hopfield网络网络根据激活函数的不同根据激活函数的不同分分离散型网络离散型网络和和连续型网络连续型网络两种。两种。离散型离散型Hopfield网络是一种反馈型单层二值神经元网络，网络是一种反馈型单层二值神经元网络，图图7-9 所示为所示为n个神经元组成的个神经元组成的Hopfield网络。网络。图图7-9 Hopfield 网络网络y1(t+
37、1)y2(t+1)yn(t+1)v1(t+1)v2(t+1)vn(t+1)f（）f（）f（）u1(t)u2(t)un(t)x1x2xnwn1w21w1nw2n-2-nwn21110100,()(),()njiijijnjiijiw v tv tw v t 每个神经元结点的每个神经元结点的输出为输出为 0 或或 1。类似于。类似于 MP 神经元，神经元，可表示为可表示为（724）0iiw 若进一步令若进一步令 则这时的权矩阵是一个则这时的权矩阵是一个主对角线元素全部为零的对称矩主对角线元素全部为零的对称矩阵阵。对应的网络是一种。对应的网络是一种无自反馈的对称型无自反馈的对称型Hopfield网络
38、。网络。ijjiww其中其中，即即网络是对称的网络是对称的。为外界输入时的网络状态称网络的初始状态，记作为外界输入时的网络状态称网络的初始状态，记作111 2()()()()sgn(),(,)njjiijijjjutw vtvtf ututjn X01 2()(,)iivxin 为外界输入时的网络状态称网络的初始状态，记作为外界输入时的网络状态称网络的初始状态，记作 以以 其结构可以用一个加权无向量图表示，如图其结构可以用一个加权无向量图表示，如图7-10和图和图7-11所示。所示。图图7-10 Hopfield网络网络 结结 构简图构简图图图7-11 Hopfield网络网络 等价结构图等价
39、结构图y1y2y3w21w12w13w23w32w31w31y1y2y3w12w13w23式中式中 sgn。为符号函数，即为符号函数，即1011 200()()sgn(),(,)()jjjju tv tu tjnu t网络运行的方式有网络运行的方式有异步异步和和同步同步两种：两种：异步（串行）方式。在任意时刻异步（串行）方式。在任意时刻t，随机或按某一确定的顺，随机或按某一确定的顺序对网络的某一神经元的状态进行演变更新，其余神经元的序对网络的某一神经元的状态进行演变更新，其余神经元的状态保持不变。状态保持不变。同步（并行）方式。在任意时刻同步（并行）方式。在任意时刻t，网络中的部分神经元，网络
40、中的部分神经元（如同一层）的状态同时演变更新，或网络中的全部神经元（如同一层）的状态同时演变更新，或网络中的全部神经元的状态同时进行演变更新。的状态同时进行演变更新。Hopfield离散型网络在某一时刻离散型网络在某一时刻t的能量函数定义为的能量函数定义为11112,()()()()nnnjiijjjjiijjE tw v t vtvt 可以证明，如果网络的权值矩阵是可以证明，如果网络的权值矩阵是对称的且无自反馈对称的且无自反馈，若按异步（串行）方式更新时网络是稳定的，必定会收敛若按异步（串行）方式更新时网络是稳定的，必定会收敛于一个稳定状态。也就是说，在网络的于一个稳定状态。也就是说，在网络
41、的循环演变过程循环演变过程中，中，能量能量函数函数是是单调下降单调下降的。当网络最终趋于稳定状态时，能量函数达的。当网络最终趋于稳定状态时，能量函数达到最小值。到最小值。网络演变中，能量函数的变化可表示为网络演变中，能量函数的变化可表示为1()()()njiijijE twvtvt 1()()()njiijjiE tw v tv t 或或11110100,()()sgn(),()njiijnijjiijnijiijiw v tvtw v tw v t 分析可知，若取激活函数为符号函数，即令分析可知，若取激活函数为符号函数，即令可保证网络在演变过程中，能量函数单调下降，最后达到极小值可保证网络在
42、演变过程中，能量函数单调下降，最后达到极小值 连续型连续型Hopfield网络的结构与离散型相同，状态方程也相网络的结构与离散型相同，状态方程也相同，不同的是激和函数为连续可微、单调上升的同，不同的是激和函数为连续可微、单调上升的S型函数，即型函数，即11 11 2()/(),(,)jnjjiijiujjuwxvf uejn Hopfield网络用来求解最优化问题的基本步骤可概括如下：网络用来求解最优化问题的基本步骤可概括如下：选择合适的问题表达，使网络输出与最优化问题的解彼此对应；选择合适的问题表达，使网络输出与最优化问题的解彼此对应；构造计算能量函数，使其最小值对应问题的最优值；构造计算能
43、量函数，使其最小值对应问题的最优值；由能量函数和解的表达形式推出对应的连接权矩阵和阈值向量；由能量函数和解的表达形式推出对应的连接权矩阵和阈值向量；构造相应的神经网络；构造相应的神经网络；进行网络演变运算，直到网络达到稳定状态，得到最优解为止。进行网络演变运算，直到网络达到稳定状态，得到最优解为止。在用在用Hopfield 网络求解最优化问题时，关键在于针对网络求解最优化问题时，关键在于针对不同不同的问题的问题构造相应的构造相应的能量函数能量函数和和网络结构网络结构。为此首先需要把目标函数和约束条件与网络的能量函数联为此首先需要把目标函数和约束条件与网络的能量函数联系起来，即令网络的能量函数等
44、于最优化问题的系起来，即令网络的能量函数等于最优化问题的目标函数目标函数或或惩惩罚函数罚函数11112()nnnjiijjjjijijf XEw x xx 11112()nnnjiijjjjijijXEw x xx（728）（729）或 从而确定网络的从而确定网络的结构结构和结构和结构参数参数（权值（权值和阈值）。和阈值）。然后按然后按异步异步方式，不断对网络进行方式，不断对网络进行更新更新，当网络达到，当网络达到稳定稳定状态时，便可得到最优化问题的状态时，便可得到最优化问题的最优解最优解。对于无约束的二次函数最优化问题对于无约束的二次函数最优化问题12min()TTf XX HXX B 显然
45、，若将显然，若将二阶导数矩阵二阶导数矩阵H当作当作权矩阵权矩阵，将，将梯度梯度当作当作阈值向量阈值向量则有则有12()()TTE Xf XX WXX 对于线性规划问题对于线性规划问题12300min().,Tf XC Xs tAXBx xx建立相应的外点惩罚函数建立相应的外点惩罚函数(,)TTX rC Xr AXBAXB 若取若取 22TTWrA ACrA B 可见以能量函数（可见以能量函数（732）建立神经网络并运算求解，当）建立神经网络并运算求解，当能量函数达到极小时惩罚函数也达到极小，对应的解就是线能量函数达到极小时惩罚函数也达到极小，对应的解就是线性规划问题的最优解性规划问题的最优解。
46、可以验证当能量函数取作可以验证当能量函数取作1222()()()TTTTE XXrA A XXCrA B时，惩罚函数时，惩罚函数与能量函数的值仅相差一个常数。与能量函数的值仅相差一个常数。（732）()(,)E XX rc 即即 将式上式代入式（将式上式代入式（7-30）后）后12()TTTTE VV T HTVV T B 得得 当网络的能量函数确定以后，变量当网络的能量函数确定以后，变量X还需用神经元的状态还需用神经元的状态向量向量V表示，设它们之间的转换矩阵为表示，设它们之间的转换矩阵为T，XTV即令令 TTWT HTT B 则有则有 12()TTE VV WVV 这就是用神经网络算法求解
47、二次函数最优化问题时的能量函数。这就是用神经网络算法求解二次函数最优化问题时的能量函数。对应的神经元状态演变关系为对应的神经元状态演变关系为1()()()sgn()U tWV tV tU t 或或 111 2()sgn(),(,)njjiijijjv tw v tjn 例例74 求解无约束最优化问题求解无约束最优化问题121323132353min()f Xx xx xx xxx 解解 首先将目标函数带入式（首先将目标函数带入式（728），比较可知对应的神经网），比较可知对应的神经网络为三结点络为三结点Hopfield网络，网络参数为：网络，网络参数为：12211331233211223312
48、30,wwwwwwwww 123503,即即 012510302303,W 按式按式()()U tWV t 1()sgn()V tU t 和和 对网络进行更新，取对网络进行更新，取 00011()TVX因因 0120580103103230136()U 有有 11000()sgn()VU 同理有同理有151121 10(),()TTUV261431 10(),()TTUV 可见，网络到此已达到稳定状态，故所求无约束问题的可见，网络到此已达到稳定状态，故所求无约束问题的最优解是最优解是1 106,()Xf X 例例7-5 求解无约束最优化问题求解无约束最优化问题2212121222min()f
49、Xxxx xx给定初始点给定初始点0 3,TX 解解：采用离散型采用离散型Hopfield 网络，将变量用二位二进制数表示网络，将变量用二位二进制数表示20100201XTVT即令即令02100000021131 X00(0)11V 取目标函数为计算能量函数取目标函数为计算能量函数，即，即22121211112222222212022412,()TTExxx xxxxxxxxXH XB X XTX 将上面用二进制数表示的将上面用二进制数表示的 和和 代入上式代入上式由于由于Hopfield网络中存在关系网络中存在关系0iiw，故权矩阵和阈值向量是故权矩阵和阈值向量是04844042840842
50、80W20410220200010TB 对应的网络如图对应的网络如图7-12，其中，其中n=4，即有，即有4个神经元。个神经元。图图7-12 例例7-4 的网络结构图的网络结构图 2(0)v4(0)v3(0)v1(0)v4(1)v t3(1)v t2(1)v t1(1)v t32121w43w34w42w41w41234 演变求解演变求解采用串行运行方式，初始点采用串行运行方式，初始点对应的网路初始状态是对应的网路初始状态是0001 1()TV18f 0484041640420280084081084280108()()UWV 分别单独改变第分别单独改变第1到第到第4个神经元的状态，得如下状态
