0104073Hopfield网络学习及其在最优化问题中的应用

管理科学与系统科学研究新进展——第6届全国青年管理科学与系统科学学术会议论文集2001年·大连3Hopfield网络学习及其在最优化问题中的应用金海和（清华大学经济管理学院，北京100084）摘要本文针对Hopfield神经网络（HNN）所存在的极小值问题及缺乏学习能力的问题，提出了一种学习算法。它是将决定约束条件权值大小的系数作为学习参数，在参数空间里使参数向着HNN能量上升最快的方向学习，使网络状态能够有效地从一旦陷入的极小值状态中逃脱出来。该算法分别被应用于10、20城市的旅行商问题（TSP），结果能够以很高的比率收敛于最优解。关键词Hopfield神经网络最速上升法参数学习最优化问题1引言Hopfield等通过用连续值HNN求解TSP，开辟了运用神经网络求解最优化问题的新途径[1]。但存在着（1）不能学习、（2）产生大量极小值等问题。作为解决极小值问题的方法之一，Hinton等提出了Boltzmann机模型及其学习算法[2]，但因速度太慢，难以为现实所接受[3]。对于问题（2），笔者进行过深入的理论分析，并在数学上进行了证明[4]。针对问题（1）、（2），笔者提出了登山学习算法[5]，但该算法中，为了避免因学习使最小值发生位移，以学习后的解为初始解，使网络回到未学习的HNN状态空间里进行状态更新至平衡状态，显然增加了计算量。TSP常被用作研究最优化问题的范例[6]，当运用HNN求解时，它的解依从于决定约束条件权值大小的系数，而这类系数在选择上具有一定的自由度。本文提出一种HNN学习算法，思想是，将决定约束条件权值大小的系数作为学习参数，在参数空间里使学习参数向着HNN能量上升最快的方向学习，使HNN能从一旦陷入的极小值状态中逃脱出来，直至找到最优解或满意解。本文将对N=10、20的TSP进行仿真实验，以证明其有效性。2Hopfield神经网络模型HNN是由大量简单的神经处理单元相互结合而成，并有对称性，无直接自反馈，非同期动作等约束。由n个单元构成的HNN，其能量函数可表达为niyiniiininjjiijidyyfhyyywe101111)(121(1)e是能量，其自身是时间的函数；wij是单元i和j的权值；yi是第i个单元的输出；hi是第i个单元的阀值；τ是正的常数。各个单元内部电压随时间的变化可以用微分方程式（2）记述，xi是第i个单元的输入总和。单元的输入输出可采用sigmoid形的逻辑非线性单调增加函数，如式（3）。金海和,1964年生,博士后。主要研究方向:管理科学与工程,智能优化,信息技术,Email:[e-mail]管理科学与系统科学研究新进展——第6届全国青年管理科学与系统科学学术会议论文集2001年·大连4njijijiihywxdtdx1（2）)(11)(Tixexfyii（3）T是一个对神经单元输入输出函数的形状有影响的参数。HNN有收敛特性(证明见[7])，即在适当的初始条件下反复使其更新状态，则能量随时间单调地减小，状态向平衡状态的方向更新。能量减至全局最小或局部最小时，状态稳定在某个平衡状态。3基于Hopfield神经网络的TSP解法设有N个城市的集合{C1，C2，…，CN}，其中任意两个城市Ci和Ck之间的距离是dik（dik=dki），试找出一条最短的经过每个城市各一次（仅一次）并回到出发地的路径，这就是TSP。N个城市的TSP，用HNN求解时，需要用N2个神经单元。可以由一个行代表城市号码，列代表访问次序号码的矩阵来表示。其能量函数可以写成式（4）。NiNkNjjkjkijikNjNiijNiNjijDBAyyydDyByAeeee)(2)1(2)1(21,1,22（4）)()1()1(1,1,,jnjnimimjnjnimmnijDdBAw（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是距离项系数，其取值，一般算法是凭经验给出的。式中的第一项是行控制项，各行中只有一个“1”（一个城市只访问一次），第二项是列控制项，各列中只有一个“1”（一次只访问一个城市），第三项是距离项，是路径的全长。将式（4）和式（1）的各项对应，可导出其权值如式（5），阀值如式（6），同时定义符号式（7）:BAhij（6）jiifotherwiseij10（7）TSP能量函数曲面复杂，存在许多极小值，只靠减小能量是不可能求得全局最优解或满意解。4Hopfeild神经网络学习算法图1是学习算法的流程图。框I是用学习后的新参数（第一次用初始给出的参数值），使HNN在状态空间里进行状态更新至平衡状态，t是状态更新次数，被定义为时间。框II是网络到达平衡状态后，在参数空间里进行学习，s（离散值）是学习次数。为了简明起见，举一个只含二个极小值的HNN为例，说明其学习过程。图2是能量和状态管理科学与系统科学研究新进展——第6届全国青年管理科学与系统科学学术会议论文集2001年·大连5的关系，属概念性图示，横坐标表示状态，纵坐标表示与之对应的能量（为了便于理解，用一维表示）。网络的初始状态和所对应的能量可以被定义为“山岳地形”上的某一点，这个点在特定“山谷”的斜面上。在状态空间里，由HNN的收敛特性可知，随着HNN状态的更新，这个点将滑向谷底。如初始状态是图2（a）上的点A，随着HNN状态的更新，将向谷底滑去，最终陷入谷底B点（极小值）。(b)(d)图1学习算法的流程图图2含二个极小值HNN的学习过程HNN能量函数的形状是由各种参数值决定的。因此，对于一旦陷入极小值的点，在参数空间里，让参数向着使能量函数最速上升的方向学习。为此，用参数对能量函数进行微分，在它的最速上升方向（能量函数的微分系数更大的方向），即正的梯度方向上对参数进行修正，这里我们称之为最速上升法。下面就此作进一步阐述。首先，考虑一个含有许多参数的系统，把这些参数归纳起来用向量V表示，在参数空间里，V将按照式（8）进行学习，这里设ε是正的常数，V的修正量sV可以由式（9）求得，sssVVV1（8）)(ssVeV（9）▽e是e关于V的梯度。如果能使ε取得足够小，随着学习，能量函数e是上升的。因此，学习后上升了的B点，又成为“山谷”斜面上的一点B′。这时，在状态空间里，使HNN进行状态更新，点B′将向谷底C滑去，最后陷入谷底C点（图2（b））。如此使网络在状态空间和参数空间里，按照HNN的收敛特性及最速上升法，反复地进行状态更新、参数学习，HNN能量函数能够从陷入的极小值中逃脱出来，最终收敛于最优解或满意解（图2（d））。(a)(c)管理科学与系统科学研究新进展——第6届全国青年管理科学与系统科学学术会议论文集2001年·大连65基于Hopfield神经网络学习的TSP解法TSP能量函数式（4）中，A、B、D是决定约束条件权值大小的系数，并且在选择范围上有一定的自由度，可作为学习参数。因此，对应于式（9），A、B、D的修正量分别是)()(sAepsA（10）)()(sBeqsB（11）)()(sDersD（12）p、q、r是正常数，称学习系数。由式（4），可以导出能量函数关于学习参数A、B、D的偏微分21)1(21)(NiNjijNiNjNmNnmnijjnimyyysAe（13）21)1(21)(NiNjijNiNjNmNnmnijimjnyyysBe（14）NiNjNmNnjnjnmnijimyydsDe)(21)(1,1,（15）6仿真实验结果10城市的坐标被随机地配置在一个单位正方形内，设p=q=r=0.001，T=0.25，学习参数初始值A=B=1、D=2。在[0.000000,1.000000]范围内，随机产生100组不同的初始出发状态，其计算结果如图3所示。图中，非可行解、可行解及最优解分别用failure、feasible及optimum表示。由图可见，不学习的HNN（学习次数是0），failure、feasible、optimum的收敛率分别是23%、77%、0%。随着学习次数的增加，optimum的收敛率增高，学习23次后，100%的解收敛于optimum。图3随机给出100组不同初始值的计算结果图420城市TSP的最终解20城市的坐标被随机地配置在一个单位正方形内(图4)，设p=q=r=0.0002，T=0.2，A=B=10、D=14。yij的初始值，由[0.000000,1.000000]内的随机数随机地给出，计算结果如表1及图4所示，（表1中，s、t、e、d、r分别是学习次数、状态更新次数、能量、距离、访问路径）。管理科学与系统科学研究新进展——第6届全国青年管理科学与系统科学学术会议论文集2001年·大连7表120城市TSP的能量、距离、路径变化过程stedr(1)024-353.68316620.0272582,1,4,3,6,5,8,7,10,9,12,11,14,13,16,20,19,15,18,17,2(2)14414507.81892413.03765214,1,4,3,9,5,8,7,10,17,12,11,16,13,2,20,19,15,6,18,14(3)147149713.44795111.65109514,1,4,3,9,5,8,7,10,17,12,11,15,13,2,20,16,19,6,18,14(4)151173619.1934418.2773373,6,18,8,9,5,14,1,11,12,17,10,15,13,2,20,16,4,19,7,37结论(1)本文提出的学习算法，即把决定约束条件权值大小的系数作为学习参数，在参数空间里使参数向着HNN能量高速上升的方向学习，能够有效地使网络从极小值状态中逃脱出来，并能以很高的比率收敛于最优解。因此，本算法在最优化问题的应用方面将会比HNN更有效更广泛。(2)该学习算法并不局限于求解TSP，更适用于求解状态到达全局最优解时有明确定性特征的最优化问题。（3）因算法简明，可望易于硬件实现。参考文献1HopfieldJJ,TankDW.‘Neural’computationofdecisioninoptimizationproblems.Bio.Cybern.,1985,52:141-1522AckleyDH,HintonGE,SejnowskiTJ.AlearningalgorithmforBoltzmanMachines.CognitiveSci,1985,9:147-1693MurataJ,FuchikamiT,HirasawaK.Heuristicoptimizationusinglong,medium,andshorttermmemories.T.IEE,1998,118-C(9):1315-13214TangZ,JinHH,IshizukaO,etal.AninvestigationonauniquesolutionoftheHopfieldandtheT-modelneuralnetworks.T.IEE,1998,118-C(2):150-1605TangZ,JinHH,MuraoK,etal.AgradientascentlearningforHopfieldnetworks.T.IEICE,2000,J83-A(3):319-3316LawlerEL,LenstraJK,RinnooyAHG,etal.TheTravellingSalesmanProblem.Chichester:Wiley,e