学术讨论—人工神经网络第七章.ppt

第第7章章循环循环(xnhun)(xnhun)网络网络主要内容主要内容Hopfield网络实现的自相联存储网络实现的自相联存储稳定性分析稳定性分析统计统计Hopfield网与网与Boltzmann机机基本双联存储器基本双联存储器(BAM)(BAM)的结构的结构(jigu)(jigu)与训练与训练几种相联存储网络几种相联存储网络用用Hopfield网解决网解决TSP问题。问题。第一页，共七十三页。2023/9/24 周日1第第7章章循环循环(xnhun)(xnhun)网络网络重点重点Hopfield网络实现的自相联存储网络实现的自相联存储基本双联存储器的结构与训练。基本双联存储器的结构与训练。难点难点(ndin)稳定性分析稳定性分析用用Hopfield网解决网解决TSP问题问题 第二页，共七十三页。2023/9/24 周日2第第7章章循环循环(xnhun)(xnhun)网络网络7.1循环网络的组织循环网络的组织 7.2稳定性分析稳定性分析 7.3统计统计Hopfield网与网与Boltzmann机机 7.4双联存储器的结构双联存储器的结构 7.5异相联存储异相联存储 7.6其它其它(qt)(qt)的双联存储器的双联存储器 7.7Hopfield网用于解决网用于解决TSP问题问题 第三页，共七十三页。2023/9/24 周日3第第7章章循环循环(xnhun)(xnhun)网络网络循环循环(xnhun)(xnhun)网络称为网络称为Hopfield网网 循环网络对输入信号的处理是一个逐渐循环网络对输入信号的处理是一个逐渐“修复修复(xif)(xif)”、“加强加强”的过程。的过程。强烈变化强烈变化较弱的变化较弱的变化不变化不变化第四页，共七十三页。2023/9/24 周日47.1 7.1 循环网络循环网络(wnglu)(wnglu)的组织的组织 网络结构网络结构X1Xno1om第五页，共七十三页。2023/9/24 周日57.1 7.1 循环网络循环网络(wnglu)(wnglu)的组织的组织 联联接接：神神经经元元之之间间都都是是互互联联的的wij，每每个个神神经经元都没有到自身的联接元都没有到自身的联接wii=0。神神经经元元个个数数h，输输入入(shr)(shr)向向量量维维数数n，输输出出向向量维数量维数m。hnn，hmhm，n1n1，m1m1。神经元神经元：输入、输出、隐藏：输入、输出、隐藏状态变化：状态变化：非同步、同步非同步、同步输入向量输入向量：X=(x1，x2，xn)输出向量输出向量：O=(o1，o2，om)第六页，共七十三页。2023/9/24 周日67.1 7.1 循环循环(xnhun)(xnhun)网络的组织网络的组织神经元的网络神经元的网络(wnglu)输输入：入：阈值阈值(y zh)函数函数：oj=1if netjj0if netj0，ok=1&ok=0，ok由由0 0变到变到1，netkk，netk-k0所以所以(suy)(suy)，-(netk-k)ok0故故0结论：网络的目标函数总是结论：网络的目标函数总是(zn sh)(zn sh)下降下降ok0,ok=0&ok=1，ok由由1 1变到变到0netkk，netk-k0-(netk-k)ok0故故r则使则使ANi的状态为的状态为1，否则使否则使ANi的状态为的状态为0；3 3 逐渐降低温度逐渐降低温度T，如果温度足够低，则算法，如果温度足够低，则算法(sun f)(sun f)结结束。否则，重复束。否则，重复2 第四十页，共七十三页。2023/9/24 周日40BoltzmannBoltzmann机的训练机的训练(xnlin)(xnlin)Boltzmann机机是是多多级级循循环环网网络络，是是Hopfield网网的一种扩展。的一种扩展。神经元神经元ANi实际输出实际输出(shch)(shch)状态状态oi=1的概率为：的概率为：T T趋趋近近于于0 0时时，神神经经元元的的状状态态(zhungti)(zhungti)不不再再具具有有随随机机性，性，BoltzmannBoltzmann机退化成一般机退化成一般HopfieldHopfield网。网。第四十一页，共七十三页。2023/9/24 周日41BoltzmannBoltzmann机的训练机的训练(xnlin)(xnlin)第四十二页，共七十三页。2023/9/24 周日42BoltzmannBoltzmann机的训练机的训练(xnlin)(xnlin)第四十三页，共七十三页。2023/9/24 周日43BoltzmannBoltzmann机的训练机的训练(xnlin)(xnlin)Boltzmann机机 是是 多多 级级 循循 环环(xnhun)(xnhun)网网 络络，是是Hopfield网的一种扩展。网的一种扩展。神经元神经元ANi网络输入为：网络输入为：T T趋趋近近于于0 0时时，神神经经元元的的状状态态不不再再具具有有(jyu)(jyu)随随机机性，性，BoltzmannBoltzmann机退化成一般机退化成一般HopfieldHopfield网。网。第四十四页，共七十三页。2023/9/24 周日44BoltzmannBoltzmann机的训练机的训练(xnlin)(xnlin)神神经经元元ANi实实际际输输出出状状态态(zhungti)(zhungti)oi=1的的概概率为率为神经元神经元ANi实际输出实际输出(shch)(shch)状态状态oi=0的概率为的概率为显然显然 越大，则越大，则 oi 取取1 1的概率越大的概率越大第四十五页，共七十三页。2023/9/24 周日45BoltzmannBoltzmann机的训练机的训练(xnlin)(xnlin)神经元神经元ANi在运行在运行(ynxng)(ynxng)中状态发生了变化中状态发生了变化 BoltzmannBoltzmann机的能量机的能量(nngling)(nngling)函数函数(一致性函数一致性函数)第四十六页，共七十三页。2023/9/24 周日46BoltzmannBoltzmann机的训练机的训练(xnlin)(xnlin)如如果果i0，神神经经元元ANi处处于于状状态态(zhungti)(zhungti)1的的概概率率就就应应该该越越大大，否否则则，神神经经元元ANi处处于于状状态态0 0的概就应该越大。的概就应该越大。i的值越大，神经元的值越大，神经元ANi应该处于状态应该处于状态1的概率就应该越大。反之，的概率就应该越大。反之，i的值越小，的值越小，神经元神经元ANi应该处于状态应该处于状态1的概率就应该越的概率就应该越小。从而，小。从而，oi=1的概率为：的概率为：第四十七页，共七十三页。2023/9/24 周日47BoltzmannBoltzmann机的训练机的训练(xnlin)(xnlin)处于状态处于状态a，b的概率的概率(gil)(gil)Pa和和Pb，对应于，对应于oi=1和和oi=0，其它的神经元在，其它的神经元在a，b状态下不状态下不变变 Pa=pi Pb=（1-1-pi）当系统的温度较低时，如果当系统的温度较低时，如果EaPb：网络处：网络处于较低能量于较低能量(nngling)状态的概率较大状态的概率较大第四十八页，共七十三页。2023/9/24 周日48BoltzmannBoltzmann机的训练机的训练(xnlin)(xnlin)网网络络进进行行足足够够多多次次迭迭代代后后，处处于于某某状状态态的的概概率率与与此此状状态态下下的的能能量量和和此此时时系系统统的的温温度度有有关。关。由由于于高高温温(gown)(gown)时时网网络络的的各各个个状状态态出出现现的的概概率率基基本本相相同同，这这就就给给它它逃逃离离局局部部极极小小点点提提供供了机会。了机会。第四十九页，共七十三页。2023/9/24 周日49BoltzmannBoltzmann机的训练机的训练(xnlin)(xnlin)1986年，年，Hinton和和Sejnowski训练方法训练方法自自由由概概率率(gil)P Pijij-：没没有有输输入入时时ANi和和ANj同同时处于激发状态的概率。时处于激发状态的概率。约约束束概概率率P Pijij+：加加上上输输入入后后ANi和和ANj同同时时处处于于激发状态的概率。激发状态的概率。联接权修改量联接权修改量：wij=(Pij+-Pij-)第五十页，共七十三页。2023/9/24 周日50算法算法(sun f)(sun f)7-2 Boltzmann7-2 Boltzmann机训练机训练算法算法(sun f)(sun f)1 1计算约束概率计算约束概率1.1对对样样本本(yngbn)(yngbn)集集中中每每个个样样本本(yngbn)(yngbn)，执执行行如如下操作：下操作：1.1.1将将样样本本加加在在网网络络上上（输输入入向向量量及及其其对应的输出向量）；对应的输出向量）；1.1.2让网络寻找平衡；让网络寻找平衡；1.1.3记录下所有神经元的状态；记录下所有神经元的状态；1.2计计算算对对所所有有的的样样本本，ANi和和ANj的的状状态态同同时为时为1的概率的概率P Pijij+；第五十一页，共七十三页。2023/9/24 周日51算法算法(sun f)(sun f)7-2 Boltzmann7-2 Boltzmann机训练机训练算法算法(sun f)(sun f)2计算自由概率计算自由概率2.1从从一一个个随随机机状状态态开开始始，不不加加输输入入、输输出出，让让网网络络自自由由运运行行，并并且且在在运运行行过过程程中中多多次纪录网络的状态；次纪录网络的状态；2.2对对所所有有(suyu)(suyu)的的ANi和和ANj，计计算算它它们们的的状态同时为状态同时为1的概率的概率P Pijij-；3对权矩阵进行调整对权矩阵进行调整wij=(Pij+-Pij-)第五十二页，共七十三页。2023/9/24 周日527.7 Hopfield7.7 Hopfield网解决网解决(jiju)(jiju)TSPTSP问题问题1985年，年，J.J.Hopfield和和D.W.Tank用循环用循环(xnhun)(xnhun)网求解网求解TSP。试验表明，当城市的个数。试验表明，当城市的个数不超过不超过30时，多可以给出最优解的近似解。时，多可以给出最优解的近似解。而当城市的个数超过而当城市的个数超过30时，最终的结果就不时，最终的结果就不太理想了太理想了 设问题中含有设问题中含有n个城市个城市,用用n*n个神经元构成个神经元构成网络网络 第五十三页，共七十三页。2023/9/24 周日53应用应用CHNN网解决优化计算问题网解决优化计算问题用用CHNN网解决优化问题一般需要以下几个步骤：网解决优化问题一般需要以下几个步骤：(1)对于特定的问题，要选择一种合适的表示方法，使对于特定的问题，要选择一种合适的表示方法，使得神经网络的输出与问题的解相对应；得神经网络的输出与问题的解相对应；(2)构造网络能量函数，使其最小值对应于问题的最构造网络能量函数，使其最小值对应于问题的最佳解；佳解；(3)将能量函数与将能量函数与Lyapunov函数函数标准形式进行比较，标准形式进行比较，可推出神经网络的权值与偏流的表达式，从而确定了网络可推出神经网络的权值与偏流的表达式，从而确定了网络的结构；的结构；(4)由网络结构建立网络的电子线路并运行，其稳态就由网络结构建立网络的电子线路并运行，其稳态就是在一定条件是在一定条件(tiojin)下的问题优化解。也可以编程模拟网下的问题优化解。也可以编程模拟网络的运行方式，在计算机上实现。络的运行方式，在计算机上实现。第五十四页，共七十三页。2023/9/24 周日54TSP问题是一个经典的人工智能难题。对问题是一个经典的人工智能难题。对n个城市个城市而言，可能而言，可能(knng)的路径总数为的路径总数为n!2n。随着。随着n的增的增加，路径数将按指数率急剧增长，即所谓加，路径数将按指数率急剧增长，即所谓“指数爆指数爆炸炸”。当。当n值较大时，用传统的数字计算机也无法值较大时，用传统的数字计算机也无法在有限时间内寻得答案。例如，在有限时间内寻得答案。例如，n50时，即使用时，即使用每秒每秒1亿次运算速度的巨型计算机按穷举搜索法，亿次运算速度的巨型计算机按穷举搜索法，也需要也需要51048年时间。即使是年时间。即使是n20个城市，也需个城市，也需求解求解350年。年。1985年年Hopfield和和Tank两人用两人用CHNN网络为解网络为解决决TSP难题开辟了一条崭新的途径，获得了巨大的难题开辟了一条崭新的途径，获得了巨大的成功。成功。第五十五页，共七十三页。2023/9/24 周日55其基本思想是把其基本思想是把TSP问题映射到问题映射到CHNN网络中网络中去，并设法用网络能量去，并设法用网络能量(nngling)代表路径总长。这样，代表路径总长。这样，当网络的能量当网络的能量(nngling)随着模拟电子线路状态的变迁，随着模拟电子线路状态的变迁，最终收敛于极小值最终收敛于极小值(或最小值或最小值)时，问题的较佳解时，问题的较佳解(或最佳解或最佳解)便随之求得。此外，由于模拟电子线路便随之求得。此外，由于模拟电子线路中的全部元件都是并行工作的，所以求解时间与城中的全部元件都是并行工作的，所以求解时间与城市数的多少无关，仅是运算放大器工作所需的微秒市数的多少无关，仅是运算放大器工作所需的微秒级时间，显著地提高了求解速度，充分展示了神经级时间，显著地提高了求解速度，充分展示了神经网络的巨大优越性。网络的巨大优越性。第五十六页，共七十三页。2023/9/24 周日561TSP问题描述问题描述为使为使CHNN网络完成优化计算，必须找到一种合适网络完成优化计算，必须找到一种合适的表示旅行路线的方法。鉴于的表示旅行路线的方法。鉴于TSP的解是的解是n个城市的有个城市的有序排列，因此可用一个由序排列，因此可用一个由nn个神经元构成的矩阵个神经元构成的矩阵(称为换位阵称为换位阵)来描述旅行路线。图来描述旅行路线。图7.5给出给出8城市城市TSP问题中的一条可能问题中的一条可能(knng)的有效路线的换位阵。的有效路线的换位阵。第五十七页，共七十三页。2023/9/24 周日57TSP问题描述问题描述为使为使CHNN网络完成优化计算，必须网络完成优化计算，必须(bx)找到一种合适找到一种合适的表示旅行路线的方法。鉴于的表示旅行路线的方法。鉴于TSP的解是的解是n个城市的有序排个城市的有序排列，因此可用一个由列，因此可用一个由nn个神经元构成的矩阵个神经元构成的矩阵(称为换位阵称为换位阵)来描述旅行路线。图给出来描述旅行路线。图给出8城市城市TSP问题中的一条可能的有问题中的一条可能的有效路线的换位阵。效路线的换位阵。第五十八页，共七十三页。2023/9/24 周日58由于每个城市仅能访问一次，因此换位阵中由于每个城市仅能访问一次，因此换位阵中每城市行只允许且必须有一个每城市行只允许且必须有一个1，其余元素均为，其余元素均为0。为了用神经元的状态表示某城市在某一有效。为了用神经元的状态表示某城市在某一有效(yuxio)路线中的位置，采用双下标路线中的位置，采用双下标Yxi，第一个下标，第一个下标x表示城市名，表示城市名，1，2，n；第二个下标；第二个下标i表表示该城市在访问路线中的位置，示该城市在访问路线中的位置，i1，2，n。例如，。例如，Y461表示旅途中第表示旅途中第6站应访问城市站应访问城市4；若；若Y460则表示第则表示第6站访问的不是城市站访问的不是城市4，而是其他某，而是其他某个城市。个城市。图图78中的换位阵所表示的旅行路线为中的换位阵所表示的旅行路线为:425813764，旅行路线总长为，旅行路线总长为d42+d25+d58+d81+d13+d37+d76+d64。第五十九页，共七十三页。2023/9/24 周日597.7 Hopfield7.7 Hopfield网解决网解决(jiju)(jiju)TSPTSP问题问题dxy城市城市X与城市与城市Y之间的距离之间的距离(jl)(jl)；vxi城市城市X的第的第i个神经元的状态：个神经元的状态：1城市城市X在第在第i个被访问个被访问vxi=0城市城市X不在第不在第i个被访问个被访问wxi,yj城市城市X的第的第i个神经元到城市个神经元到城市Y的第的第j个神经元的连接权。个神经元的连接权。第六十页，共七十三页。2023/9/24 周日607.7 Hopfield7.7 Hopfield网用于解决网用于解决(jiju)(jiju)TSPTSP问题问题例例如如(lr)：四四个个城城市市X、Y、Z、W城市名城市名访问顺序标示访问顺序标示1234X0100Y0001Z1000W0010第六十一页，共七十三页。2023/9/24 周日61能量函数设计能量函数设计用用CHNN求解求解TSP问题的关键是构造一个合适的能量函数。问题的关键是构造一个合适的能量函数。TSP问题的问题的能量函数由能量函数由4部分组成：部分组成：(1)能量能量E1城市行约束城市行约束当每个城市行中的当每个城市行中的1不多于一个时，应有第不多于一个时，应有第x行的全部行的全部(qunb)元素元素vxi按按顺序两两相乘之和为顺序两两相乘之和为0，即，即从而全部从而全部(qunb)n行的所有元素按顺序两两相乘之和也应为零，行的所有元素按顺序两两相乘之和也应为零，即即=0第六十二页，共七十三页。2023/9/24 周日62按此约束按此约束(yush)可定义能量可定义能量E1为为式中式中A为正常数。显然，当为正常数。显然，当E10时可保证对每个城市访问的次时可保证对每个城市访问的次数数(csh)不超过一次。不超过一次。(2)能量能量E2位置列约束位置列约束同理，当每个位置列中的同理，当每个位置列中的1不多于一个时，应有第不多于一个时，应有第i列的全部元列的全部元素素vxi按顺序两两相乘之和为按顺序两两相乘之和为0，即，即因此，全部因此，全部n列的所有元素按顺序列的所有元素按顺序(shnx)两两相乘之和也应为零，即两两相乘之和也应为零，即=0第六十三页，共七十三页。2023/9/24 周日63按此约束按此约束(yush)可定义能量可定义能量E2为为式中式中B为正常数。显然为正常数。显然(xinrn)，当，当E20时就能确保每次访问的城时就能确保每次访问的城市数不超过一个。市数不超过一个。(3)能量能量E3换位阵全局约束换位阵全局约束E10和和E20只是换位阵有效的必要条件，但不是充分条件。容易只是换位阵有效的必要条件，但不是充分条件。容易看出，当换位阵中各元素均为看出，当换位阵中各元素均为“0”时，也能满足时，也能满足El0和和E20，但这显，但这显然是无效的。因此，还需引入第三个约束条件然是无效的。因此，还需引入第三个约束条件全局约束条件，以全局约束条件，以确保换位阵中确保换位阵中1的数目等于城市数的数目等于城市数n，即，即第六十四页，共七十三页。2023/9/24 周日64因此因此(ync)定义能量定义能量E为为式中式中C为正常数。则为正常数。则E30可保证换位阵中可保证换位阵中1的数目正好的数目正好(zhngho)等于等于n。第六十五页，共七十三页。2023/9/24 周日65(4)能量能量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；反之亦然。因此；反之亦然。因此(ync)，有，有dxy(vxi,vy,i1)(vxi,vy,i1dxy。若定义。若定义n个城市各种可能的旅行路线长度为个城市各种可能的旅行路线长度为第六十六页，共七十三页。2023/9/24 周日66式中式中D为正常数，当为正常数，当E4最小时最小时(xiosh)旅行路线最短。旅行路线最短。综合以上综合以上4项能量，可得项能量，可得TSP问题的能量函数如下：问题的能量函数如下：(6.30)(6.30)第六十七页，共七十三页。2023/9/24 周日67网络网络(wnglu)的能量函数的能量函数第六十八页，共七十三页。2023/9/24 周日687.7 Hopfield7.7 Hopfield网用于解决网用于解决(jiju)(jiju)TSPTSP问题问题 联接矩阵联接矩阵(jzhn)wxi,yj=-Axy(1-ij)Bij(1-xy)Cdxy(ji+1+ji-1)1如果如果i=jij=0如果如果ij 第六十九页，共七十三页。2023/9/24 周日69图给出用图给出用CHNN网解决网解决(jiju)10城市城市TSP问题的结问题的结果。图果。图(a)为最优解，图为最优解，图(b)为较佳解。为较佳解。第七十页，共七十三页。2023/9/24 周日70按照穷举法，我国按照穷举法，我国31个个(尚未计入香港特区尚未计入香港特区)直直辖市、省会和自治区首府的巡回路径应有辖市、省会和自治区首府的巡回路径应有(ynyu)约约1.3261032种。我国学者对中国旅行商种。我国学者对中国旅行商CTSP(ChineseTSP)问题进行了大量的研究，最新成问题进行了大量的研究，最新成果已达到果已达到15449km。所得最短巡回路径为。所得最短巡回路径为17102km。采用。采用Hopfield经典算法，所得到的经典算法，所得到的400个解中最短个解中最短路径为路径为21777km。在。在Hopfield经典算法基础上增加约经典算法基础上增加约束条件，最短路径为束条件，最短路径为16262km。在。在Hopfield经典算法经典算法基础上将所有城市分成基础上将所有城市分成3部分后，求得最短路径为部分后，求得最短路径为15904km。第七十一页，共七十三页。2023/9/24 周日71第七十二页，共七十三页。2023/9/24 周日72内容(nirng)总结第7章 循环网络。状态变化：非同步、同步。1if netjj。0if netjj。ojif netj=j。改为S形函数后，系统(xtng)就成为一个连续系统(xtng)。wij=(Pij+-Pij-)。1如果i=j。0如果ij。72第七十三页，共七十三页。