基于Hopfield网络的TSP路径优化研究.pdf

《基于Hopfield网络的TSP路径优化研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第31卷第6期(下)赤峰学院学报(自然科学版)Vo1．3lNo．62015年6月JournalofChifengUniversity(NaturalScienceEdition)Jun．2015基于Hopfield网络的TSP路径优化研究王颖(哈尔滨远东理工学院，黑龙江哈尔滨150025)摘要：旅行商问题(TravelingSalesmanProblem，简称TSP)可以被描述为：一名推销员必须遍访N个城市，N个城市之间距离为已知．并且每个城市推销员只能访问一次，最后必须回到始发城市．怎样安排推销员在这些城市间的访问顺序，从而求解出他的最短旅行路线总长度．组合优化问题中的

2、一个典型就是旅行商问题，尤其是当N为很大数目时，计算量太大，常规方法无法完全进行求解．用常规方法和现有计算工具在繁杂的搜索空间中寻求最优解，实现起来存在着诸多的计算困难．为了解决计算困难这个问题，引入Hopfield网络的优化能力可以很轻松地解决这类问题．本文基于Hopfield网络求得经典组合优化问题(TSP)的最优解．开创了优化问题求解的新方法．关键词：旅行商问题(TSP)；Hopfield网络；优化中图分类号：TP393．01文献标识码：A文章编号：1673—260X(2015)06—0031—03组合优化问题中的一个典型就是旅行商问题(TsP)，其表1中是一个4X

3、4二维矩阵，矩阵中每行每列只有一可能的城市数目N和路径数目呈指数型增长，由于计算量个元素为1，其余均为0，否则路径是无效的．神经元(x，i)的太大，常规方法无法求解出最优解，所以针对旅行商问题输出用Vxi表示，神经元(x，i)的输入用Uxi表示．如果城市x(P)寻找有效的近似求解算法具有非常重要的理论意义．在i位置上被访问，则Vxi=l，否则Vxi=0．另外，现今可以将很多实际应用问题进行简化处理，处理后针对TSP问题，Hopfield宣言了如下形式的能量函数：的结果均可用旅行商问题(TSP)进行表示，因而对旅行商问E_-AEZV~v,+BZZZV~V～；题(P)求解方法

4、的研究具有重要的应用价值．NN一1求解TSP问题的Hopfield网络设计+孚(∑∑v一N)。、1ilTSP问题是在一个城市集合{A，B。，C⋯··}中找出一个最短路径，该路径必须经过并只经过每个城市一次，最终+_D_l∑∑∑d(。+v1)(1．1)回到起点的路径的方法．Hopfield采取了换位矩阵的表示方公式1．1中A，B，C，D是权值，d表示城市x到城市y法，从而将TSP问题映射为一个神经网络的动态过程，用之间的距离．1llN×N矩阵表示旅行商访问N个城市．I】例如，有四个城市公式1．1中，E的前三项用于约束问题，最后一项用于{A，B，C，D}，旅行商访问的路线是B

5、c_cAc__+DB，优化目标．E的第一项用于保证矩阵v的每一行1的个数则Ho胡eld网络输出所代表有效解用下面的二维矩阵表表>=0且<=1时E最小(即每个城市只去一次)，E的第二项1进行表示。保证矩阵v的每一列1的个数>：0且<：1时E最小(即每表1四个城市的访问路线次只访问一个城市)，E的第三项保证矩阵v中的1的个数恰好为N时E最小．在神经网络中引入Hopfield能量函数的概念，从而产生新的方法进行求解优化问题．但新方法在求解上仍然存在一些不足，如局部极小、不稳定等问题．为此，将TSP的能量一31—函数定义为：路径坐标为：E：AN)+耋一·)0．1O．1O．90．5

6、0．90．1+∑∑∑dv(1．2)x：1v=1i=10．450．9取式1．2，Hopfield网络的动态方程为：0．90．8=熹⋯(i耋V)0．7O．90．10．45N、N-A(，V·)-Dd-(1I)0．450．12采用Hopfield网络求解TSP问题的算法如果初始化的寻优路径有效，即路径矩阵中每行每列采用Hopfield网络求解TSP问题的算法描述如下：只有一个元素为1，其余均为O，则给出最后的优化路径，否(1股置初始值，t=0，A=I．5，D=I．0，=50；则停止优化，需要重新运行优化程序．如果本次寻优路径(2)计算N个城市之间的距离d(x，y=l，2，⋯，N)

7、；，有效，经过2000次迭代，最优能量函数为FinalE=1．4468，(3)在0附近设置神经网络输入Uxi(t)F~J初始化数值；初始路程为Initial_Length=4．1419，最终路程为Final_Length-(4)根据动态方程(1．3)计算}；-2．8937．仿真中取M=2时，对2O个城市的路径进行优化，城市(5)采用一阶欧拉法计算Uxi(t+1)路径坐标为：Uxi(t+1)=u菇(I)+dU~AT(1．4)dtO．10．1(6)~JT保证收敛于正确解，HP矩阵V每行每列只有一O．90．5个元素为1，其余为0，应