资源描述：
《现代计算方法—TSP问题的神经网络解法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、TSP的神经网络解法杨康一、问题概述1、TSP问题旅行商问题，即TSP问题（TravellingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。2、神经网络介绍人工神经网络（ArtificialNeuralNetworks，简写为ANNs）也简称为神经网络（NNs）或称作连接模型（ConnectionModel），它是一种模仿动物神经网络行为特征，进行分布式并行信息处
2、理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。神经网络起源于上世纪四、五十年代，经历60多年的发展取得了巨大成果。目前神经网络算法比较多，最基础的为BP、RBF、Hopfield等，基于这些算法的研究成果很多。针对实际问题和存在缺陷，国内外很多学者提出了相关的改进方法。本文采用Hopfield神经网络解决TSP问题。Hopfield网络最重要的贡献就是引入了Lyapunov稳定性定理，证明了网络在任意初始状态下都能渐近稳定，从而Hopfield网络可用于优化计算。二、解决方案根据TSP问题的基本要求，优化目标为：上式中的每
3、一项表示城市y在城市x之前或之后被访问时，dxy就应被计入总路程，因此上式是任意一个循环旅行的总路程。其中下标i对N取模运算，即当i=N+1时令i=1，从而保证旅行路线上的第N个城市与第一个城市相邻。如果把约束条件公式化，则分别为：上式可满足下列三个条件：（1）是置换矩阵在每行中只有至多一个元素的值为1，表示每城市不能最多只能访问一次；（2）置换矩阵每列至多只能有一个元素为1，即每次只能访问一个城市；（3）保证置换矩阵的每行每列均有且仅有一个元素的1。应用高数中处理约束的方法，即引入Lagrange函数，就可以把上述的约束优化问题转化为无约束优化问题求解，于是可采用如下的总目标函数：将
4、上式与能量函数相等，便可得到神经元之间的连结权值表达式：其中，，。能量函数为在仿真中，目标函数选为：其中，A=B（保证对称性）。神经元函数选为：三、仿真结果以中国各个省会为研究对象的TSP问题，采用Hopfield网络作为解决手段。参数选择如下：城市数N=31；系数A=B=1.5，D=1；神经元函数斜率u0=0.02；计算步长为0.1；最大迭代次数为2000。从运行结果看，并不是每次都能得到最后解，存在较多的无效解和非最优解，所以需要进行多次试验才能确定最后结果。在仿真前，首先对数据进行预处理，保证权值在合理范围内：将距离矩阵中的所有元素均除以2000。经过6次试验得到下列结果：表一、
5、距离参数序号距离/200018.73929.75938.49849.874558.47869.73从表中可以看出，在这6次试验中，最优解为8.478*2000=16956（公里）。由于置换矩阵较大，在此不再展示，这将在附件中《TSP-NewV矩阵》电子表格中展示。在最优解为16956公里的情况下，旅行商的路线为：西宁、兰州、银川、西安、长沙、武汉、南昌、合肥、南京、上海、杭州、台北、福州、广州、海口、南宁、昆明、贵阳、成都、郑州、太原、石家庄、济南、北京、天津、沈阳、哈尔滨、长春、呼和浩特、乌鲁木齐、拉萨，最后再回到西宁。四、源程序N=31;A=1.5;D=1;u0=0.02;Step
6、_t=0.1;MaxEpochs=2000;%CityCood=rand(2,N);DistanceMat=CTSR31S1/2000;%dist(CityCood',CityCood);U=0.2*rand(N,N)-0.1;forCount=1:MaxEpochsV=(1+tansig(U/u0))/2;E=CacuEnergy(V,DistanceMat,A,D)delta_U=CacuDeltaU(V,DistanceMat,A,D,Step_t);U=U+delta_U*Step_t;end[NewV,CheckRes]=RouteCheck(V);if(CheckRes<1
7、)FinalE=CacuEnergy(NewV,DistanceMat,A,D)%RouteLen=TotalRouteLength(NewV,CityCood)RouteLen1=TotalRouteLength1(NewV,DistanceMat)%PlotRoute(NewV,CityCood);elsedisp('路径无效¡'),end%能量计算functionE=CacuEnergy(V,d,A,D)[n,n]=size(V);t1=
