hopfield网络求解TSP问题.doc

Hopfield神经网络求解TSP问题 1. 什么是TSP问题？ 旅行商问题，即TSP问题（Traveling Salesman Problem），也是最优化问题。一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要 回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 用数学语言描述TSP如下 :设有限个城市集合 : C = C1 , C 2 , , Cn ，每两个城市间的距离为 d（Ci，Cj）Z, 其中 Ci，CjC（ 1=i , j 0为常数。保证当矩阵V的每一行不多于一个1时，达到最小=0。 ，其中B0为常数。保证当矩阵V的每一列不多于一个l时，达到最小=0。 ，其中C0为常数。保证当矩阵V中的1的个数恰好为n时，即整个矩阵有n个1时，达到最小=0。 ，实际数值就是一次有效路径总长度的倍数。若路径为最佳时，达到最小点。9. Hopfield神经网络状态方程将约束条件能量函数E和神经网络电路标准能量函数公式对比，并化简后得：其中为神经元的时空综合输入, 为其对应的神经元的输出10.Matlab实现与仿真结果实验一：10个城市的归一化坐标： （0.7788 0.5181） （0.4235 0.9436） （0.0908 0.6377） （0.2665 0.9577） （0.1537 0.2407） （0.2810 0.6761） （0.4401 0.2891） （0.5271 0.6718） （0.4574 0.6951）（0.8754 0.0680）k=1:1:5000（迭代次数）;A=B=D=500,C=200;u0=0.02（初始条件）;step=0.01;N=10(10个城市) TSP_hopfield迭代次数k = 5000寻优路径矩阵：V1 = 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0优化路径L=C6-C9-C8-C1-C10-C7-C5-C3-C4-C2-C6最优能量函数：Final_E = 1.5063初始路程：Initial_Length = 4.1888最短路程：Final_Length =3.0126迭代次数对能量函数的影响能量函数随着迭代次数的增加而减小，最后达到极小稳定值，而在迭代开始的时候优化约束条件能量函数迅速下降，说明神经网络对于解决TSP的有效性。实验二改变u0=0.03，其他的都变TSP_hopfield迭代次数k = 5000寻优路径矩阵：V1 = 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0优化路径L=C4-C6-C3-C5-C7-C10-C1-C8-C9-C-C4最优能量函数：Final_E =1.4469初始路程：Initial_Length = 4.1888最短路程：Final_Length =2.8938实验一和实验二对比：初始条件的微小变化，也会对结果产生严重的影响，致使寻优路径，换位矩阵，能量函数都发生变化，产生了更优的结果。 实验三20个城市归一化坐标： （0.8954 0.0946） （0.5825 0.3232） （0.5827 0.7696） （0.8549 0.2341） （0.0349 0.7404） （0.8854 0.6928） （0.4077 0.8241） （0.0364 0.8280） （0.7461 0.2934） （0.1548 0.3094） （0.1439 0.5230） （0.6060 0.3253） （0.2545 0.8318） （0.3242 0.8103） （0.4018 0.5570） （0.4064 0.2630） （0.3862 0.6806） （0.6098 0.2337） （0.1669 0.4564） （0.1881 0.3846）k=1:1:5000（迭代次数）;A=B=D=500,C=200;u0=0.02（初始条件）;step=0.01; N=20(10个城市)寻优路径矩阵：V1 =1000000000000000000000001000000000000000000000000000000000100100000000000000000000000000000010000000000000000000000000010000000000000000010000000000000100000000001000000000000000000000000000000010000000000000000000001000000001000000000000000000000000100000000000000000010000000000000000010000000000000000001000000000000000000000100000000000000100000000000000000000000000000001000000000000000001000000优化路径：C1-C4-C9-C18-C2-C12-C16-C15-C17-C14-C13-C8-C5-C20-C10-C19-C11-C7-C3-C6最优能量函数E=1.9335初始路程LI= 9.0503优化最短路程LF=3.8671对比可知，经过神经网络得出的路径能量函数减小，路程比初始路程优化了很多，说明hopfield神经网络可以有效解决TSP问题。附录：程序代码 % % % % % % 计算dufunction du=DeltaU(V,d,A,D)n,n=size(V);t1=repmat(sum(V,2)-1,1,n);t2=repmat(sum(V,1)-1,n,1);PermitV=V(:,2:n);PermitV=PermitV V(:,1);t3=d*PermitV;du=-1*(A*t1+A*t2+D*t3);% % % % % % 计算能量函数function E=Energy(V,d,A,D)n,n=size(V);t1=sumsqr(sum(V,2)-1);t2=sumsqr(sum(V,1)-1);PermitV=V(:,2:n);PermitV=PermitV V(:,1);temp=d*PermitV;t3=sum(sum(V.*temp);E=0.5*(A*t1+A*t2+D*t3);% % % % % % 计算最终总路程function L=Final_RouteLength(V,citys)xxx,order=max(V);New=citys(order,:);New=New;New(1,:);rows,cs=size(New);L=0;for i=2:rowsL=L+dist(New(i-1,:),New(i,:);end% 计算初始总路程function L0=Initial_RouteLength(citys)%citys=citys;citys(1,:);r,c=size(citys);L0=0;for i=2:r L0=L0+dist(citys(i-1,:),citys(i,:);end% % % % % % % 路径寻优作图function PlotR(V,citys)figure;citys_origin=citys;citys=citys;citys(1,:);xxx,order=max(V);New=citys(order,:);New=New;New(1,:);% subplot(1,2,1)figure(1) ;plot(citys(1,1),citys(1,2),p) % first cityhold onplot(citys(2,1),citys(2,2),p) % second cityhold onplot(citys(:,1),citys(:,2),ko-)for i=1:length(citys_origin) text(citys_origin(i,1),citys_origin(i,2), num2str(i)endxlabel(横向距离X)ylabel(纵向距离Y)title(原始路线)axis(0 1 0 1)grid onfigure(2) ;plot(New(1,1),New(1,2),p) % first cityhold onplot(New(2,1),New(2,2),p) % second cityhold onplot(New(:,1),New(:,2),ko-)for i=1:length(citys_origin) text(citys_origin(i,1),citys_origin(i,2), num2str(i)endxlabel(横向距离X)ylabel(纵向距离Y)title(TSP路线)axis(0 1 0 1)axis ongrid on% % % % % % 标准化路径，并检查路径合法性，要求每行每列只有一个“1”function V1,CheckR=RouteCheck(V)rows,cols=size(V);V1=zeros(rows,cols);XC,Order=max(V);for j=1:cols V1(Order(j),j)=1;endC=sum(V1);R=sum(V1);CheckR=sumsqr(C-R);%神经网络解决TSP问题%function TSP_hopfield()clear all;close all;% step 1A=1.5;D=1;u0=0.02;step=0.01;% step 2N=20;citys=load(cities10.txt);Initial_Length=Initial_RouteLength(citys); % 计算初始路径长度DistanceCity=dist(citys,citys);% step 3u=2*rand(N,N)-1;U=0.5*u0*log(N-1)+u;V=(1+tanh(U/u0)/2;for k=1:1:5000 times(k)=k; % step 4 dU=DeltaU(V,DistanceCity,A,D); % step 5 U=U+dU*step; % step 6 V=(1+tanh(U/u0)/2; % step 7 计算能量函数 E=Energy(V,DistanceCity,A,D); Ep(k)=E; % step 8 检查路径合法性 V1,CheckR=RouteCheck(V);end% step 9if (CheckR=0) Final_E=Energy(V1,DistanceCity,A,D); Final_Length=Final