内容发布更新时间 : 2024/9/12 22:45:51星期一 下面是文章的全部内容请认真阅读。
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);