1、2022-6-221第第7章章 循环网络循环网络 主要内容主要内容 Hopfield网络实现的自相联存储网络实现的自相联存储稳定性分析稳定性分析统计统计Hopfield网与网与Boltzmann机机基本双联存储器基本双联存储器(BAM)(BAM)的结构与训练的结构与训练几种相联存储网络几种相联存储网络用用Hopfield网解决网解决TSP问题。问题。2022-6-222第第7章章 循环网络循环网络 重点重点 Hopfield网络实现的自相联存储网络实现的自相联存储基本双联存储器的结构与训练。基本双联存储器的结构与训练。 难点难点稳定性分析稳定性分析用用Hopfield网解决网解决TSP问题问题
2、 2022-6-223第第7章章 循环网络循环网络7.1 循环网络的组织循环网络的组织 7.2 稳定性分析稳定性分析 7.3 统计统计Hopfield网与网与Boltzmann机机 7.4 双联存储器的结构双联存储器的结构 7.5 异相联存储异相联存储 7.6 其它的双联存储器其它的双联存储器 7.7 Hopfield网用于解决网用于解决TSP问题问题 2022-6-224第第7章章 循环网络循环网络 循环网络称为循环网络称为Hopfield网网 循环网络对输入信号的处理是一个逐渐循环网络对输入信号的处理是一个逐渐“修复修复”、“加强加强”的过程。的过程。强烈变化强烈变化较弱的变化较弱的变化不
3、变化不变化2022-6-2257.1 7.1 循环网络的组织循环网络的组织 网络结构网络结构X1Xno1om2022-6-2267.1 7.1 循环网络的组织循环网络的组织 联接：联接：神经元之间都是互联的神经元之间都是互联的wij，每个神经，每个神经元都没有到自身的联接元都没有到自身的联接wii=0。神经元个数神经元个数h，输入向量维数，输入向量维数n，输出向量维，输出向量维数数m。hnn，hmhm，n1n1，m1m1。神经元神经元：输入、输出、隐藏：输入、输出、隐藏状态变化：状态变化：非同步、同步非同步、同步输入向量输入向量：X=(x1，x2，xn) 输出向量输出向量：O=(o1，o2，o
4、m) 2022-6-2277.1 7.1 循环网络的组织循环网络的组织神经元的网络输入：神经元的网络输入： hjiijiijjxownet&1阈值函数阈值函数：oj=1if netjj0if netj0，ok=1& ok=0，ok由由0 0变到变到1，netkk，netk-k0所以，所以，-( (netk-k)ok0故故0结论：网络的目标函数总是下降结论：网络的目标函数总是下降ok0, ok=0& ok=1，ok由由1 1变到变到0netkk，netk-k0-( (netk-k)ok0故故r 则使则使ANi的状态为的状态为1， 否则使否则使ANi的状态为的状态为0；3 3 逐渐降低温度逐渐降低
5、温度T，如果温度足够低，则算法结束。，如果温度足够低，则算法结束。否则，重复否则，重复2 2022-6-2241BoltzmannBoltzmann机的训练机的训练 Boltzmann机是多级循环网络，是机是多级循环网络，是Hopfield网网的一种扩展。的一种扩展。神经元神经元ANi实际输出状态实际输出状态oi=1的概率为：的概率为： )exp(11TnetpiiiT T趋近于趋近于0 0时，神经元的状态不再具有随机性，时，神经元的状态不再具有随机性，BoltzmannBoltzmann机退化成一般机退化成一般HopfieldHopfield网。网。 2022-6-2242Boltzmann
6、Boltzmann机的训练机的训练 2022-6-2243BoltzmannBoltzmann机的训练机的训练 2022-6-2244BoltzmannBoltzmann机的训练机的训练 Boltzmann机是多级循环网络，是机是多级循环网络，是Hopfield网网的一种扩展。的一种扩展。神经元神经元ANi网络输入为：网络输入为： jnjijiownetT T趋近于趋近于0 0时，神经元的状态不再具有随机性，时，神经元的状态不再具有随机性，BoltzmannBoltzmann机退化成一般机退化成一般HopfieldHopfield网。网。 2022-6-2245BoltzmannBoltzma
7、nn机的训练机的训练 神经元神经元ANi实际输出状态实际输出状态oi=1的概率为的概率为) 1(*) 1(1)0(/iioPeopopTuii神经元神经元ANi实际输出状态实际输出状态oi=0的概率为的概率为)exp(11) 1(Tnetopiii显然显然 越大，则越大，则 oi 取取1 1的概率越大的概率越大inet2022-6-2246BoltzmannBoltzmann机的训练机的训练 神经元神经元ANi在运行中状态发生了变化在运行中状态发生了变化 hjjjjijiijooowE1jijijiiiowoEoEE)1()0( BoltzmannBoltzmann机的能量函数机的能量函数(
8、(一致性函数一致性函数 ) )2022-6-2247BoltzmannBoltzmann机的训练机的训练 如果如果i0，神经元，神经元ANi处于状态处于状态1的概率的概率就应该越大，否则，神经元就应该越大，否则，神经元ANi处于状态处于状态0 0的概就应该越大。的概就应该越大。 i的值越大，神经元的值越大，神经元ANi应该处于状态应该处于状态1的概率就应该越大。反之的概率就应该越大。反之，i的值越小，的值越小，神经元神经元ANi应该处于状态应该处于状态1的概率就应该越的概率就应该越小。从而，小。从而，oi=1的概率为：的概率为： )exp(11TEpii2022-6-2248Boltzmann
9、Boltzmann机的训练机的训练 处于状态处于状态a，b的概率的概率Pa和和Pb，对应于，对应于oi=1和和oi=0，其它的神经元在，其它的神经元在a，b状态下不变状态下不变 Pa=pi Pb = =（1-1-pi） )TEEexp(PPbaba当系统的温度较低时，如果当系统的温度较低时，如果EaPb：网络处于较低能量状态的概率较大网络处于较低能量状态的概率较大2022-6-2249BoltzmannBoltzmann机的训练机的训练 网络进行足够多次迭代后，处于某状态的网络进行足够多次迭代后，处于某状态的概率与此状态下的能量和此时系统的温度有概率与此状态下的能量和此时系统的温度有关。关。
10、由于高温时网络的各个状态出现的概率基由于高温时网络的各个状态出现的概率基本相同，这就给它逃离局部极小点提供了机本相同，这就给它逃离局部极小点提供了机会。会。2022-6-2250BoltzmannBoltzmann机的训练机的训练1986年年，Hinton和和Sejnowski训练方法训练方法 自由概率自由概率P Pijij- -：没有输入时没有输入时ANi和和ANj同时同时处于激发状态的概率。处于激发状态的概率。 约束概率约束概率P Pijij+ +：加上输入后：加上输入后ANi和和ANj同时同时处于激发状态的概率。处于激发状态的概率。联接权修改量联接权修改量：wij=( Pij+ - Pi
11、j-) 2022-6-2251算法算法7-2 Boltzmann7-2 Boltzmann机训练算法机训练算法 1 1 计算约束概率计算约束概率 1.1 对样本集中每个样本，执行如下操作：对样本集中每个样本，执行如下操作： 1.1.1 将样本加在网络上（输入向量及其将样本加在网络上（输入向量及其对应的输出向量）；对应的输出向量）； 1.1.2 让网络寻找平衡；让网络寻找平衡； 1.1.3 记录下所有神经元的状态；记录下所有神经元的状态； 1.2 计算对所有的样本，计算对所有的样本，ANi和和ANj的状态同的状态同时为时为1的概率的概率P Pijij+ +；2022-6-2252算法算法7-2
12、Boltzmann7-2 Boltzmann机训练算法机训练算法2 计算自由概率计算自由概率 2.1 从一个随机状态开始，不加输入、输从一个随机状态开始，不加输入、输出，让网络自由运行，并且在运行过程中出，让网络自由运行，并且在运行过程中多次纪录网络的状态；多次纪录网络的状态； 2.2 对所有的对所有的ANi和和ANj，计算它们的状，计算它们的状态同时为态同时为1的概率的概率P Pijij- -； 3 对权矩阵进行调整对权矩阵进行调整wij=(Pij+-Pij-)2022-6-22537.7 Hopfield7.7 Hopfield网解决网解决TSPTSP问题问题 1985年，年，J. J.
13、Hopfield和和D. W. Tank用循环用循环网求解网求解TSP。试验表明，当城市的个数不超。试验表明，当城市的个数不超过过30时，多可以给出最优解的近似解。而时，多可以给出最优解的近似解。而当城市的个数超过当城市的个数超过30时，最终的结果就不时，最终的结果就不太理想了太理想了 设问题中含有设问题中含有n个城市个城市, ,用用n*n个神经元构成个神经元构成网络网络 2022-6-2254应用应用CHNN网解决优化计算问题网解决优化计算问题 用用CHNN网解决优化问题一般需要以下几个步骤网解决优化问题一般需要以下几个步骤： (1)对于特定的问题，要选择一种合适的表示方法对于特定的问题，要
14、选择一种合适的表示方法，使得神经网络的输出与问题的解相对应；，使得神经网络的输出与问题的解相对应； (2)构造网络能量函数，使其最小值对应于问题的构造网络能量函数，使其最小值对应于问题的最佳解；最佳解； (3)将能量函数与将能量函数与Lyapunov函数函数标准形式进行比较标准形式进行比较，可推出神经网络的权值与偏流的表达式，从而确定，可推出神经网络的权值与偏流的表达式，从而确定了网络的结构；了网络的结构； (4)由网络结构建立网络的电子线路并运行，其稳由网络结构建立网络的电子线路并运行，其稳态就是在一定条件下的问题优化解。也可以编程模拟态就是在一定条件下的问题优化解。也可以编程模拟网络的运行
15、方式，在计算机上实现。网络的运行方式，在计算机上实现。2022-6-2255 TSP问题是一个经典的人工智能难题。对问题是一个经典的人工智能难题。对n个城个城市而言，可能的路径总数为市而言，可能的路径总数为n!2n。随着。随着n的增的增加，路径数将按指数率急剧增长，即所谓加，路径数将按指数率急剧增长，即所谓“指指数爆炸数爆炸”。当。当n值较大时，用传统的数字计算机值较大时，用传统的数字计算机也无法在有限时间内寻得答案。例如，也无法在有限时间内寻得答案。例如，n50时时，即使用每秒，即使用每秒1亿次运算速度的巨型计算机按穷亿次运算速度的巨型计算机按穷举搜索法，也需要举搜索法，也需要51048年时
16、间。即使是年时间。即使是n20个城市，也需求解个城市，也需求解350年。年。 1985年年Hopfield和和Tank两人用两人用CHNN网络网络为解决为解决TSP难题开辟了一条崭新的途径，获得难题开辟了一条崭新的途径，获得了巨大的成功。了巨大的成功。2022-6-2256 其基本思想是把其基本思想是把TSP问题映射到问题映射到CHNN网网络中去，并设法用网络能量代表路径总长。这络中去，并设法用网络能量代表路径总长。这样，当网络的能量随着模拟电子线路状态的变样，当网络的能量随着模拟电子线路状态的变迁，最终收敛于极小值迁，最终收敛于极小值(或最小值或最小值)时，问题的较时，问题的较佳解佳解(或最
17、佳解或最佳解)便随之求得。此外，由于模拟电便随之求得。此外，由于模拟电子线路中的全部元件都是并行工作的，所以求子线路中的全部元件都是并行工作的，所以求解时间与城市数的多少无关，仅是运算放大器解时间与城市数的多少无关，仅是运算放大器工作所需的微秒级时间，显著地提高了求解速工作所需的微秒级时间，显著地提高了求解速度，充分展示了神经网络的巨大优越性。度，充分展示了神经网络的巨大优越性。2022-6-22571TSP问题描述问题描述 为使为使CHNN网络完成优化计算，必须找到一网络完成优化计算，必须找到一种合适的表示旅行路线的方法。鉴于种合适的表示旅行路线的方法。鉴于TSP的解是的解是n个城市的有序排
18、列，因此可用一个由个城市的有序排列，因此可用一个由nn个神个神经元构成的矩阵经元构成的矩阵(称为换位阵称为换位阵)来描述旅行路线。来描述旅行路线。图图7.5给出给出8城市城市TSP问题中的一条可能的有效路问题中的一条可能的有效路线的换位阵。线的换位阵。2022-6-2258 TSP问题描述问题描述 为使为使CHNN网络完成优化计算，必须找到一种合适网络完成优化计算，必须找到一种合适的表示旅行路线的方法。鉴于的表示旅行路线的方法。鉴于TSP的解是的解是n个城市的有个城市的有序排列，因此可用一个由序排列，因此可用一个由nn个神经元构成的矩阵个神经元构成的矩阵(称称为换位阵为换位阵)来描述旅行路线。
19、图给出来描述旅行路线。图给出8城市城市TSP问题中的问题中的一条可能的有效路线的换位阵。一条可能的有效路线的换位阵。2022-6-2259 由于每个城市仅能访问一次，因此换位阵由于每个城市仅能访问一次，因此换位阵中每城市行只允许且必须有一个中每城市行只允许且必须有一个1，其余元素均，其余元素均为为0。为了用神经元的状态表示某城市在某一有。为了用神经元的状态表示某城市在某一有效路线中的位置，采用双下标效路线中的位置，采用双下标 Yxi，第一个下标，第一个下标x表示城市名，表示城市名，1，2，n；第二个下标；第二个下标i表表示该城市在访问路线中的位置，示该城市在访问路线中的位置，i1，2，n。例如
20、，。例如，Y461表示旅途中第表示旅途中第6站应访问城市站应访问城市4；若若Y460则表示第则表示第6 站访问的不是城市站访问的不是城市4，而是，而是其他某个城市。其他某个城市。 图图78中的换位阵所表示的旅中的换位阵所表示的旅行路线为行路线为: 425813764，旅行，旅行路线总长为路线总长为d42+d25+d58+d81+d13+d37+d76+d64。2022-6-22607.7 Hopfield7.7 Hopfield网解决网解决TSPTSP问题问题 dxy城市城市X与城市与城市Y之间的距离；之间的距离； vxi城市城市X的第的第i个神经元的状态：个神经元的状态： 1城市城市X在第在
21、第i个被访问个被访问vxi= 0城市城市X不在第不在第i个被访问个被访问 wxi,yj城市城市X的第的第i个神经元到城市个神经元到城市Y的第的第j个神经元的连接权。个神经元的连接权。 2022-6-22617.7 Hopfield7.7 Hopfield网用于解决网用于解决TSPTSP问问题题例如：四个城市例如：四个城市X、Y、Z、W城市名城市名访问顺序标示访问顺序标示1234X0100Y0001Z1000W00102022-6-2262能量函数设计能量函数设计 用用CHNN求解求解TSP问题的关键是构造一个合适的能量函数问题的关键是构造一个合适的能量函数。TSP问题的能量函数由问题的能量函数
22、由4部分组成：部分组成： (1)能量能量E1城市行约束城市行约束 当每个城市行中的当每个城市行中的1不多于一个时，应有第不多于一个时，应有第x行的全部元素行的全部元素vxi按顺序两两相乘之和为按顺序两两相乘之和为0，即，即 从而全部从而全部n行的所有元素按顺序两两相乘之和也应为零，行的所有元素按顺序两两相乘之和也应为零，即即11110nnnxixjxij iv v 111nnxixjij iv v =02022-6-2263 按此约束可定义能量按此约束可定义能量E1为为 式中式中A为正常数。显然，当为正常数。显然，当E10时可保证对每个城市访问时可保证对每个城市访问的次数不超过一次。的次数不超
23、过一次。 (2)能量能量E2位置列约束位置列约束 同理，当每个位置列中的同理，当每个位置列中的1不多于一个时，应有第不多于一个时，应有第i列的全列的全部元素部元素vxi按顺序两两相乘之和为按顺序两两相乘之和为0，即，即 因此，全部因此，全部n列的所有元素按顺序两两相乘之和也应为零，列的所有元素按顺序两两相乘之和也应为零，即即111112nnnxixjxij iEAv v 111nnxiyixy xv v =02022-6-2264 按此约束可定义能量按此约束可定义能量E2为为 式中式中B为正常数。显然，当为正常数。显然，当E20时就能确保每次访问的城时就能确保每次访问的城市数不超过一个。市数不
24、超过一个。 (3)能量能量E3换位阵全局约束换位阵全局约束 E10和和E20只是换位阵有效的必要条件，但不是充分条只是换位阵有效的必要条件，但不是充分条件。容易看出，当换位阵中各元素均为件。容易看出，当换位阵中各元素均为“0”时，也能满足时，也能满足El0和和E20，但这显然是无效的。因此，还需引入第三个约束条件，但这显然是无效的。因此，还需引入第三个约束条件全局约束条件，以确保换位阵中全局约束条件，以确保换位阵中1的数目等于城市数的数目等于城市数n，即，即1211112nnnxiyiixyxBv vE 111nnxixinv2022-6-2265 因此定义能量因此定义能量E 为为 式中式中C
25、为正常数。则为正常数。则E30可保证换位阵中可保证换位阵中1的数的数目正好等于目正好等于n。 22xixinvC2022-6-2266 (4)能量能量E4旅行路线长度旅行路线长度 同时满足以上同时满足以上3个约束条件只能说明路线是有效个约束条件只能说明路线是有效的，但不一定是最优的。依题意，在路线有效的前提的，但不一定是最优的。依题意，在路线有效的前提下，其总长度应最短。为此在能量函数中尚须引入一下，其总长度应最短。为此在能量函数中尚须引入一个能反映路线总长度的分量个能反映路线总长度的分量E4，其定义式要能保证，其定义式要能保证E4随路线总长度的缩短而减小。为设计随路线总长度的缩短而减小。为设
26、计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,vy,i1dxy。若定义若定义n个城市各种可能的旅行路线长度为个城市各种可能的旅行路
27、线长度为2022-6-2267 式中式中D为正常数，当为正常数，当E4最小时旅行路线最短。最小时旅行路线最短。 综合以上综合以上4项能量，可得项能量，可得TSP问题的能量函数如下：问题的能量函数如下：4, 1, 11111(,) (,)2nnnxyxiy ixiy ixyiDd v vv vE (6.30)2022-6-2268网络的能量函数网络的能量函数xxzizizixixzxixiixzxzixixiijxjxivvvdDnvCvvBvvAE11222222022-6-22697.7 Hopfield7.7 Hopfield网用于解决网用于解决TSPTSP问题问题 联接矩阵联接矩阵 wx
28、i,yj= -Axy(1-ij) Bij(1-xy) C dxy(ji+1+ji-1) 1如果如果i=jij= 0如果如果ij 2022-6-2270 图给出用图给出用CHNN网解决网解决10城市城市TSP问题的结果问题的结果。图。图 (a)为最优解，图为最优解，图 (b)为较佳解。为较佳解。2022-6-2271 按照穷举法，我国按照穷举法，我国31个个(尚未计入香港特区尚未计入香港特区)直辖市、省会和自治区首府的巡回路径应有约直辖市、省会和自治区首府的巡回路径应有约1.3261032种。我国学者对中国旅行商种。我国学者对中国旅行商CTSP(Chinese TSP)问题进行了大量的研究，最问题进行了大量的研究，最新成果已达到新成果已达到15 449km。所得最短巡回路径为。所得最短巡回路径为17102km。采用。采用Hopfield经典算法，所得到的经典算法，所得到的400个解中最短路径为个解中最短路径为21 777km。在。在Hopfield经典算经典算法基础上增加约束条件，最短路径为法基础上增加约束条件，最短路径为16262km。在在Hopfield经典算法基础上将所有城市分成经典算法基础上将所有城市分成3部分部分后，求得最短路径为后，求得最短路径为15 904km。2022-6-2272
