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