欢迎来到天天文库
浏览记录
ID:33645599
大小:111.50 KB
页数:6页
时间:2019-02-27
《hopfield网络学习及其在最优化问题中的应用》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、Hopfield网络学习及其在最优化问题中的应用金海和*金海和,1964年生,博士后。主要研究方向:管理科学与工程,智能优化,信息技术,Email:jinhh@em.tsinghua.edu.cn(清华大学经济管理学院,北京100084)摘要本文针对Hopfield神经网络(HNN)所存在的极小值问题及缺乏学习能力的问题,提出了一种学习算法。它是将决定约束条件权值大小的系数作为学习参数,在参数空间里使参数向着HNN能量上升最快的方向学习,使网络状态能够有效地从一旦陷入的极小值状态中逃脱出来。该算法分别被应用于10、20城市的旅行商问题(TSP),结果能够以很高的比率收敛于最优解。关
2、键词Hopfield神经网络最速上升法参数学习最优化问题1引言Hopfield等通过用连续值HNN求解TSP,开辟了运用神经网络求解最优化问题的新途径[1]。但存在着(1)不能学习、(2)产生大量极小值等问题。作为解决极小值问题的方法之一,Hinton等提出了Boltzmann机模型及其学习算法[2],但因速度太慢,难以为现实所接受[3]。对于问题(2),笔者进行过深入的理论分析,并在数学上进行了证明[4]。针对问题(1)、(2),笔者提出了登山学习算法[5],但该算法中,为了避免因学习使最小值发生位移,以学习后的解为初始解,使网络回到未学习的HNN状态空间里进行状态更新至平衡状态
3、,显然增加了计算量。TSP常被用作研究最优化问题的范例[6],当运用HNN求解时,它的解依从于决定约束条件权值大小的系数,而这类系数在选择上具有一定的自由度。本文提出一种HNN学习算法,思想是,将决定约束条件权值大小的系数作为学习参数,在参数空间里使学习参数向着HNN能量上升最快的方向学习,使HNN能从一旦陷入的极小值状态中逃脱出来,直至找到最优解或满意解。本文将对N=10、20的TSP进行仿真实验,以证明其有效性。2Hopfield神经网络模型HNN是由大量简单的神经处理单元相互结合而成,并有对称性,无直接自反馈,非同期动作等约束。由n个单元构成的HNN,其能量函数可表达为(1)
4、e是能量,其自身是时间的函数;wij是单元i和j的权值;yi是第i个单元的输出;hi是第i个单元的阀值;τ是正的常数。各个单元内部电压随时间的变化可以用微分方程式(2)记述,xi是第i个单元的输入总和。单元的输入输出可采用sigmoid形的逻辑非线性单调增加函数,如式(3)。(2)(3)T是一个对神经单元输入输出函数的形状有影响的参数。HNN有收敛特性(证明见[7]),即在适当的初始条件下反复使其更新状态,则能量随时间单调地减小,状态向平衡状态的方向更新。能量减至全局最小或局部最小时,状态稳定在某个平衡状态。3基于Hopfield神经网络的TSP解法设有N个城市的集合{C1,C2,
5、…,CN},其中任意两个城市Ci和Ck之间的距离是dik(dik=dki),试找出一条最短的经过每个城市各一次(仅一次)并回到出发地的路径,这就是TSP。N个城市的TSP,用HNN求解时,需要用N2个神经单元。可以由一个行代表城市号码,列代表访问次序号码的矩阵来表示。其能量函数可以写成式(4)。(4)(5)yij是神经单元的状态变量,表示第i个城市第j回是否访问,且yij∈[0,1]。当yij≥0.5时,yij发火,意义是第i个城市在第j回被访问;当yij〈0.5时,yij不发火,意义是第i个城市在第j回不被访问。dik是城市i与城市k之间的距离。A,B是控制项系数,D是距离项系数
6、,其取值,一般算法是凭经验给出的。式中的第一项是行控制项,各行中只有一个“1”(一个城市只访问一次),第二项是列控制项,各列中只有一个“1”(一次只访问一个城市),第三项是距离项,是路径的全长。将式(4)和式(1)的各项对应,可导出其权值如式(5),阀值如式(6),同时定义符号式(7):(6)(7)TSP能量函数曲面复杂,存在许多极小值,只靠减小能量是不可能求得全局最优解或满意解。4Hopfeild神经网络学习算法图1是学习算法的流程图。框I是用学习后的新参数(第一次用初始给出的参数值),使HNN在状态空间里进行状态更新至平衡状态,t是状态更新次数,被定义为时间。框II是网络到达平
7、衡状态后,在参数空间里进行学习,s(离散值)是学习次数。为了简明起见,举一个只含二个极小值的HNN为例,说明其学习过程。图2是能量和状态的关系,属概念性图示,横坐标表示状态,纵坐标表示与之对应的能量(为了便于理解,用一维表示)。网络的初始状态和所对应的能量可以被定义为“山岳地形”上的某一点,这个点在特定“山谷”的斜面上。在状态空间里,由HNN的收敛特性可知,随着HNN状态的更新,这个点将滑向谷底。如初始状态是图2(a)上的点A,随着HNN状态的更新,将向谷底滑去,最终
此文档下载收益归作者所有