hopfield网络求解TSP问题_第1页
hopfield网络求解TSP问题_第2页
hopfield网络求解TSP问题_第3页
hopfield网络求解TSP问题_第4页
hopfield网络求解TSP问题_第5页
已阅读5页,还剩15页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、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为常数。保证当

2、矩阵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.28

3、10 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

4、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_hopfi

5、eld迭代次数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_L

6、ength = 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.60

7、60 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 =1000000000000000000000001000000000000000000000000000000000100100000000000000000000

8、000000000010000000000000000000000000010000000000000000010000000000000100000000001000000000000000000000000000000010000000000000000000001000000001000000000000000000000000100000000000000000010000000000000000010000000000000000001000000000000000000000100000000000000100000000000000000000000000000001000000

9、000000000001000000优化路径: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

10、(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);% % % % % % 计

11、算最终总路程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,:);e

12、nd% % % % % % % 路径寻优作图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),

13、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_origi

14、n) 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

15、);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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论