神经网络优化计算.ppt
第三章 神经网络优化计算,智能优化计算,数学与统计学院 2013年,教学重点 掌握BP神经网络的结构 掌握BP神经网络的算法原理 理解Hopfield网络的原理教学难点 BP神经网络的算法原理 Hopfield网络的原理另外，算法的实现请参阅程序文件,3.1 人工神经网络的基本概念 3.1.1 发展历史 3.1.2 McCulloch-Pitts神经元 3.1.3 网络结构的确定 3.1.4 关联权值的确定 3.1.5 工作阶段 3.2 多层前向神经网络 3.2.1 一般结构 3.2.2 反向传播算法 3.3 反馈型神经网络 3.3.1 离散Hopfield神经网络 3.3.2 连续Hopfield神经网络 3.3.3 Hopfield神经网络在TSP中的应用,智能优化计算,数学与统计学院 2013年,3.1 人工神经网络的基本概念,智能优化计算,数学与统计学院 2013年,“神经网络”与“人工神经网络”1943年，Warren McCulloch和Walter Pitts建立了第一个人工神经网络模型；1969年，Minsky和Papert发表Perceptrons；20世纪80年代，Hopfield将人工神经网络成功应用在组合优化问题。,3.1.1 发展历史,3.1 人工神经网络的基本概念,智能优化计算,数学与统计学院 2013年,重要意义 现代的神经网络开始于McCulloch,Pitts(1943)的先驱工作；他们的神经元模型假定遵循有-无模型律；如果如此简单的神经元数目足够多和适当设置连接权值并且同步操作,McCulloch&Pitts证明这样构成的网络原则上可以计算任何可计算函数；标志着神经网络和人工智能的诞生。,3.1.2 McCulloch-Pitts神经元,3.1 人工神经网络的基本概念,智能优化计算,数学与统计学院 2013年,结构 McCulloch-Pitts输出 函数定义为：,3.1.2 McCulloch-Pitts神经元,3.1 人工神经网络的基本概念,智能优化计算,数学与统计学院 2013年,网络的构建 Y=F(X),3.1.2 McCulloch-Pitts神经元,网络的拓扑结构 前向型、反馈型等神经元激活函数 阶跃函数 线性函数 Sigmoid函数,3.1 人工神经网络的基本概念,智能优化计算,数学与统计学院 2013年,3.1.3 网络结构的确定,确定的内容 权值wi和确定的方式 学习（训练）有指导的学习：已知一组正确的输入输出结果的条件下，神经网络依据这些数据，调整并确定权值；无指导的学习：只有输入数据，没有正确的输出结果情况下，确定权值。,3.1 人工神经网络的基本概念,智能优化计算,数学与统计学院 2013年,3.1.4 关联权值的确定,学习与工作的关系 先学习再工作,3.1 人工神经网络的基本概念,智能优化计算,数学与统计学院 2013年,3.1.5 工作阶段,3.2 多层前向神经网络,智能优化计算,数学与统计学院 2013年,多层 两层以上前向 无反馈,3.2.1 一般结构,3.2 多层前向神经网络,智能优化计算,数学与统计学院 2013年,目的 确定权值方法 反向推导,3.2.2 反向传播算法,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,一般结构 各神经元之间存在相互联系分类 连续系统：激活函数为连续函数 离散系统：激活函数为阶跃函数,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,Hopfield神经网络 1982年提出Hopfield反馈神经网络（HNN），证明在高强度连接下的神经网络依靠集体协同作用能自发产生计算行为。是典型的全连接网络，通过引入能量函数，使网络的平衡态与能量函数极小值解相对应。,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,网络结构 N为网络节点总数。,3.3.1 离散Hopfield神经网络,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,网络结构 一般认为vj(t)=0时神经元保持不变sj(t+1)=sj(t);一般情况下网络是对称的（wij=wji）且无自反馈（wjj=0）;整个网络的状态可用向量s表示：,3.3.1 离散Hopfield神经网络,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,工作方式 串行（异步，asynchronous）:任一时刻只有一个单元改变状态，其余单元保持不变；并行（同步，synchronous）：某一时刻所有神经元同时改变状态。稳定状态 如果从t=0的任一初始态s(0)开始变化，存在某一有限时刻t，从此以后网络状态不再变化，即s(t+1)=s(t)，则称网络达到稳定状态。,3.3.1 离散Hopfield神经网络,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,能量函数的定义 异步方式：同步方式：,3.3.1 离散Hopfield神经网络,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,能量函数 能量是有界的：从任一初始状态开始，若在每次迭代时都满足E0，则网络的能量将越来越小，最后趋向于稳定状态E0。,3.3.1 离散Hopfield神经网络,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,能量函数 分析异步（且网络对称wij=wji）情况下：假设只有神经元i改变状态,3.3.1 离散Hopfield神经网络,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,能量函数 分析异步（且网络对称wij=wji）情况下：假设只有神经元i改变状态,3.3.1 离散Hopfield神经网络,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,能量函数 分析同步（且网络对称wij=wji）情况下：,3.3.1 离散Hopfield神经网络,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,网络结构 与电子线路对应：放大器神经元 电阻、电容神经元的时间常数 电导权系数,3.3.2 连续Hopfield神经网络,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,网络的微分方程能量函数 可证明，若g-1为单调增且连续，Cj0，Tji=Tij，则有dE/dt0，当且仅当dvi/dt=0时dE/dt=0。,3.3.2 连续Hopfield神经网络,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,能量函数 随着时间的增长，神经网络在状态空间中的解轨迹总是向能量函数减小的方向变化，且网络的稳定点就是能量函数的极小点。,3.3.2 连续Hopfield神经网络,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,能量函数 将动力系统方程 简单记为：如果，则称ve是动力系统的平衡点，也称ve为吸引子。,3.3.2 连续Hopfield神经网络,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,能量函数 当从某一初始状态变化时，网络的演变是使E下降，达到某一局部极小时就停止变化。这些能量的局部极小点就是网络的稳定点或称吸引子。,3.3.2 连续Hopfield神经网络,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,Hopfield网络设计 当Hopfield用于优化计算时，网络的权值是确定的，应将目标函数与能量函数相对应，通过网络的运行使能量函数不断下降并最终达到最小，从而得到问题对应的极小解。,3.3.3 Hopfield神经网络在TSP中的应用,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,Hopfield网络设计 通常需要以下几方面的工作：（1）选择合适的问题表示方法，使神经网络的输出与问题的解相对应；（2）构造合适的能量函数，使其最小值对应问题的最优解；,3.3.3 Hopfield神经网络在TSP中的应用,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,Hopfield网络设计 通常需要以下几方面的工作：（3）由能量函数和稳定条件设计网络参数，如连接权值和偏置参数等；（4）构造相应的神经网络和动态方程；（5）用硬件实现或软件模拟。,3.3.3 Hopfield神经网络在TSP中的应用,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,TSP问题的表示 将TSP问题用一个nn矩阵表示，矩阵的每个元素代表一个神经元。代表商人行走顺序为：3124 每一行、每一列的和各为1。,3.3.3 Hopfield神经网络在TSP中的应用,能量函数的构建 每个神经元接收到的值为zij，其输出值为yij，激活函数采用Sigmoid函数，记两个城市x和y的距离是dxy。1）希望每一行的和为1，即 最小，每一行最多有一个1时，E10。,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,能量函数的构建 2）希望每一列的和为1，即 最小，每一列最多有一个1时，E20。3）希望每一行每一列正好有一个1，则 为零。,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,能量函数的构建 4）E1，E2，E3只能保证TSP的一个可行解，为了得到TSP的最小路径，当duv=dvu时，希望 最小，其中，yu0=yun，yu(n+1)=yu1。duvyuiyv(i+1)表示城市u和v之间的距离（i代表行走顺序）。,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,能量函数的构建 5）根据连续Hopfield神经网络能量函数，最后，能量函数表示为：A，B，C，D，为非负常数。,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,能量函数的构建 由动力学方程，,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,能量函数的构建 整理后得到：,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,10城市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,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,10城市TSP问题（d*=2.691）流程图：,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,10城市TSP问题（d*=2.691）初始参数：1 ABD500，C200 激励函数为Sigmoid 其中，00.02,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,10城市TSP问题（d*=2.691）初始参数：初始的yui 初始的zui=0.00001,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,10城市TSP问题（d*=2.691）,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,10城市TSP问题（d*=2.691）,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,10城市TSP问题（d*=2.691）,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,10城市TSP问题（d*=2.691）,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,10城市TSP问题（d*=2.691）,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,10城市TSP问题（d*=2.691）,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,10城市TSP问题（d*=2.691）,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,基于Hopfield网络优化的缺陷 用Hopfield网络优化的出发点建立在：（1）神经网络是稳定的，网络势必收敛到渐进平衡点；（2）神经网络的渐进平衡点恰好是能量函数的极小值。,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,基于Hopfield网络优化的缺陷 用Hopfield网络优化会导致：（1）网络最终收敛到局部极小解，而非全局最优解；（2）网络可能会收敛到问题的不可行解；（3）网络优化的最终结果很大程度上依赖于网络的参数。,3.3 反馈型神经网络,智能优化计算,数学与统计学院 2013年,3.3.3 Hopfield神经网络在TSP中的应用,课外习题BP神经网络数绝处理Hopfield解决TSP问题,智能优化计算,数学与统计学院 2013年,
