利用Hopfield神经网络求解旅行商问题研究

Hopfield神经网络在TSP问题中的应用的开题报告1.研究背景旅行商问题(TSP)是运筹学中的经典问题，它是要找到一条经过所有城市(节点)的路径，使得路径经过的距离最短。

由于该问题是NP难问题，因此解决TSP问题一直是一个热门研究领域。

Hopfield神经网络作为一种反向传播神经网络模型，已经在很多问题中得到了应用，包括TSP问题。

Hopfield神经网络可以使用能量函数描述问题，利用机器学习技术学习问题的解，自适应地调整神经元之间的连接权值，从而达到解决TSP问题的目的。

2.研究意义研究Hopfield神经网络在TSP问题中的应用，可以为人们提供一种新的解决TSP 问题的方法。

Hopfield神经网络的优点是可以处理非线性问题，因此在解决TSP问题这种复杂的非线性问题时非常有效。

通过研究Hopfield神经网络在TSP问题中的应用，可以提高解决TSP问题的效率和精度，为一些实际问题提供有效的解决方案。

同时，这种研究也会推动神经网络领域的发展。

3.研究目标本研究的目标是探讨Hopfield神经网络在TSP问题中的应用，并提出一种有效的Hopfield神经网络解决TSP问题的方法。

具体目标如下：(1)研究Hopfield神经网络原理，并深入了解其在TSP问题中的特点和应用。

(2)分析TSP问题的性质和解决方法，并与Hopfield神经网络相结合，提出一种有效的解决方案。

(3)设计和实现算法，并对算法进行测试和优化。

(4)使用实验数据对算法进行验证和评估，分析算法的优缺点和适用范围。

4.研究方法本研究将采用以下几种方法：(1)文献调研法：通过查阅相关文献，研究Hopfield神经网络在TSP问题中的应用，并了解近年来该领域的研究进展。

(2)模型建立法：根据TSP问题的相关性质，结合Hopfield神经网络的原理，提出一种新的解决方案。

(3)实验方法：通过编写代码实现算法，并使用TSP问题数据进行测试和验证，对算法效率和精度进行评估，并进行优化。

旅行商问题（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ，简称ＴＳＰ）是一个著名的组合优化问题：给定ｎ个城市，有一个旅行商从某一城市出发，访问每个城市各一次后再回到原出发城市，要求找出的巡回路径最短。

如果用图论来描述，那就是已知带权图Ｇ＝（Ｃ，Ｌ），寻出总权值最小的Ｈａｍｉｌｔｏｎ圈。

其中Ｃ＝｛ｃ１，ｃ２，…，ｃｎ｝表示ｎ个城市的集合，Ｌ＝｛ｌｉｊ｜ｃｉ，ｃｊ∈Ｃ｝是集合Ｃ中元素（城市）两两连接的集合，每一条边ｌｉｊ，都存在与之对应的权值ｄｉｊ，实际应用中ｄｉｊ可以表示距离、费用、时间、油量等。

ＴＳＰ的描述虽然简单，解决起来却很困难。

最简单思路是用穷举法把所有可能的巡回路径全部列出来，最短的一个就是最优解，但这样只能处理很小规模的问题。

旅行商问题属于ＮＰ－ｃｏｍｐｌｅｔｅ问题，是ＮＰ（ｎｏｎ－ｄｅｔｅｒｍｉｎｉｓｔｉｃｐｏｌｙ－ｎｏｍｉｎａｌ）问题中最难的一类，不能在多项式时间内求解。

如果有ｎ座城市，那么巡游路径共有（ｎ－１）！／２条，计算的时间和（ｎ－１）！成正比。

当城市数ｎ＝２０，巡回路径有１．２×１０１８种，ｎ＝１００，巡回路径就有多达４．６×１０１５５种，而据估计宇宙中基本粒子数“仅仅只有”１０８７个。

尽管如此，随着算法研究的逐步深入和计算机技术飞速提高，对ＴＳＰ问题的研究不断取得进展。

７０年来，被征服的ＴＳＰ规模从几十个城市增加到上万个城市。

目前的最高记录是在２００４年５月，找到的巡游瑞典２４９７８个城镇的最优路径（ｓｗ２４９７８），花费了８４．８个ＣＰＵ年。

图１展示了ＴＳＰ的研究进展，最近的二三十年时间里，被攻克的ＴＳＰ规模高速增长，差不多是每十年增加一个数量级。

照这样发展下去的话，再过２０年就能解决上百万个城市的ＴＳＰ，有专家甚至已经为此准备好了数据：全球１９０，４７１１个城市的坐标。

当然，能不能达到这个目标，有赖于未来计算技术的发展。

图１ＴＳＰ的发展字母后面的数字表示城市数，“ｓｗ２４９７８”就是瑞典的２４９７８个城镇。

3我的页脚Hopfield 网络学习及其在最优化问题中的应用金海和*（清华大学经济管理学院，北京 100084）摘要 本文针对Hopfield 神经网络（HNN ）所存在的极小值问题及缺乏学习能力的问题，提出了一种学习算法。

它是将决定约束条件权值大小的系数作为学习参数，在参数空间里使参数向着HNN 能量上升最快的方向学习，使网络状态能够有效地从一旦陷入的极小值状态中逃脱出来。

该算法分别被应用于10、20城市的旅行商问题（TSP ），结果能够以很高的比率收敛于最优解。

关键词 Hopfield 神经网络 最速上升法 参数学习 最优化问题1 引言Hopfield 等通过用连续值HNN 求解TSP ，开辟了运用神经网络求解最优化问题的新途径[1]。

但存在着（1）不能学习、（2）产生大量极小值等问题。

作为解决极小值问题的方法之一，Hinton 等提出了Boltzmann 机模型及其学习算法[2]，但因速度太慢，难以为现实所接受[3]。

对于问题（2），笔者进行过深入的理论分析，并在数学上进行了证明[4]。

针对问题（1）、（2），笔者提出了登山学习算法[5]，但该算法中，为了避免因学习使最小值发生位移，以学习后的解为初始解，使网络回到未学习的HNN 状态空间里进行状态更新至平衡状态，显然增加了计算量。

TSP 常被用作研究最优化问题的范例[6]，当运用HNN 求解时，它的解依从于决定约束条件权值大小的系数，而这类系数在选择上具有一定的自由度。

本文提出一种HNN 学习算法，思想是，将决定约束条件权值大小的系数作为学习参数，在参数空间里使学习参数向着HNN 能量上升最快的方向学习，使HNN 能从一旦陷入的极小值状态中逃脱出来，直至找到最优解或满意解。

本文将对N =10、20的TSP 进行仿真实验，以证明其有效性。

2 Hopfield 神经网络模型HNN 是由大量简单的神经处理单元相互结合而成，并有对称性，无直接自反馈，非同期动作等约束。

Hopfield神经网络求解TSP问题1.什么是TSP问题旅行商问题，即TSP问题（Traveling Salesman Problem），也是最优化问题。

一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。

路径的选择目标是要求得的路径路程为所有路径之中的最小值。

用数学语言描述TSP如下 :设有限个城市集合 : C = { C1 , C 2 , … , Cn }，每两个城市间的距离为 d（Ci，Cj）∈Z, 其中 Ci，Cj∈C（ 1<=i , j <=n), 即求 minL=∑d（Ci，Cj）的值的问题。

有效路径的方案数目为Rn=（（n-1）！/2）,例如:R4=3,R5=12,R6=120,R10=181440可见路径总数，随n增大而急剧增长,当城市数目增加到一定的程度,计算量增加到无法进行的地步，所以要选择一种合理快速的算法，而不能对所有情况使用人工列举的方法。

2.Hopfield神经网络介绍人工神经网络（Artificial Neural Networks，简写为ANNs）也简称为神经网络（NNs）或称作连接模型（Connection Model），它是一种模仿动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。

这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的.最基础的为BP、Hopfield网络等。

Hopfield网络是一种互连型网络的一种，它引入类似于Lyapunov 函数的能量函数概念，把神经网络的拓扑结构(用连接权矩阵表示)与所求问题(用目标函数描述)相对应，并将其转换为神经网动力学系统的演化问题。

3.神经元的数学模型人的大脑是由大量神经细胞或神经元组成的。

每个神经元可以看作为一个小的处理单元，这些神经元按照某种方式相互连接起来，构成大脑内部的生理神经元网络系统，他们中各个神经元之间连接的强弱不是固定不变的，而是按照外部的信号激励程度做自适应的变化，而每个神经元又随着接收到的多个激励信号的综合大小呈现兴奋或抑制状态。

案例背景：
利用神经网络解决组合优化问题是神经网络应用的一个重要方面。

所谓组合优化问题，就是在给定约束条件下，使目标函数极小（或极大）的变量组合问题。

将Hopfield网络应用于求解组合优化问题，把目标函数转化为网络的能量函数，把问题的变量对应到网络的状态，这样，当网络的能量函数收敛于极小值时，问题的最优解也随之求出。

由于神经网络是并行计算的，其计算量不随维数的增加而发生指数性“爆炸”，因而对于优化问题的高速计算特别有效。

[ 以下有详细的Hopfield网络理论知识..........]
问题描述：
TSP问题，即所谓的旅行商问题（Traveling Salesman Problem）。

问题的提法是：在N个城市中各经历一次后回到出发点，使所经过的路程最短。

不考虑方向性和周期性，在给定N 的条件下，可能存在的闭合路径数目为1/2(N-1)!。

当N较大时，枚举法的计算量之大难以想象。

将Hopfield网络用于求解该问题，效果非常显著。

模型建立：
该处有完整的数学理论推导过程....
Matlab程序实现：
该处有完整的Matlab程序代码，以及代码的详细说明
* 清空环境变量、定义全局变量
* 导入城市位置
* 初始化网络
* 计算相互城市间距离
* 寻优迭代
* 检查路径合法性
* 结果绘图
* 绘制能量函数变化过程
结果分析：
该处有详细的运行结果。

HopField 神经网络解决旅行商问题实验名称：用Hopfield 神经网络解决旅行商(TSP)问题实验内容：旅行商问题（TravellingSalesman Problem, 简记TSP ，亦称货郎担问题)：设有n 个城市和距离矩阵D=[dij]，其中dij 表示城市i 到城市j 的距离，i ，j=1，2 …n ，则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短。

TSP 的一个解可表述为一个循环排列，假如有５个城市ABCD Ｅ顺序为如有５个城市顺序为Ｃ→A →Ｅ→Ｂ→Ｄ→Ｃ。

那么路线总长度为：D C BD EB AE CA d d d d d d ++++=TSP 问题综合了一大类组合优化问题的典型特征，属于NP 完全问题，不能在多项式时间内进行检验。

若使用动态规划的方法时间复杂性和空间复杂性都保持为n 的指数函数。

HNN 方法是解TSP 问题的另一种有效的方法，在城市数目比较小的情况下可以在较短的时间得到满意的结果。

算法分析：所用到的基本理论与方法，具体算法。

1.根据文献（1），HNN 解TSP 问题的具体步骤为：0、置t=0,A=1.5,D=1;1、读入N 城市之间的距离),,2,1,(n y x d xy =文件；2、计算神经元之间的权重和输入偏置 权重：n j i y x Dd A A T i j xy ij xy YjXi ,2,1,,,,1,,=---=-其中δδδ输入偏置： I=2A;3、)(t U xi 的初值在0附近随机产生（x,i=1,2,……，N ）;4、计算))/)(tanh(1(21)(0U t U t V xi xi +=， 这里2.00=U 5、利用神经元动态方程，计算∑∑==+=∆n y nj yj yjxi xi I V Tt u 11,)(6利用一阶尤拉法计算 ,5.0)()1()1(=∆∆⨯∆++=+t t t u t U t U xi xi xi ，这里7、如果系统达到平衡状态，那么终止程序，否则返回第4步。

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。

%% 连续Hopfield神经网络的优化—旅行商问题优化计算% function main%% 清空环境变量、定义全局变量clear allclcglobal A D%% 导入城市位置load city_location%% 计算相互城市间距离distance=dist(citys,citys');%% 初始化网络N=size(citys,1);A=200;D=100;U0=0.1;step=0.0001;delta=2*rand(N,N)-1;U=U0*log(N-1)+delta;V=(1+tansig(U/U0))/2;iter_num=10000;E=zeros(1,iter_num);%% 寻优迭代for k=1:iter_num% 动态方程计算dU=diff_u(V,distance);% 输入神经元状态更新U=U+dU*step;% 输出神经元状态更新V=(1+tansig(U/U0))/2;% 能量函数计算e=energy(V,distance);E(k)=e;end%% 判断路径有效性[rows,cols]=size(V);V1=zeros(rows,cols);[V_max,V_ind]=max(V);for j=1:colsV1(V_ind(j),j)=1;endC=sum(V1,1);R=sum(V1,2);flag=isequal(C,ones(1,N)) & isequal(R',ones(1,N));%% 结果显示% 计算初始路径长度sort_rand=randperm(N);citys_rand=citys(sort_rand,:);Length_init=dist(citys_rand(1,:),citys_rand(end,:)');for i=2:size(citys_rand,1)Length_init=Length_init+dist(citys_rand(i-1,:),citys_rand(i,:)');end% 绘制初始路径figure(1)plot([citys_rand(:,1);citys_rand(1,1)],[citys_rand(:,2);citys_rand(1,2)],'o-') for i=1:length(citys)text(citys(i,1),citys(i,2),[' ' num2str(i)])endtext(citys_rand(1,1),citys_rand(1,2),[' 起点' ])text(citys_rand(end,1),citys_rand(end,2),[' 终点' ])title(['优化前路径(长度：' num2str(Length_init) ')'])axis([0 1 0 1])grid onxlabel('城市位置横坐标')ylabel('城市位置纵坐标')% 计算最优路径长度[V1_max,V1_ind]=max(V1);citys_end=citys(V1_ind,:);Length_end=dist(citys_end(1,:),citys_end(end,:)');for i=2:size(citys_end,1)Length_end=Length_end+dist(citys_end(i-1,:),citys_end(i,:)');enddisp('最优路径矩阵');V1% 绘制最优路径figure(2)plot([citys_end(:,1);citys_end(1,1)],...[citys_end(:,2);citys_end(1,2)],'o-')for i=1:length(citys)text(citys(i,1),citys(i,2),[' ' num2str(i)])endtext(citys_end(1,1),citys_end(1,2),[' 起点' ])text(citys_end(end,1),citys_end(end,2),[' 终点' ])title(['优化后路径(长度：' num2str(Length_end) ')'])axis([0 1 0 1])grid onxlabel('城市位置横坐标')ylabel('城市位置纵坐标')% 绘制能量函数变化曲线plot(1:iter_num,E);ylim([0 2000])title(['能量函数变化曲线(最优能量：' num2str(E(end)) ')']);xlabel('迭代次数');ylabel('能量函数');elsedisp('寻优路径无效');end% %===========================================% function du=diff_u(V,d)% global A D% n=size(V,1);% sum_x=repmat(sum(V,2)-1,1,n);% sum_i=repmat(sum(V,1)-1,n,1);% V_temp=V(:,2:n);% V_temp=[V_temp V(:,1)];% sum_d=d*V_temp;% du=-A*sum_x-A*sum_i-D*sum_d;% %==========================================% function E=energy(V,d)% global A D% n=size(V,1);% sum_x=sumsqr(sum(V,2)-1);% sum_i=sumsqr(sum(V,1)-1);% V_temp=V(:,2:n);% V_temp=[V_temp V(:,1)];% sum_d=d*V_temp;% sum_d=sum(sum(V.*sum_d));% E=0.5*(A*sum_x+A*sum_i+D*sum_d);% % % % 计算dufunction du=diff_u(V,d)global A Dn=size(V,1);sum_x=repmat(sum(V,2)-1,1,n);sum_i=repmat(sum(V,1)-1,n,1);V_temp=V(:,2:n);V_temp=[V_temp V(:,1)];sum_d=d*V_temp;du=-A*sum_x-A*sum_i-D*sum_d;% % % % % 计算能量函数function E=energy(V,d)global A Dn=size(V,1);sum_x=sumsqr(sum(V,2)-1);sum_i=sumsqr(sum(V,1)-1);V_temp=V(:,2:n);V_temp=[V_temp V(:,1)];sum_d=d*V_temp;sum_d=sum(sum(V.*sum_d));E=0.5*(A*sum_x+A*sum_i+D*sum_d);。

人工神经网络实验二用CHNN 算法求解TSP 问题一． 问题描述利用连续型Hopfield 反馈网络求解10城市的旅行商（TSP ）问题。

其中10个城市的坐标给定如下：1(0.4000,0.4439),2(0.2439,0.1463),3(0.1707,0.2293),4(0.2293,0.7610),5(0.5171,0.9414),6(0.8732,0.6536),7(0.6878,0.5219),8(0.8488,0.3609),9(0.6683,0.2536),city city city city city city city city city ci =========10(0.6195,0.2634)ty =基本网络参数为：0500,200,0.02A B D C μ=====二． 算法实现1．CHNN 算法应用CHNN 网络解决优化问题一般需要以下步骤：(1.)对于特定的问题，要选择一种合适的表示方法，使得神经网络的输出与问题的解相对应。

(2.)构造网络的能量函数，使其最小值对应于问题的最佳解。

(3.)将能量函数与CHNN 算法标准形式相比较，推出神经网络权值与偏流表达式。

(4.)推出网络状态更新公式，并利用更新公式迭代求问题的最优解。

2．TSP 问题为使用CHNN 网络进行TSP 问题的求解，根据上述步骤，可将问题转化为： (1.)对N 个城市的TSP 问题，用一个N N ⨯的换位阵描述旅行路线，换位阵中每行每列有且只有一个元素为1，其余全为0。

为1的元素其横坐标x 表示城市名，纵坐标i 表示该城市在访问路线中的位置。

(2.)网络的能量函数由四部分组成，分别用来保证换位阵的合法性以及最终路线长度的最短。

2,1,1()()2222xi xj xi yi xi xy xi y i y i x i j i i x y x x i x i y xA B C D E v v v v v n d v v v +-≠≠≠=++-++∑∑∑∑∑∑∑∑∑∑∑(3.)将能量函数与标准形式相比较，得到网络权值与偏流表达式为：,,1,1(1)(1)()xi yj xy ij ij xy xy j i j i xiW A B C Dd I C n δδδδδδ+-=------+⎧⎪⎨=⋅⎪⎩ (4.)从而，网络更新公式为：,1,10()()1()[1tanh(/)]2xixi xj yi xi xy y i y i j i y x x i y xxi xi xi du u A v B v C v n D d v v dt v g u u u τ+-≠≠≠⎧=------+⎪⎪⎨⎪==⋅+⎪⎩∑∑∑∑∑3． 程序设计根据上述推导在MATLAB 中设计CHNN 网络求解TSP 问题的程序（程序代码见附页）。