




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025版城市排水降水井施工服务合同
- 二零二五年度股权激励撤资退股合同范本
- 二零二五年度国有企业员工劳务派遣合作协议
- 二零二五年度二手房买卖合同房屋质量及验收标准
- 2025版酒吧DJ岗位聘用及权益保障合同
- 2025版学生军训教官心理健康辅导服务合同
- 二零二五年度快递物流紧急救援服务合同
- 2025版信息技术服务外包合同规范
- 二零二五年度股权激励与分红权转让组合合同范本
- 2025年度建筑行业临时工聘用合同
- 2025年江苏省C类行测真题及答案
- 中心静脉压测量技术
- 加盟红娘合同样本
- 骨科考试题库及答案
- 2024年大学生就业力调研报告-智联招聘-202405
- 2025年中考语文一轮复习:名著阅读《朝花夕拾》考点预测练习题(含答案)
- 儿童输血指南课件
- 2025年-重庆市建筑安全员-B证(项目经理)考试题库
- 靶向治疗的不良反应及护理
- 保安证考试职业道德试题及答案
- 道路交通事故安全警示教育培训
评论
0/150
提交评论