TSP禁忌搜索程序.doc

function TspTS clear;city31=1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;4196 1004;4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2367;3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975;for i=1:31 for j=1:31 DL31(i,j)=(city31(i,1)-city31(j,1)2+(city31(i,2)-city31(j,2)2)0.5; endenddislist=DL31;Clist=city31;CityNum=size(dislist,2);Tlist=zeros(CityNum); %禁忌表(tabu list)cl=80; %保留前cl个最好候选解bsf=Inf;tl=ceil(CityNum0.5); %禁忌长度(tabu length)l1=160; %候选解(candidate),不大于n*(n-1)/2(全部领域解个数)S0=randperm(CityNum);S=S0;BSF=S0;Si=zeros(l1,CityNum);StopL=80*CityNum;p=1;clf;figure(1);stop = uicontrol(style,toggle,string,stop, background,white);tic;while (pCityNum*(CityNum)/2 disp(候选解个数,不大于n*(n-1)/2(全部领域解个数)！ 系统自动退出！); l1=(CityNum*(CityNum)/2).5; break; end ArrS(p)=F(dislist,S); i=1; A=zeros(l1,2); while i=l1 M=CityNum*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 CL=Inf*ones(cl,4); for i=1:l1 Si(i,:)=S; Si(i,A(i,1),A(i,2)=S(A(i,2),A(i,1); F(i)=F(dislist,Si(i,:); if i=cl CL(i,2)=F(i); CL(i,1)=i; CL(i,3)=S(A(i,1); CL(i,4)=S(A(i,2); else for j=1:cl if F(i)CL(j,2) CL(j,2)=F(i); CL(j,1)=i; CL(j,3)=S(A(i,1); CL(j,4)=S(A(i,2); break; end end end end if CL(1,2)bsf %藐视准则(aspiration criterion) bsf=CL(1,2); S=Si(CL(1,1),:); BSF=S; for m=1:CityNum for n=1:CityNum 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:CityNum for n=1:CityNum 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 p=p+1; Arrbsf(p)=bsf; for i=1:CityNum-1 plot(Clist(BSF(i),1),Clist(BSF(i+1),1),Clist(BSF(i),2),Clist(BSF(i+1),2),bo-); hold on; end plot(Clist(BSF(CityNum),1),Clist(BSF(1),1),Clist(BSF(CityNum),2),Clist(BSF(1),2),bo-); title(Counter : ,int2str(p*l1), The Min Distance: ,num2str(bsf); hold off; pause(0.005); if get(stop,value)=1 break; endendtoc;BestShortcut=BSFtheMinDistance=bsfset(stop,style,pushbutton,string,close, callback,close(gcf);figure(2);plot(Arrbsf,r); hold on;plot(ArrS,b);grid;title(搜索过程);legend(Best So Far,当前解);endfunction F=F(dislist,s)