matlab-基于禁忌搜索算法的TSP最优路径规划matlab仿真-源码

clc; clear; close all; warning off; addpath(genpath(pwd)); CityNum=22; [dislist,Clist]=tsp(CityNum); Tlist=zeros(CityNum);%禁忌表(tabu list) cl=60;%保留前cl个最好候选解 bsf=Inf; tl=50; %禁忌长度(tabu length) l1=100;%候选解(candidate),不大于n*(n)/2(全部领域解个数) S0=randperm(CityNum); S0(:,1)=0; S0(:,CityNum)=CityNum-1; S0(:,2:CityNum-1)=randperm(CityNum-2); S0=S0+ones; S=S0(:,2:CityNum-1); Num=length(S); BSF=S0; Si=zeros(l1,Num); StopL=100; %终止步数 p=1; clf; figure(1); while (p<StopL+1) if l1>Num*(Num)/2 disp('候选解个数,不大于n*(n)/2(全部领域解个数)！ 系统自动退出！'); l1=(Num*(Num)/2)^.5; break; end ArrS(p)=CalDist(dislist,S); i=1; A=zeros(l1,2); while i<=l1 M=Num*rand(1,2); M=ceil(M); if M(1)~=M(2) m1=max(M(1),M(2));m2=min(M(1),M(2)); A(i,1)=m1;A(i,2)=m2; if i==1 isdel=0; else for j=1:i-1 if A(i,1)==A(j,1)&&A(i,2)==A(j,2) isdel=1; break; else isdel=0; end end end if ~isdel i=i+1; else i=i; end else i=i; end end for i=1:l1 Si(i,:)=S; Si(i,[A(i,1),A(i,2)])=S([A(i,2),A(i,1)]); CCL(i,1)=i; CCL(i,2)=CalDist(dislist,Si(i,:)); CCL(i,3)=S(A(i,1)); CCL(i,4)=S(A(i,2)); end [fs fin]=sort(CCL(:,2)); for i=1:cl CL(i,:)=CCL(fin(i),:); end if CL(1,2)<bsf %藐视准则(aspiration criterion) bsf=CL(1,2); S=Si(CL(1,1),:); BSF(:,2:CityNum-1)=S; for m=1:Num for n=1:Num if Tlist(m,n)~=0 Tlist(m,n)=Tlist(m,n)-1; end end end Tlist(CL(1,3),CL(1,4))=tl; else for i=1:cl if Tlist(CL(i,3),CL(i,4))==0 S=Si(CL(i,1),:); for m=1:Num for n=1:Num if Tlist(m,n)~=0 Tlist(m,n)=Tlist(m,n)-1; end end end Tlist(CL(i,3),CL(i,4))=tl; break; end end end Arrbsf(p)=bsf; drawTSP(Clist,BSF,bsf,p,0); p=p+1; end BestShortcut=BSF; n=22; GX1=[0,4,5,6,7,9,10,11,16,17,18,19,20,21,22,24,25,26,27,29,30,31]; GX=zeros(1,22); for i1=1:n k=find(BestShortcut(:,:)==i1); GX(:,k)=GX1(:,i1); end GX theMinDistance=bsf figure(2); plot(Arrbsf,'r'); hold on; plot(ArrS,'b');grid; title('搜索过程'); legend('最优解','当前解');