第五章-神经网络优化计算.课件.ppt

1、华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 1 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 2 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 3 w“神经网络神经网络”与与“人工神经网络人工神经网络”w1943年，年，Warren McCulloch和和Walter Pitts建立了建立了第一个人工神经网络模型；第一个人工神经网络模型；w1969年，年，Minsky和和Papert发表发表Perceptrons；w20世纪世纪80年代，年代，Hop

2、field将人工神经网络成功应用将人工神经网络成功应用在组合优化问题。在组合优化问题。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 4 w重要意义重要意义 现代的神经网络开始于现代的神经网络开始于McCulloch, Pitts(1943)的先的先驱工作；驱工作； 他们的神经元模型假定遵循有他们的神经元模型假定遵循有-无模型律；无模型律； 如果如此简单的神经元数目足够多和适当设置连接如果如此简单的神经元数目足够多和适当设置连接权值并且同步操作权值并且同步操作, McCulloch & Pitts证明这样构证明这样构成的网络原则上可以计算任何可计算

3、函数；成的网络原则上可以计算任何可计算函数； 标志着神经网络和人工智能的诞生。标志着神经网络和人工智能的诞生。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 5 w结构结构 McCulloch-Pitts输出输出 函数定义为：函数定义为：InputsignalSynapticweightsSummingfunctionActivationfunctionOutputyx1x2xnw2wnw1)(f-0, 00, 1)sgn()sgn()(1xxxxwzfyniii其中，华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102

4、010年年年 6 w网络的构建网络的构建 Y=F(X) x1y1输出层输出层隐藏层隐藏层输入层输入层x2y2ymxn华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 7w网络的拓扑结构网络的拓扑结构 前向型、反馈型等前向型、反馈型等w神经元激活函数神经元激活函数 阶跃函数阶跃函数 线性函数线性函数 Sigmoid函数函数 baxxf)(xexf11)(f(x)x0+1华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 8w确定的内容确定的内容 权值权值wi和和w确定的方式确定的方式 学习（训练）学习（训练）

5、有指导的学习有指导的学习：已知一组正确的输入输出结果的条：已知一组正确的输入输出结果的条件下，神经网络依据这些数据，调整并确定权值；件下，神经网络依据这些数据，调整并确定权值； 无指导的学习无指导的学习：只有输入数据，没有正确的输出结：只有输入数据，没有正确的输出结果情况下，确定权值。果情况下，确定权值。 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 9w学习与工作的关系学习与工作的关系 先学习先学习再再工作工作 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 10 华东理工大学自动化系华东理工大学自

6、动化系华东理工大学自动化系 201020102010年年年 11w多层多层 两层以上两层以上w前向前向 无反馈无反馈输出层输出层隐藏层隐藏层输入层输入层y1y2ymx1x2xn华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 12w目的目的 确定权值确定权值w方法方法 反向推导反向推导华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 13 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 14w一般结构一般结构 各神经元之间存在相互联系各神经元之间存在相互联系w分

7、类分类 连续系统：激活函数为连续函数连续系统：激活函数为连续函数 离散系统：激活函数为阶跃函数离散系统：激活函数为阶跃函数华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 15wHopfield神经网络神经网络 1982年提出年提出Hopfield反馈神经网络（反馈神经网络（HNN），证明），证明在高强度连接下的神经网络依靠集体协同作用能自在高强度连接下的神经网络依靠集体协同作用能自发产生计算行为。发产生计算行为。 是典型的是典型的全连接网络全连接网络，通过引入能量函数，使网络，通过引入能量函数，使网络的平衡态与能量函数极小值解相对应。的平衡态与能量

8、函数极小值解相对应。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 16w网络结构网络结构 N为网络节点总数。为网络节点总数。 0)( , 10)( , 1) 1(),(sgn) 1( )()(1tvtvtstvtstswtvjjjjjjNiijij即s1(t+1)s2(t+1)sn(t+1)s1(t)s2(t)sn(t)w12w1nw21w2nwn1wn2v1(t)v2(t)vn(t)输入输入输出输出华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 17TNssss 21w网络结构网络结构 一般认为一般

9、认为vj(t)=0时神经元保持不变时神经元保持不变sj(t+1)=sj(t); 一般情况下网络是对称的（一般情况下网络是对称的（wij=wji）且无自反馈（）且无自反馈（wjj=0）; 整个网络的状态可用向量整个网络的状态可用向量s表示：表示： 0)( , 10)( , 1) 1(),(sgn) 1( )()(1tvtvtstvtstswtvjjjjjjNiijij即华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 18w工作方式工作方式 串行（异步，串行（异步，asynchronous）:任一时刻只有一个任一时刻只有一个单元改变状态，其余单元保持不

10、变；单元改变状态，其余单元保持不变； 并行（同步，并行（同步，synchronous）：某一时刻所有神经）：某一时刻所有神经元同时改变状态。元同时改变状态。w稳定状态稳定状态 如果从如果从t=0的任一初始态的任一初始态s(0)开始变化，存在某一有开始变化，存在某一有限时刻限时刻t，从此以后网络状态不再变化，即，从此以后网络状态不再变化，即s(t+1)=s(t)，则称网络达到，则称网络达到稳定状态稳定状态。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 19w能量函数的定义能量函数的定义 异步方式：异步方式： 同步方式：同步方式：swss)()()(

11、21)()()(21ttttststswETTiiiijjiji)() 1(21)() 1(21 )1()(21)() 1(21tttttstststswETTiiiiijjijisswss 0)( , 10)( , 1) 1(),(sgn) 1( )()(1tvtvtstvtstswtvjjjjjjNiijij即华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 20w能量函数能量函数 能量是有界的：能量是有界的： 从任一初始状态开始，若在每次迭代时都满足从任一初始状态开始，若在每次迭代时都满足E0，则网络的能量将越来越小，最后趋向于稳，则网络的能量

12、将越来越小，最后趋向于稳定状态定状态E0 。iiijijiiiijjijiwssswE|21|21|华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 211)( , 1) 1( , 21)( , 1) 1( , 2)() 1( , 0)() 1()(tststststststststsiiiiiiiiiw能量函数能量函数 分析异步（且网络对称分析异步（且网络对称wij=wji）情况下：）情况下： 假设只有神经元假设只有神经元i改变状态改变状态同号同号同号同号华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年

13、220)() 1( )() 1(2121 21212211tstsswsswststswsswsswssswsswEiiiiiiijjijiiiiiiijijjiijijijiiNjijjiNjijijw能量函数能量函数 分析异步（且网络对称分析异步（且网络对称wij=wji）情况下：）情况下： 假设只有神经元假设只有神经元i改变状态改变状态同号同号swss)()()(21)()()(21ttttststswETTiiiijjiji 0)( , 10)( , 1) 1(),(sgn) 1( )()(1tvtvtstvtstswtvjjjjjjNiijij即华东理工大学自动化系华东理工大学自动化

14、系华东理工大学自动化系 201020102010年年年 23w能量函数能量函数 分析同步（且网络对称分析同步（且网络对称wij=wji）情况下：）情况下： 0)1() 1()(21 )1() 1(21)1() 1()(21 )1()(21) 1()(21)() 1(21)() 1(21ttttttttttttttttETTTTTTTTsswssssswssswsssswss同号同号华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 24w网络结构网络结构 与电子线路对应：与电子线路对应： g1C1I1z1g2C2I2z2g3C3I3z3gnCnInzn

15、y1y2y3yny1y2y3ynw21wn1w31w12w13w1nw23w2nw32w3nwn2wn3. . . . .华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 25iiinijjjijiiIzGywdtdzC1w网络的微分方程网络的微分方程 Gi.giCiwi1wi2winIiy1y2ynziyi( )ia uyi =a(zi)(y1-zi)wi1(y2-zi)wi2(yn-zi)winiiinijjijijiiIzgzywdtdzC1)(iiinijjijnijjjijiiIzgwywdtdzC11输入输入输出输出华东理工大学自动化系华

16、东理工大学自动化系华东理工大学自动化系 201020102010年年年 26w网络的微分方程网络的微分方程 ze是动力系统的平是动力系统的平 衡点，称吸引子。衡点，称吸引子。 )(1iiiiinijjjijiizayIzGywdtdzC),(tdtdzfztte ),(0zf.giCiwi1wi2winIiy1y2ynziyi( )ia uyi =a(zi)(y1-zi)wi1(y2-zi)wi2(yn-zi)win华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 27w能量函数能量函数 可证明，若可证明，若a-1为单调增且连续，为单调增且连续，Ci

17、0，wji=wij，则，则有有dE/dt0，当且仅当，当且仅当dzi/dt=0时时dE/dt=0。 niviiiiniiininjjiijidyyaGyIyywE101111)(121niiiiiidtdydyydaCdtdE121)(1iiyEdtdz华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 28w能量函数能量函数 当从某一初始状态变化时，网络的演变是使当从某一初始状态变化时，网络的演变是使E下降，下降，达到某一局部极小时就停止变化。这些能量的局部达到某一局部极小时就停止变化。这些能量的局部极小点就是网络的极小点就是网络的稳定点稳定点或称或

18、称吸引子吸引子。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 29wHopfield网络设计网络设计 当当Hopfield用于优化计算时，网络的权值是确定用于优化计算时，网络的权值是确定的，应将目标函数与能量函数相对应，通过网络的，应将目标函数与能量函数相对应，通过网络的运行使能量函数不断下降并最终达到最小，从的运行使能量函数不断下降并最终达到最小，从而得到问题对应的极小解。而得到问题对应的极小解。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 30wHopfield网络设计网络设计 通常需要以下几方

19、面的工作：通常需要以下几方面的工作： （1）选择合适的问题表示方法，使神经网络的输）选择合适的问题表示方法，使神经网络的输出与问题的解相对应；出与问题的解相对应； （2）构造合适的能量函数，使其最小值对应问题）构造合适的能量函数，使其最小值对应问题的最优解；的最优解； 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 31wHopfield网络设计网络设计 通常需要以下几方面的工作：通常需要以下几方面的工作： （3）由能量函数和稳定条件设计网络参数，如连）由能量函数和稳定条件设计网络参数，如连接权值和偏置参数等；接权值和偏置参数等； （4）构造相应的

20、神经网络和动态方程；）构造相应的神经网络和动态方程； （5）用硬件实现或软件模拟。）用硬件实现或软件模拟。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 32wTSP问题的表示问题的表示 将将TSP问题用一个问题用一个nn矩阵表示，矩阵的每个元素矩阵表示，矩阵的每个元素代表一个神经元。代表一个神经元。 代表商人行走顺序为：代表商人行走顺序为：3124 每一行、每一列的和各为每一行、每一列的和各为1。1为是，为是，0为否为否第第1站站第第2站站第第3站站第第4站站城市城市10100城市城市20010城市城市31000城市城市40001华东理工大学自动

21、化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 33w能量函数的构建能量函数的构建 每个神经元接收到的值为每个神经元接收到的值为zij，其输出值为，其输出值为yij，激活，激活函数采用函数采用Sigmoid函数，记两个城市函数，记两个城市x和和y的距离是的距离是dxy。 1）希望每一行的和为）希望每一行的和为1，即，即 最小，每一行最多有一个最小，每一行最多有一个1时，时，E10。nuniijujuiyyE111第第1站站第第2站站第第3站站第第4站站城市城市10100城市城市20010城市城市31000城市城市40001每行的输出每行的输出值两两相乘值两两相乘之

22、和之和华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 34w能量函数的构建能量函数的构建 2）希望每一列的和为）希望每一列的和为1，即，即 最小，每一列最多有一个最小，每一列最多有一个1时，时，E20。 3）希望每一行每一列正好有一个）希望每一行每一列正好有一个1，则，则 最小时为零。最小时为零。ninuuvviuiyyE1122113nyEninjij第第1站站第第2站站第第3站站第第4站站城市城市10100城市城市20010城市城市31000城市城市40001每列的输出每列的输出值两两相乘值两两相乘之和之和所有的输出所有的输出值两两相乘值两两相

23、乘之和应该为之和应该为n华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 35w能量函数的构建能量函数的构建 4）E1，E2，E3只能保证只能保证TSP的一个可行解，为了的一个可行解，为了得到得到TSP的最小路径，当的最小路径，当duv=dvu时，希望时，希望 最小，其中，最小，其中，yu0=yun，yu(n+1)=yu1。duvyuiyv(i+1)表示城表示城市市u和和v之间的距离（之间的距离（i代表行走顺序）。代表行走顺序）。nuuvniivivuiuvyyydE11)1()1(4)(第第1站站第第2站站第第3站站第第4站站城市城市10100城市

24、城市20010城市城市31000城市城市40001华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 36w能量函数的构建能量函数的构建 5）根据连续）根据连续Hopfield神经网络能量函数，神经网络能量函数， 最后，能量函数表示为：最后，能量函数表示为： A，B，C，D，为非负常数。为非负常数。jiyijijdyyaE,015)(543212222EEDECEBEAE)(uiuizay华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 37w能量函数的构建能量函数的构建 由动力学方程，由动力学方程， )()

25、()( 1111uiuiuvviviuvnvnjvjuvviijujuiuiuizayyydDnyCyByAzyEdtdz华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 38w能量函数的构建能量函数的构建 参照动力学方程，可知：参照动力学方程，可知：0 , , 0 , 1 )()1 ()1 (1,1,uuijuiijjjuvuvijijuvvjuidjijinCIDdCBAw其中，)(1iiiiinijjjijiizayIzGywdtdzC )()()( 1111uiuiuvviviuvnvnjvjuvviijujuiuiuizayyydDnyCy

26、ByAzyEdtdz华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 39w10城市城市TSP问题（问题（d*=2.691） 0.4 0.4439; 0.2439 0.1463; 0.1707 0.2293; 0.2293 0.761; 0.5171 0.9414; 0.8732 0.6536; 0.6878 0.5219; 0.8488 0.3609; 0.6683 0.2536; 0.6195 0.2634华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 40w10城市城市TSP问题（问题（d*=2.6

27、91） 流程图：流程图： 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 41w10城市城市TSP问题（问题（d*=2.691） 初始参数：初始参数： 1 ABD500，C200 激励函数为激励函数为Sigmoid 其中，其中，00.020211)(uizuiuiezfy华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 42w10城市城市TSP问题（问题（d*=2.691） 初始参数：初始参数： 初始的初始的yui 初始的初始的zui =0.0000110110110uiuiy00000001 . 01

28、. 0 ,9ln2uiuiuizzzzz华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 43w10城市城市TSP问题（问题（d*=2.691） 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 44w10城市城市TSP问题（问题（d*=2.691） 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 45w10城市城市TSP问题（问题（d*=2.691） 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 46w10城市城

29、市TSP问题（问题（d*=2.691） 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 47w10城市城市TSP问题（问题（d*=2.691） 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 48w10城市城市TSP问题（问题（d*=2.691） 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 49w10城市城市TSP问题（问题（d*=2.691） 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 50w基于基于H

30、opfield网络优化的缺陷网络优化的缺陷 用用Hopfield网络优化的出发点建立在：网络优化的出发点建立在： （1）神经网络是稳定的，网络势必收敛到渐进平）神经网络是稳定的，网络势必收敛到渐进平衡点；衡点； （2）神经网络的渐进平衡点恰好是能量函数的极）神经网络的渐进平衡点恰好是能量函数的极小值。小值。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 51w基于基于Hopfield网络优化的缺陷网络优化的缺陷 用用Hopfield网络优化会导致：网络优化会导致： （1）网络最终收敛到局部极小解，而非全局最优）网络最终收敛到局部极小解，而非全局最优解；解； （2）网络可能会收敛到问题的不可行解；）网络可能会收敛到问题的不可行解； （3）网络优化的最终结果很大程度上依赖于网络）网络优化的最终结果很大程度上依赖于网络的参数。的参数。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 201020102010年年年 52