金海* 金海 1964年生 博士研究方 理科学工程智优化 信息技术 Email jinhh@emtsinghuaeducn
(清华学济理学院北京 100084)
摘 文针Hopfield神网络(HNN)存极值问题缺乏学力问题提出种学算法决定约束条件权值系数作学参数参数空间里参数着HNN量升快方学网络状态够效旦陷入极值状态中逃脱出该算法分应1020城市旅行商问题(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旦陷入极值状态中逃脱出直找优解满意解文N1020TSP进行仿真实验证明效性
2 Hopfield神网络模型
HNN量简单神处理单元相互结合成称性直接反馈非期动作等约束n单元构成HNN量函数表达
(1)
e量身时间函数wij单元ij权值yi第i单元输出hi第i 单元阀值τ正常数单元部电压时间变化微分方程式(2)记述xi第i单元输入总单元输入输出采sigmoid形逻辑非线性单调增加函数式(3)
(2) (3)
T神单元输入输出函数形状影响参数
HNN收敛特性(证明见[7])适初始条件反复更新状态量时间单调减状态衡状态方更新量减全局局部时状态稳定某衡状态
3 基Hopfield神网络TSP解法
设N城市集合{C1C2…CN}中意两城市CiCk间距离dik(dikdki)试找出条短城市次(仅次)回出发路径TSPN城市TSPHNN求解时需N2神单元行代表城市号码列代表访问次序号码矩阵表示量函数写成式(4)
(4) (5)
yij神单元状态变量表示第i城市第j回否访问yij∈[01]yij≥05时yij发火意义第i城市第j回访问yij〈05时yij发火意义第i城市第j回访问dik城市i城市k间距离AB控制项系数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)
▽ee关梯度果ε取足够着学量函数e升
学升B点成山谷斜面点B′时状态空间里HNN进行状态更新点B′谷底C滑陷入谷底C点(图2(b))网络状态空间参数空间里HNN收敛特性速升法反复进行状态更新参数学HNN量函数够陷入极值中逃脱出终收敛优解满意解(图2(d))
5 基Hopfield 神网络学TSP解法
TSP量函数式(4)中ABD决定约束条件权值系数选择范围定度作学参数应式(9)ABD修正量分
(10) (11) (12)
pqr正常数称学系数式(4)导出量函数关学参数ABD偏微分
(13)
(14)
(15)
6 仿真实验结果
10城市坐标机配置单位正方形设pqr0001T025学参数初始值AB1D2[00000001000000]范围机产生100组初始出发状态计算结果图3示图中非行解行解优解分failurefeasibleoptimum表示图见学HNN(学次数0)failurefeasibleoptimum收敛率分23770着学次数增加optimum收敛率增高学23次100解收敛optimum
图3 机出100组初始值计算结果 图4 20城市TSP终解
20城市坐标机配置单位正方形(图4)设pqr00002T02AB10D14yij初始值[00000001000000]机数机出计算结果表1图4示(表1中stedr分学次数状态更新次数量距离访问路径)
表1 20城市TSP量距离路径变化程
s t e d r
(1) 0 24 353683166 20027258 214365871091211141316 20191518172
(2) 144 1450 7818924 13037652 14143958710 17121116132 20191561814
(3) 147 1497 13447951 11651095 14143958710 17121115132 20161961814
(4) 151 1736 19193441 8277337 3618895141 111217101513 2201641973
7 结
(1) 文提出学算法决定约束条件权值系数作学参数参数空间里参数着HNN量高速升方学够效网络极值状态中逃脱出高率收敛优解算法优化问题应方面会HNN更效更广泛
(2) 该学算法局限求解TSP更适求解状态达全局优解时明确定性特征优化问题
(3)算法简明易硬件实现
参考文献
1 Hopfield J J Tank D W Neural’ computation of decision in optimization problems Bio Cybern 1985 52 141152
2 Ackley D H Hinton G E Sejnowski T J A learning algorithm for Boltzman Machines Cognitive Sci 1985 9 147169
3 Murata J Fuchikami T Hirasawa K Heuristic optimization using long medium and short term memories TIEE 1998 118 C (9) 13151321
4 Tang Z Jin H H Ishizuka O et al An investigation on a unique solution of the Hopfield and the Tmodel neural networks TIEE 1998 118C (2) 150160
5 Tang Z Jin H H Murao K et al A gradient ascent learning for Hopfield networks TIEICE 2000 J83A (3) 319331
6 Lawler E L Lenstra J K Rinnooy A H G et al The Travelling Salesman Problem Chichester Wiley eds 1985
7 Hopfield J J Neurons with graded response have collective computational properties like those of twostate neurons Proc of the Natl Acad of Sci USA 1984 81 30883092
Hopfield Network Learning and Its Application in Optimization Problems
Jin Haihe
(School of Economics and Management Tsinghua University Beijing 100084 China)
Abstract This paper proposes a learning algorithm of solving the local minimum problem and the unlearnable 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 10city and 20city traveling salesman problems respectively As a result the network can converge in global minimum with higher percentage
Key words Hopfield Neural Networks Gradient Ascent Method Parameter Learning Optimization Problems
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
该内容是文档的文本内容,更好的格式请下载文档