资源描述：
《hopfield网络求解tsp的一种改进算法和理论证明_孙守宇》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第l期电子学报Vl23119951ATAEJan年月IETRNIAOSINIAJ豢pfield网络求解THSo的一种改进算’法和理论证明AMdifiedOAglrithmandTheretiealAnalysisoofrfiedlNetrSlingvTSHoooo孙守宇郑君里清华大(学电子工程系北京100084”【提要】本文通过简化叩fiedl神经网络求解旅行商问题TS(的能H量函数提出了一种神、经网络求解TS的改进算法借助连接矩阵特征值的分析从理论上证明了该算法保证获得TS,,有效解的原因大量计算机模拟实验表明该算法明显优于目
2、前广泛应用的iAyer算法具有收敛.速度快、可避免无效解,易获得优化解等特点:,,关祖词H叩ifeld神经网络旅行商问题局部和全局最小Abstraet:TheTravellingSalesmanproblem(TSP)15studiedusingHopfieldneuralnetworkntsaer.neaor5roosesnene,(HNN)ihippAwlgithm1ppdbyimplifyigrgyfunetionandthefeasibilityofthealgorithm15analze.Theanasis15aseo
3、ntegeoetryotesuspaeesetupbytee-ydlybdhmfhbhdenerateeenvaue.-gdiglsoftheeonneetionmatrixAlargenumberofsimulationresultsshowthatthealgoritasteadvantageoavoidingmostaenergyminimawitteoptimuornear一optimuhmhhflcolhhmmsolutionandfastspeedofeonvergenee..,Keywords:Hopfieldne
4、uralnetwork(HNN)Travellingsalesmanproblem(TSP)Lalandcogloanimublmim飞己!封一、J.`二,自从Hopifeld等用神经网络求得NP问题的旅行商问题(TSP)优化解以来lj[人们对其评2,:价褒贬不Wilson认为H叩ifcld网络不能很好地求解TSP[〕与此相反iAye通过TSP网络一的动态分析TSP,..s[]修正了的能量函数从而获得有效解但其能量函数的表达式过于复杂相比之下,本文简化了这个能量函数,提出了一种基于H叩ifeld神经网络求解TSP的改进算法.、二
5、对Hopifeld网络求解TSP的两种不同评价H叩ifeld求解TSP时,用N义N个神经元素表示商人访问N个城市.例如有4城市A,,,.,:BCD访间路线是DACBD那么网络输出所代表的有效解可用下面的二维矩阵表示,,.用V刀表示神经元x(约的输出相应的输入用姚,表示如果城市x在i位置上访问,则V。1993年7月收到,1993年.国家自然科学基金资助项目n月定稿SunShouyu,ZhengJunlsnghuanversty,l一ing100084)i(TiUiiBe电子学报15年99,。,o:一1否则V一O因此Hpifeld定
6、义了如下形式的能量函数·A2二x,。,二,,2一ō艺乙艺v不+vv+(习艺v一)+己。E一早艺艺名早孕名名习,,,一1少一1少笋1`二~l夕一1y笋二,一1一乙x一1,二1乙工二ly一11~1x,.,V,,+,,1(V+V一)(l),.ùé1最后一项是优化目标项盆0C甘1,前三项是间题的约束项网络随机设置初始值.能量函数单调下降,E的最小BADC000l,点对应问题的优化解H叩ifeld报告表明在20次模拟实验00中,有16次收敛到最优解或接近最优化解.000,wilson用Hopfield求解Tsp的相同方法并不能达到Hopi
7、feld报告中所给出的结果.他在10次重复试验中,只有巧次能在1000次迭代计算以内,“”,收敛到有意义的巡回路径上45次被冻结在无意义的旅行路线上其它40次在1000次迭,代计算中不收敛,r从超空间的角度解释了iAye通过网络特征值的分析闭Hopifeld网络求解TSP时经常,:陷入无效解的原因并将式(l)表示的能量函数修改为.,,,.~A又,,又,,B,,,___,,,__。,__J又曰J刀,,“又J又“二,二:又J又“,C又飞“又J,n“一E一于2匕二或乙,一乙1V’刀V’`了+’于之,一之并二之VV’”+’一A““(乙
8、之V’呈二,+’于之之V’刀一)一忿节升2全二1节忿胃”置胃2置昌二,、,二,二,,、.卫二生)vv+、1、+1`鱼丝土旦艺艺习艺孕名乙乙v(v一+v)(2)刀z=1,~1夕=z少=1一乙J二1,~1少=l,.显然riAye所做的努力保证网络收敛到有效解是以复杂
