人工神经网络第七章

1、第7章 循环网络主要内容Hopfield网络实现的自相联存储稳定性分析统计Hopfield网与Boltzmann机根本双联存储器(BAM)的结构与训练几种相联存储网络用Hopfield网解决TSP问题。9/4/20221第一页，共七十三页。第7章 循环网络重点Hopfield网络实现的自相联存储根本双联存储器的结构与训练。难点稳定性分析用Hopfield网解决TSP问题 9/4/20222第二页，共七十三页。第7章 循环网络7.1 循环网络的组织 7.2 稳定性分析 7.3 统计Hopfield网与Boltzmann机 7.4 双联存储器的结构 7.5 异相联存储 7.6 其它的双联存储器 7

2、.7 Hopfield网用于解决TSP问题 9/4/20223第三页，共七十三页。第7章 循环网络 循环网络称为Hopfield网 循环网络对输入信号的处理是一个逐渐“修复、“加强的过程。强烈变化较弱的变化不变化9/4/20224第四页，共七十三页。7.1 循环网络的组织 网络结构X1Xno1om9/4/20225第五页，共七十三页。7.1 循环网络的组织 联接：神经元之间都是互联的wij，每个神经元都没有到自身的联接wii=0。神经元个数h，输入向量维数n，输出向量维数m。hn，hm，n1，m1。神经元：输入、输出、隐藏状态变化：非同步、同步输入向量：X=(x1，x2，xn) 输出向量：O=

3、(o1，o2，om) 9/4/20226第六页，共七十三页。7.1 循环网络的组织神经元的网络输入： 阈值函数：oj=1if netjj0if netj0，ok=1& ok=0，ok由0变到1，netkk，netk-k0所以，-(netk-k)ok0故0结论：网络的目标函数总是下降ok0, ok=0& ok=1，ok由1变到0netkk，netk-k0-(netk-k)ok0故r 那么使ANi的状态为1， 否那么使ANi的状态为0；3 逐渐降低温度T，如果温度足够低，那么算法结束。否那么，重复2 9/4/202240第四十页，共七十三页。Boltzmann机的训练 Boltzmann机是多级循

4、环网络，是Hopfield网的一种扩展。神经元ANi实际输出状态oi=1的概率为： T趋近于0时，神经元的状态不再具有随机性，Boltzmann机退化成一般Hopfield网。 9/4/202241第四十一页，共七十三页。Boltzmann机的训练 9/4/202242第四十二页，共七十三页。Boltzmann机的训练 9/4/202243第四十三页，共七十三页。Boltzmann机的训练 Boltzmann机是多级循环网络，是Hopfield网的一种扩展。神经元ANi网络输入为： T趋近于0时，神经元的状态不再具有随机性，Boltzmann机退化成一般Hopfield网。 9/4/20224

5、4第四十四页，共七十三页。Boltzmann机的训练 神经元ANi实际输出状态oi=1的概率为神经元ANi实际输出状态oi=0的概率为显然 越大，那么 oi 取1的概率越大9/4/202245第四十五页，共七十三页。Boltzmann机的训练神经元ANi在运行中状态发生了变化 Boltzmann机的能量函数(一致性函数 )9/4/202246第四十六页，共七十三页。Boltzmann机的训练如果i0，神经元ANi处于状态1的概率就应该越大，否那么，神经元ANi处于状态0的概就应该越大。i的值越大，神经元ANi应该处于状态1的概率就应该越大。反之，i的值越小，神经元ANi应该处于状态1的概率就应

6、该越小。从而，oi=1的概率为： 9/4/202247第四十七页，共七十三页。Boltzmann机的训练处于状态a，b的概率Pa和Pb，对应于oi=1和oi=0，其它的神经元在a，b状态下不变 Pa=pi Pb =1-pi 当系统的温度较低时，如果EaPb：网络处于较低能量状态的概率较大 9/4/202248第四十八页，共七十三页。Boltzmann机的训练网络进行足够屡次迭代后，处于某状态的概率与此状态下的能量和此时系统的温度有关。由于高温时网络的各个状态出现的概率根本相同，这就给它逃离局部极小点提供了时机。9/4/202249第四十九页，共七十三页。Boltzmann机的训练1986年，H

7、inton和Sejnowski训练方法自由概率Pij-：没有输入时ANi和ANj同时处于激发状态的概率。约束概率Pij+：加上输入后ANi和ANj同时处于激发状态的概率。联接权修改量：wij=( Pij+ - Pij-) 9/4/202250第五十页，共七十三页。算法7-2 Boltzmann机训练算法 1计算约束概率 1.1 对样本集中每个样本，执行如下操作： 1.1.1 将样本加在网络上输入向量及其对应的输出向量； 1.1.2 让网络寻找平衡； 1.1.3 记录下所有神经元的状态； 1.2 计算对所有的样本，ANi和ANj的状态同时为1的概率Pij+；9/4/202251第五十一页，共七十

8、三页。算法7-2 Boltzmann机训练算法 2 计算自由概率 2.1 从一个随机状态开始，不加输入、输出，让网络自由运行，并且在运行过程中屡次纪录网络的状态； 2.2 对所有的ANi和ANj，计算它们的状态同时为1的概率Pij-； 3 对权矩阵进行调整wij=(Pij+-Pij-)9/4/202252第五十二页，共七十三页。7.7 Hopfield网解决TSP问题1985年，J. J. Hopfield和D. W. Tank用循环网求解TSP。试验说明，当城市的个数不超过30时，多可以给出最优解的近似解。而当城市的个数超过30时，最终的结果就不太理想了 设问题中含有n个城市,用n*n个神经

9、元构成网络 9/4/202253第五十三页，共七十三页。应用CHNN网解决优化计算问题 用CHNN网解决优化问题一般需要以下几个步骤： (1)对于特定的问题，要选择一种适宜的表示方法，使得神经网络的输出与问题的解相对应； (2)构造网络能量函数，使其最小值对应于问题的最佳答案解； (3)将能量函数与Lyapunov函数标准形式进行比较，可推出神经网络的权值与偏流的表达式，从而确定了网络的结构； (4)由网络结构建立网络的电子线路并运行，其稳态就是在一定条件下的问题优化解。也可以编程模拟网络的运行方式，在计算机上实现。 9/4/202254第五十四页，共七十三页。 TSP问题是一个经典的人工智能

10、难题。对n个城市而言，可能的路径总数为n!2n。随着n的增加，路径数将按指数率急剧增长，即所谓“指数爆炸。当n值较大时，用传统的数字计算机也无法在有限时间内寻得答案。例如，n50时，即使用每秒1亿次运算速度的巨型计算机按穷举搜索法，也需要51048年时间。即使是n20个城市，也需求解350年。 1985年Hopfield和Tank两人用CHNN网络为解决TSP难题开辟了一条崭新的途径，获得了巨大的成功。9/4/202255第五十五页，共七十三页。 其根本思想是把TSP问题映射到CHNN网络中去，并设法用网络能量代表路径总长。这样，当网络的能量随着模拟电子线路状态的变迁，最终收敛于极小值(或最小

11、值)时，问题的较佳解(或最佳答案解)便随之求得。此外，由于模拟电子线路中的全部元件都是并行工作的，所以求解时间与城市数的多少无关，仅是运算放大器工作所需的微秒级时间，显著地提高了求解速度，充分展示了神经网络的巨大优越性。9/4/202256第五十六页，共七十三页。1TSP问题描述 为使CHNN网络完成优化计算，必须找到一种适宜的表示旅行路线的方法。鉴于TSP的解是n个城市的有序排列，因此可用一个由nn个神经元构成的矩阵(称为换位阵)来描述旅行路线。图7.5给出8城市TSP问题中的一条可能的有效路线的换位阵。9/4/202257第五十七页，共七十三页。 TSP问题描述 为使CHNN网络完成优化计

12、算，必须找到一种适宜的表示旅行路线的方法。鉴于TSP的解是n个城市的有序排列，因此可用一个由nn个神经元构成的矩阵(称为换位阵)来描述旅行路线。图给出8城市TSP问题中的一条可能的有效路线的换位阵。9/4/202258第五十八页，共七十三页。 由于每个城市仅能访问一次，因此换位阵中每城市行只允许且必须有一个1，其余元素均为0。为了用神经元的状态表示某城市在某一有效路线中的位置，采用双下标 Yxi，第一个下标x表示城市名，1，2，n；第二个下标i表示该城市在访问路线中的位置，i1，2，n。例如，Y461表示旅途中第6站应访问城市4；假设Y460那么表示第6 站访问的不是城市4，而是其他某个城市。

13、 图78中的换位阵所表示的旅行路线为: 425813764，旅行路线总长为d42+d25+d58+d81+d13+d37+d76+d64。9/4/202259第五十九页，共七十三页。7.7 Hopfield网解决TSP问题dxy城市X与城市Y之间的距离；vxi城市X的第i个神经元的状态： 1城市X在第i个被访问vxi= 0城市X不在第i个被访问wxi,yj城市X的第i个神经元到城市Y的第j个神经元的连接权。 9/4/202260第六十页，共七十三页。7.7 Hopfield网用于解决TSP问题例如：四个城市X、Y、Z、W城市名访问顺序标示1234X0100Y0001Z1000W00109/4/

14、202261第六十一页，共七十三页。能量函数设计 用CHNN求解TSP问题的关键是构造一个适宜的能量函数。TSP问题的能量函数由4局部组成： (1)能量E1城市行约束 当每个城市行中的1不多于一个时，应有第x行的全部元素vxi按顺序两两相乘之和为0，即 从而全部n行的所有元素按顺序两两相乘之和也应为零，即=0 9/4/202262第六十二页，共七十三页。 按此约束可定义能量E1为 式中A为正常数。显然，当E10时可保证对每个城市访问的次数不超过一次。 (2)能量E2位置列约束 同理，当每个位置列中的1不多于一个时，应有第i列的全部元素vxi按顺序两两相乘之和为0，即 因此，全部n列的所有元素按

15、顺序两两相乘之和也应为零，即=09/4/202263第六十三页，共七十三页。 按此约束可定义能量E2为 式中B为正常数。显然，当E20时就能确保每次访问的城市数不超过一个。 (3)能量E3换位阵全局约束 E10和E20只是换位阵有效的必要条件，但不是充分条件。容易看出，当换位阵中各元素均为“0时，也能满足El0和E20，但这显然是无效的。因此，还需引入第三个约束条件全局约束条件，以确保换位阵中1的数目等于城市数n，即9/4/202264第六十四页，共七十三页。 因此定义能量E 为 式中C为正常数。那么E30可保证换位阵中1的数目正好等于n。 9/4/202265第六十五页，共七十三页。 (4)

16、能量E4旅行路线长度 同时满足以上3个约束条件只能说明路线是有效的，但不一定是最优的。依题意，在路线有效的前提下，其总长度应最短。为此在能量函数中尚须引入一个能反映路线总长度的分量E4，其定义式要能保证E4随路线总长度的缩短而减小。为设计E4，设任意两城市x与y间的距离为dxy 。访问这两个城市有两种途径，从x到y，相应的表达式为 dxy(vxi ,vy,i+1)；从y到x，那么相应的表达式为dyx(vxi ,vy,i1) 。如果城市x和y在旅行顺序中相邻，那么当 (vxi ,vy,i+1) 1时，必有 (vxi ,vy,i1) 0；反之亦然。因此，有dxy(vxi,vy,i1) (vxi,v

17、y,i1dxy。假设定义n个城市各种可能的旅行路线长度为9/4/202266第六十六页，共七十三页。 式中D为正常数，当E4最小时旅行路线最短。 综合以上4项能量，可得TSP问题的能量函数如下：(6.30)9/4/202267第六十七页，共七十三页。网络的能量函数9/4/202268第六十八页，共七十三页。7.7 Hopfield网用于解决TSP问题 联接矩阵 wxi,yj= -Axy(1-ij) Bij(1-xy) C dxy(ji+1+ji-1) 1如果i=jij= 0如果ij 9/4/202269第六十九页，共七十三页。 图给出用CHNN网解决10城市TSP问题的结果。图 (a)为最优解，图 (b)为较佳解。9/4/202270第七十页，共七十三页。 按照穷举法，我国31个(尚未计入香港特区)直辖市、省会和自治区首府的巡回路径应有约1.3261032种。我国学者对中国旅行商CTSP(Chinese TSP)问题进行了大量的研究，最新成果已到达15 449km。所得最短巡回路径为17102km。采用Hopfi