公文写作_写作培训资材大全265

Hopfield网络学习及其在最优化问题中的应用金海和* 金海和, 1964年生, 博士后。主要研究方向: 管理科学与工程,智能优化, 信息技术, Email: （清华大学经济管理学院，北京 ）摘要 本文针对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进行仿真实验，以证明其有效性。2 Hopfield神经网络模型 HNN是由大量简单的神经处理单元相互结合而成，并有对称性，无直接自反馈，非同期动作等约束。由n个单元构成的HNN，其能量函数可表达为 (1) e是能量，其自身是时间的函数；wij是单元i和j的权值；yi是第i个单元的输出；hi是第i 个单元的阀值；是正的常数。各个单元内部电压随时间的变化可以用微分方程式（2）记述，xi是第i个单元的输入总和。单元的输入输出可采用sigmoid形的逻辑非线性单调增加函数，如式（3）。 （2） （3）T是一个对神经单元输入输出函数的形状有影响的参数。HNN有收敛特性(证明见7)，即在适当的初始条件下反复使其更新状态，则能量随时间单调地减小，状态向平衡状态的方向更新。能量减至全局最小或局部最小时，状态稳定在某个平衡状态。 3 基于Hopfield神经网络的TSP解法设有N个城市的集合C1，C2，CN，其中任意两个城市Ci和Ck之间的距离是dik（dik=dki），试找出一条最短的经过每个城市各一次（仅一次）并回到出发地的路径，这就是TSP。N个城市的TSP，用HNN求解时，需要用N2个神经单元。可以由一个行代表城市号码，列代表访问次序号码的矩阵来表示。其能量函数可以写成式（4）。 （4） （5）yij是神经单元的状态变量，表示第i个城市第j回是否访问，且yij0，1。当yij0.5时，yij发火，意义是第i个城市在第j回被访问；当yij0.5时，yij不发火，意义是第i个城市在第j回不被访问。dik是城市i与城市k之间的距离。A，B是控制项系数，D是距离项系数，其取值，一般算法是凭经验给出的。式中的第一项是行控制项，各行中只有一个“1”（一个城市只访问一次），第二项是列控制项，各列中只有一个“1”（一次只访问一个城市），第三项是距离项，是路径的全长。将式（4）和式（1）的各项对应，可导出其权值如式（5），阀值如式（6），同时定义符号式（7）: （6） （7） TSP能量函数曲面复杂，存在许多极小值，只靠减小能量是不可能求得全局最优解或满意解。4 Hopfeild神经网络学习算法图1是学习算法的流程图。框I是用学习后的新参数（第一次用初始给出的参数值），使HNN在状态空间里进行状态更新至平衡状态，t是状态更新次数，被定义为时间。框II是网络到达平衡状态后，在参数空间里进行学习，s（离散值）是学习次数。 为了简明起见，举一个只含二个极小值的HNN为例，说明其学习过程。图2是能量和状态的关系，属概念性图示，横坐标表示状态，纵坐标表示与之对应的能量（为了便于理解，用一维表示）。网络的初始状态和所对应的能量可以被定义为“山岳地形”上的某一点，这个点在特定“山谷”的斜面上。在状态空间里，由HNN的收敛特性可知，随着HNN状态的更新，这个点将滑向谷底。如初始状态是图2（a）上的点A，随着HNN状态的更新，将向谷底滑去，最终陷入谷底B点（极小值）。(c)(a) (b) (d)图1 学习算法的流程图 图2 含二个极小值HNN的学习过程HNN能量函数的形状是由各种参数值决定的。因此，对于一旦陷入极小值的点，在参数空间里，让参数向着使能量函数最速上升的方向学习。为此，用参数对能量函数进行微分，在它的最速上升方向（能量函数的微分系数更大的方向），即正的梯度方向上对参数进行修正，这里我们称之为最速上升法。下面就此作进一步阐述。首先，考虑一个含有许多参数的系统，把这些参数归纳起来用向量表示，在参数空间里，将按照式（8）进行学习，这里设是正的常数，的修正量可以由式（9）求得， （8） （9） e是e关于的梯度。如果能使取得足够小，随着学习，能量函数e是上升的。因此，学习后上升了的B点，又成为“山谷”斜面上的一点B。这时，在状态空间里，使HNN进行状态更新，点B将向谷底C滑去，最后陷入谷底C点（图2（b）。如此使网络在状态空间和参数空间里，按照HNN的收敛特性及最速上升法，反复地进行状态更新、参数学习，HNN能量函数能够从陷入的极小值中逃脱出来，最终收敛于最优解或满意解（图2（d）。5 基于Hopfield 神经网络学习的TSP解法TSP能量函数式（4）中，A、B、D是决定约束条件权值大小的系数，并且在选择范围上有一定的自由度，可作为学习参数。因此，对应于式（9），A、B、D的修正量分别是 （10） （11） （12） p、q、r是正常数，称学习系数。由式（4），可以导出能量函数关于学习参数A、B、D的偏微分 （13） （14） （15）6 仿真实验结果 10城市的坐标被随机地配置在一个单位正方形内，设p=q=r=0.001，T=0.25，学习参数初始值A=B=1、D=2。在0.,1.范围内，随机产生100组不同的初始出发状态，其计算结果如图3所示。图中，非可行解、可行解及最优解分别用failure、feasible及optimum表示。由图可见，不学习的HNN（学习次数是0），failure、feasible、optimum的收敛率分别是23%、77%、0%。随着学习次数的增加，optimum的收敛率增高，学习23次后，100%的解收敛于optimum。 图3 随机给出100组不同初始值的计算结果 图4 20城市TSP的最终解 20城市的坐标被随机地配置在一个单位正方形内(图4)，设p=q=r=0.0002，T=0.2，A=B=10、D=14。yij的初始值，由0.,1.内的随机数随机地给出，计算结果如表1及图4所示，（表1中，s、t、e、d、r分别是学习次数、状态更新次数、能量、距离、访问路径）。 表1 20城市TSP的能量、距离、路径变化过程 s t e d r (1) 0 24 -353. 20. 2,1,4,3,6,5,8,7,10,9,12,11,14,13,16, 20,19,15,18,17,2(2) 144 1450 7. 13. 14,1,4,3,9,5,8,7,10, 17,12,11,16,13,2, 20,19,15,6,18,14(3) 147 1497 13. 11. 14,1,4,3,9,5,8,7,10, 17,12,11,15,13,2, 20,16,19,6,18,14(4) 151 1736 19. 8. 3,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）因算法简明，可望易于硬件实现。 参考文献1 Hopfield J J, Tank D W. Neural computation of decision in optimization problems. Bio. Cybern., 1985, 52: 141-152 2 Ackley D H, Hinton G E, Sejnowski T J. A learning algorithm for Boltzman Machines. Cognitive Sci, 1985, 9: 147-1693 Murata J, Fuchikami T, Hirasawa K. Heuristic optimization using long, medium, and short term memories. T.IEE, 1998, 118- C (9): 1315-13214 Tang Z, Jin H H, Ishizuka O, et al. An investigation on a unique solution of the Hopfield and the T-model neural networks. T.IEE, 1998, 118-C (2): 150-160 5 Tang Z, Jin H H, Murao K, et al. A gradient ascent learning for Hopfield networks. T.IEICE, 2000, J83-A (3): 319-3316 Lawler E L, Lenstra J K, Rinnooy A H G, et al. The Travelling Salesman Problem. Chichester: Wiley, eds, 19857 Hopfield J J. Neurons with graded response have collective computational properties like those of two-state neurons. Proc. of the Natl. Acad. of Sci., USA, 1984, 81: 3088-3092Hopfield Network Learning and Its Application in Optimization ProblemsJin Haihe(School of Economics and Management, Tsinghua University, Beijing , China)Abstract This paper proposes a learning algorithm of solving the local minimum problem and the un-learnable problem for the Hopfield neural networks. The learning algorithm defines the coefficients of deciding constraint weight degrees as the learning parameters, and increases the energy of the Hopfield network by modifying its learning parameters in parameter space, thus making the network escape from the local minimum which the network once falls into. This learning algorithm is applied to 10-city and 20-city traveling sale