tsp yichuan.rar_6G16_believed6lc_matlab 最短路径问题_最短路径

clc; clear; A=[185 151%我自己写的时候用的是调用数据，为方便他人运行加上这 21 15 127 32 177 87 180 196 73 137 123 19 144 157 110 14 47 144 131 41 85 36 200 109 52 171 151 143 5 181 148 95 102 79 77 33 161 182 157 49 165 3 114 93 43 104 30 164 78 3 36 150 134 50 180 56 89 21 175 179 4 104 9 12 12 95 77 101 88 164 89 184 99 150 69 106 6 43 104 178 49 8 4 40 43 185 114 178 68 46 114 157 185 143 29 196 164 57 ]; n=10;N=49;city_new=zeros(10,51);DMIN=zeros(1,52);DMIN(1,1)=9999999; farm=zeros(n,N);%用于存储种群 for i=1:n; farm(i,:)=randperm(N)+1;%随机生成初始种群 end city=zeros(n,N+2); city(:,1)=1; city(:,N+2)=1; for i=1:n for j=1:N city(i,j+1)=farm(i,j); end end %生成初始的10条路径 DLn=zeros(N+1,N+1);%距离矩阵 for i=1:N+1 for j=1:N+1 DLn(i,j)=((A(i,1)-A(j,1))^2+(A(i,2)-A(j,2))^2)^0.5; end end for zn=1:1000 %2 D=zeros(n,1);%随机的10条路程的距离 for i=1:n m=0; for j=1:N+1 m=DLn(city(i,j),city(i,j+1)); D(i,1)=D(i,1)+m; end end v=zeros(n,1);%适应度 p=zeros(n,1);%每条路径的概率 q=zeros(n,1);a=0;%累计概率 for i=1:n v(i,1)=sum(D)/D(i,1); end for i=1:n p(i,1)=v(i,1)/sum(v); q(i,1)=p(i,1)+a; a=q(i,1); end for ze=1:5%第八步进行5次循环 r1=rand;%随机选择两条路 p1=zeros(1,N+2); if r1<q(1,1) p1(1,:)=city(1,:); else for i=1:n-1 if r1>q(i,1)&&r1<q(i+1) p1(1,:)=city(i+1,:); end end end p2=p1; while (p2==p1) r2=rand; if r2<q(1,1) p2(1,:)=city(1,:); else for i=1:n-1 if r2>q(i,1)&&r2<q(i+1) p2(1,:)=city(i+1,:); end end end end r=rand;%交配 if r<0.9 R=randperm(N-4,1); for j=R+1:R+5 a=p1(1,j); p1(1,j)=p2(1,j); p2(1,j)=a; end end cf1=zeros(1,5);wz1=zeros(1,5); k1=0; for i=1:R%找出第一条路重复的数字和其所在的位置 for j=R+1:R+5 if p1(1,i)==p1(1,j) k1=k1+1; wz1(1,k1)=i; cf1(1,k1)=p1(1,i); end end end for i=R+6:N+1 for j=R+1:R+5 if p1(1,i)==p1(1,j) k1=k1+1; wz1(1,k1)=i; cf1(1,k1)=p1(1,i); end end end cf1(cf1==0)=[];wz1(wz1==0)=[]; qs2=cf1; cf2=zeros(1,5);wz2=zeros(1,5); k2=0; for i=1:R%找出第二条路重复的数字和其所在的位置 for j=R+1:R+5 if p2(1,i)==p2(1,j) k2=k2+1; wz2(1,k2)=i; cf2(1,k2)=p2(1,i); end end end for i=R+6:N+1 for j=R+1:R+5 if p2(1,i)==p2(1,j) k2=k2+1; wz2(1,k2)=i; cf2(1,k2)=p2(1,i); end end end cf2(cf2==0)=[];wz2(wz2==0)=[]; qs1=cf2; p1_new=p1;%将1中重复的替换成它缺少的 r3=randperm(size(qs1,2)); qs1_new=qs1(1,r3); for i=1:k1 p1_new(1,wz1(1,i))=qs1_new(1,i); end p2_new=p2;%将2中重复的替换成它缺少的 r4=randperm(size(qs2,2)); qs2_new=qs2(1,r4); for i=1:k2 p2_new(1,wz2(1,i))=qs2_new(1,i); end pm1=rand;h1=0;h2=0;%变异操作 if pm1<0.2 X1=randperm(N,1)+1; X11=X1; while X11==X1 X11=randperm(N,1)+1; end h1=p1_new(1,X1); p1_new(1,X1)=p1_new(1,X11); p1_new(1,X11)=h1; end pm2=rand; if pm2<0.2 X2=randperm(N,1)+1; X22=X2; while X22==X2 X22=randperm(N,1)+1; end h2=p2_new(1,X2); p2_new(1,X2)=p2_new(1,X22); p2_new(1,X22)=h2; end %第八步的迭代 city_new(2*ze-1,:)=p1_new(1,:); city_new(2*ze,:)=p2_new(1,:); DM=zeros(2,1); cityN=[p1_new;p2_new];%找出新的两条路之间的距离 for i=1:2 m=0; for j=1:N+1 m=DLn(cityN(i,j),cityN(i,j+1)); DM(i,1)=DM(i,1)+m; end end if DM(1,1)<DM(2,1)%比较两条路的长度，记录短的 RE(ze,:)=[DM(1,1),p1_new]; else RE(ze,:)=[DM(2,1),p2_new]; end end%第八步的五次循环结束 for ze=1:5 %比较第八步中每一次得到的较短的路径 if RE(ze,1)<=DMIN(1,1) DMIN(1,:)=RE(ze,:);%得到最佳的路径 end end city=city_new;%将第八步中得到的新的10条路，跳转到第二步 end DMIN %输出最后的结果，其第一列为距离，2-52列为最佳的路线 CITY=zeros(1,51);%多余的画图命令 for i=1:51 CITY(1,i)=DMIN(1,i+1); end for i=1:N+1 plot([A(CITY(1,i),1),A(CITY(i+1),1)],[A(CITY(i),2),A(CITY(i+1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g'); text(A(CITY(i),1),A(CITY(i),2),[' ',int2str(CITY(i))]); text(A(CITY(i+1),1),A(CITY(i+1),2),[' ',int2str(CITY(i+1))]); hold on; end