hopfield網(wǎng)絡(luò)求解TSP問(wèn)題

1、Hopfield神經(jīng)網(wǎng)絡(luò)求解TSP問(wèn)題 1. 什么是TSP問(wèn)題？ 旅行商問(wèn)題，即TSP問(wèn)題（Traveling Salesman Problem），也是最優(yōu)化問(wèn)題。一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要 回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。 用數(shù)學(xué)語(yǔ)言描述TSP如下 :設(shè)有限個(gè)城市集合 : C = C1 , C 2 , , Cn ，每?jī)蓚€(gè)城市間的距離為 d（Ci，Cj）Z, 其中 Ci，CjC（ 1=i , j 0為常數(shù)。保證當(dāng)矩陣V的每一行不多于一個(gè)1時(shí)，達(dá)到最小=0。 ，其中B0為常數(shù)。保證當(dāng)

2、矩陣V的每一列不多于一個(gè)l時(shí)，達(dá)到最小=0。 ，其中C0為常數(shù)。保證當(dāng)矩陣V中的1的個(gè)數(shù)恰好為n時(shí)，即整個(gè)矩陣有n個(gè)1時(shí)，達(dá)到最小=0。 ，實(shí)際數(shù)值就是一次有效路徑總長(zhǎng)度的倍數(shù)。若路徑為最佳時(shí)，達(dá)到最小點(diǎn)。9. Hopfield神經(jīng)網(wǎng)絡(luò)狀態(tài)方程將約束條件能量函數(shù)E和神經(jīng)網(wǎng)絡(luò)電路標(biāo)準(zhǔn)能量函數(shù)公式對(duì)比，并化簡(jiǎn)后得：其中為神經(jīng)元的時(shí)空綜合輸入, 為其對(duì)應(yīng)的神經(jīng)元的輸出10.Matlab實(shí)現(xiàn)與仿真結(jié)果實(shí)驗(yàn)一：10個(gè)城市的歸一化坐標(biāo)： （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（迭代次數(shù)）;A=B=D=500,C=200;u0=0.02（初始條件）;step=0.01;N=10(10個(gè)城市) TSP_hopfield迭代次數(shù)k = 5000尋優(yōu)路徑矩陣：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優(yōu)化路徑L=C6-C9-C8-C1-C10-C7-C5-C3-C4-C2-C6最優(yōu)能量函數(shù)：Final_E = 1.5063初始路程：Initial_Length = 4.1888最短路程：Final_Length =3.0126迭代次數(shù)對(duì)能量函數(shù)的影響能量函數(shù)隨著迭代次數(shù)的增加而減小，最后達(dá)到極小穩(wěn)定值，而在迭代開始的時(shí)候優(yōu)化約束條件能量函數(shù)迅速下降，說(shuō)明神經(jīng)網(wǎng)絡(luò)對(duì)于解決TSP的有效性。實(shí)驗(yàn)二改變u0=0.03，其他的都變TSP_hopfi

5、eld迭代次數(shù)k = 5000尋優(yōu)路徑矩陣：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優(yōu)化路徑L=C4-C6-C3-C5-C7-C10-C1-C8-C9-C-C4最優(yōu)能量函數(shù)：Final_E =1.4469初始路程：Initial_L

6、ength = 4.1888最短路程：Final_Length =2.8938實(shí)驗(yàn)一和實(shí)驗(yàn)二對(duì)比：初始條件的微小變化，也會(huì)對(duì)結(jié)果產(chǎn)生嚴(yán)重的影響，致使尋優(yōu)路徑，換位矩陣，能量函數(shù)都發(fā)生變化，產(chǎn)生了更優(yōu)的結(jié)果。 實(shí)驗(yàn)三20個(gè)城市歸一化坐標(biāo)： （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（迭代次數(shù)）;A=B=D=500,C=200;u0=0.02（初始條件）;step=0.01; N=20(10個(gè)城市)尋優(yōu)路徑矩陣：V1 =1000000000000000000000001000000000000000000000000000000000100100000000000000000000

8、000000000010000000000000000000000000010000000000000000010000000000000100000000001000000000000000000000000000000010000000000000000000001000000001000000000000000000000000100000000000000000010000000000000000010000000000000000001000000000000000000000100000000000000100000000000000000000000000000001000000

9、000000000001000000優(yōu)化路徑：C1-C4-C9-C18-C2-C12-C16-C15-C17-C14-C13-C8-C5-C20-C10-C19-C11-C7-C3-C6最優(yōu)能量函數(shù)E=1.9335初始路程LI= 9.0503優(yōu)化最短路程LF=3.8671對(duì)比可知，經(jīng)過(guò)神經(jīng)網(wǎng)絡(luò)得出的路徑能量函數(shù)減小，路程比初始路程優(yōu)化了很多，說(shuō)明hopfield神經(jīng)網(wǎng)絡(luò)可以有效解決TSP問(wèn)題。附錄：程序代碼 % % % % % % 計(jì)算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);% % % % % % 計(jì)算能量函數(shù)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);% % % % % % 計(jì)

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% 計(jì)算初始總路程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% % % % % % % 路徑尋優(yōu)作圖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% % % % % % 標(biāo)準(zhǔn)化路徑，并檢查路徑合法性，要求每行每列只有一個(gè)“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);%神經(jīng)網(wǎng)絡(luò)解決TSP問(wèn)題%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); % 計(jì)算初始路徑長(zhǎng)度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 計(jì)算能量函數(shù) 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