神经网络优化计算课件.ppt

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

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

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

4、 Y=F(X)x1y1输出层输出层隐藏层隐藏层输入层输入层x2y2ymxnw网络的拓扑结构网络的拓扑结构 前向型、反馈型等前向型、反馈型等w神经元激活函数神经元激活函数 阶跃函数阶跃函数 线性函数线性函数 Sigmoid函数函数 baxxf)(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 xexf11)(f(x)x0+1w确定的内容确定的内容 权值权值wi和和w确定的方式确定的方式 学习（训练）学习（训练）有指导的学习：已知一组正确的输入输出结果的条有指导的学习：已知一组正确的输入输出结果的条件下，神经网络依据这些数据，调整并确定权值；件下，神经

5、网络依据这些数据，调整并确定权值；无指导的学习：只有输入数据，没有正确的输出结无指导的学习：只有输入数据，没有正确的输出结果情况下，确定权值。果情况下，确定权值。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w学习与工作的关系学习与工作的关系 先学习先学习再再工作工作 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w多层多层 两层以上两层以上w前向前向 无反馈无反馈输出层输出层隐藏层隐藏层输入层输入层y1y

6、2ymx1x2xn华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w目的目的 确定权值确定权值w方法方法 反向推导反向推导华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w一般结构一般结构 各神经元之间存在相互联系各神经元之间存在相互联系w分类分类 连续系统：激活函数为连续函数连续系统：激活函数为连续函数 离散系统：激活函数为阶跃函数离散系统：激活函数为阶跃函数华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wHopfield神经网络神经网络 1982年提出

7、年提出Hopfield反馈神经网络（反馈神经网络（HNN），证明），证明在高强度连接下的神经网络依靠集体协同作用能自在高强度连接下的神经网络依靠集体协同作用能自发产生计算行为。发产生计算行为。是典型的是典型的全连接网络全连接网络，通过引入能量函数，使网络，通过引入能量函数，使网络的平衡态与能量函数极小值解相对应。的平衡态与能量函数极小值解相对应。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w网络结构网络结构 N为网络节点总数。为网络节点总数。0)(,10)(,1)1(),(sgn)1()()(1tvtvtstvtstswtvjjjjjjNiij

8、ij即s1(t+1)s2(t+1)sn(t+1)s1(t)s2(t)sn(t)w12w1nw21w2nwn1wn2华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w网络结构网络结构 一般认为一般认为vj(t)=0时神经元保持不变时神经元保持不变sj(t+1)=sj(t);一般情况下网络是对称的（一般情况下网络是对称的（wij=wji）且无自反馈（）且无自反馈（wjj=0）;整个网络的状态可用向量整个网络的状态可用向量s表示：表示：TNssss 21华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w工作方

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

10、20072007年年年 w能量函数的定义能量函数的定义 异步方式：异步方式：同步方式：同步方式：swss)()()(21)()()(21ttttststswETTiiiijjiji)()1(21)()1(21 )1()(21)()1(21tttttstststswETTiiiiijjijisswss华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w能量函数能量函数 能量是有界的：能量是有界的：从任一初始状态开始，若在每次迭代时都满足从任一初始状态开始，若在每次迭代时都满足E0，则网络的能量将越来越小，最后趋向于稳，则网络的能量将越来越小，最后趋向于

11、稳定状态定状态E0。iiijijiiiijjijiwssswE|21|21|1)(,1)1(,21)(,1)1(,2)()1(,0)()1()(tststststststststsiiiiiiiii华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w能量函数能量函数 分析异步（且网络对称分析异步（且网络对称wij=wji）情况下：）情况下：假设只有神经元假设只有神经元i改变状态改变状态swss)()()(21)()()(21ttttststswETTiiiijjiji0)()1()()1(2121 21212211tstsswsswststswssw

12、sswssswsswEiiiiiiijjijiiiiiiijijjiijijijiiNjijjiNjijij华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w能量函数能量函数 分析异步（且网络对称分析异步（且网络对称wij=wji）情况下：）情况下：假设只有神经元假设只有神经元i改变状态改变状态同号同号swss)()()(21)()()(21ttttststswETTiiiijjiji华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w能量函数能量函数 分析同步（且网络对称分析同步（且网络对称wij=wj

13、i）情况下：）情况下：0)1()1()(21 )1()1(21)1()1()(21 )1()(21)1()(21)()1(21)()1(21ttttttttttttttttETTTTTTTTsswssssswssswsssswss同号同号华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w网络结构网络结构 与电子线路对应：与电子线路对应：放大器放大器神经元神经元 电阻、电容电阻、电容神经元的时间常数神经元的时间常数 电导电导权系数权系数华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w网络的微分方程网络的

14、微分方程w能量函数能量函数 可证明，若可证明，若g-1为单调增且连续，为单调增且连续，Cj0，Tji=Tij，则，则有有dE/dt0，当且仅当，当且仅当dvi/dt=0时时dE/dt=0。)(1jjjjjNiijijjvgsiRvsTdtdvCNjsjjjjNjjjNiNjjiijjdvvgRsissTE101111)(121华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w能量函数能量函数 随着时间的增长，神经网络在状态空间中的解轨迹随着时间的增长，神经网络在状态空间中的解轨迹总是向能量函数减小的方向变化，且网络的稳定点总是向能量函数减小的方向变

15、化，且网络的稳定点就是能量函数的极小点。就是能量函数的极小点。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w能量函数能量函数 将动力系统方程将动力系统方程 简单记为：简单记为：如果如果 ，则称，则称ve是动力系统的平衡点，也是动力系统的平衡点，也称称ve为吸引子。为吸引子。)(1jjjjjNiijijjvgsiRvsTdtdvC),(tvqdtdvttvqe,0),(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w能量函数能量函数 当从某一初始状态变化时，网络的演变是使当从某一初始状态变化时，网络

16、的演变是使E下降，下降，达到某一局部极小时就停止变化。这些能量的局部达到某一局部极小时就停止变化。这些能量的局部极小点就是网络的极小点就是网络的稳定点稳定点或称或称吸引子吸引子。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wHopfield网络设计网络设计 当当Hopfield用于优化计算时，网络的权值是确定用于优化计算时，网络的权值是确定的，应将目标函数与能量函数相对应，通过网络的，应将目标函数与能量函数相对应，通过网络的运行使能量函数不断下降并最终达到最小，从的运行使能量函数不断下降并最终达到最小，从而得到问题对应的极小解。而得到问题对应的

17、极小解。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wHopfield网络设计网络设计 通常需要以下几方面的工作：通常需要以下几方面的工作：（1）选择合适的问题表示方法，使神经网络的输）选择合适的问题表示方法，使神经网络的输出与问题的解相对应；出与问题的解相对应；（2）构造合适的能量函数，使其最小值对应问题）构造合适的能量函数，使其最小值对应问题的最优解；的最优解；华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wHopfield网络设计网络设计 通常需要以下几方面的工作：通常需要以下几方面的工作：

18、（3）由能量函数和稳定条件设计网络参数，如连）由能量函数和稳定条件设计网络参数，如连接权值和偏置参数等；接权值和偏置参数等；（4）构造相应的神经网络和动态方程；）构造相应的神经网络和动态方程；（5）用硬件实现或软件模拟。）用硬件实现或软件模拟。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wTSP问题的表示问题的表示 将将TSP问题用一个问题用一个nn矩阵表示，矩阵的每个元素矩阵表示，矩阵的每个元素代表一个神经元。代表一个神经元。代表商人行走顺序为：代表商人行走顺序为：3124 每一行、每一列的和各为每一行、每一列的和各为1。1为是，为是，0为否

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

20、站第第4站站城市城市10100城市城市20010城市城市31000城市城市40001w能量函数的构建能量函数的构建 2）希望每一列的和为）希望每一列的和为1，即，即 最小，每一列最多有一个最小，每一列最多有一个1时，时，E20。3）希望每一行每一列正好有一个）希望每一行每一列正好有一个1，则，则 为零。为零。ninuuvviuiyyE112华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 2113nyEninjij第第1站站第第2站站第第3站站第第4站站城市城市10100城市城市20010城市城市31000城市城市40001w能量函数的构建能量函数的

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

22、量函数的构建能量函数的构建 5）根据连续）根据连续Hopfield神经网络能量函数，神经网络能量函数，最后，能量函数表示为：最后，能量函数表示为：A，B，C，D，为非负常数。为非负常数。jiyijijdyyfE,015)(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 543212222EEDECEBEAEw能量函数的构建能量函数的构建 由动力学方程，由动力学方程，)()()(1111uiuiuvviviuvnvnjvjuvviijujuiuiuizfyyydDnyCyByAzyEdtdz华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系

23、 200720072007年年年 w能量函数的构建能量函数的构建 整理后得到：整理后得到：华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 0 ,0 ,1 )()1()1(1,1,uuijuiijjjuvuvijijuvvjuidjijinCIDdCBAw其中，w10城市城市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;

24、0.6195 0.2634华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w10城市城市TSP问题（问题（d*=2.691）流程图：流程图：华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w10城市城市TSP问题（问题（d*=2.691）初始参数：初始参数：1 ABD500，C200 激励函数为激励函数为Sigmoid 其中，其中，00.02华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 0211)(uizuiuiezfyw10城市城市TSP问题（问题（d*

25、=2.691）初始参数：初始参数：初始的初始的yui 初始的初始的zui =0.0000110110110uiuiy华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 00000001.01.0 ,9ln2uiuiuizzzzzw10城市城市TSP问题（问题（d*=2.691）华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w10城市城市TSP问题（问题（d*=2.691）华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w10城市城市TSP问题（问题（d*=2.

26、691）华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w10城市城市TSP问题（问题（d*=2.691）华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w10城市城市TSP问题（问题（d*=2.691）华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w10城市城市TSP问题（问题（d*=2.691）华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w10城市城市TSP问题（问题（d*=2.691）华东理工大学自动

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