TSP禁忌搜索程序

function TspTSclear;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:31for j=1:31DL31(i,j)=(city31(i,1)-city31(j,1)A2+(city31(i,2)-city31(j,2)A2)A0.5;endenddislist=DL31;Clist=city31;CityNum=size(dislist,2);Tlist=zeros(CityNum);% 禁忌表(tabu list)cl=80;%保留前cl个最好候选解bsf=Inf;tl=ceil(CityNumA0.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)/2disp(候选解个数，不大于n*(n-1)/2(全部领域解个数)！系统自动退出！)；l1=(CityNum*(CityNum)/2)A.5;break;endArrS(p)=F(dislist,S);i=1;A=zeros(l1,2);while i=l1M=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=1isdel=0;elsefor j=1:i-1if A(i,1)=A(j,1)&A(i,2)=A(j,2) isdel=1;break;elseisdel=0;endendendif isdeli=i+1;else i=i;endelse i=i;endendCL=Inf*ones(cl,4);for i=1:l1Si(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=clCL(i,2)=F(i);CL(i,1)=i;CL(i,3)=S(A(i,1);CL(i,4)=S(A(i,2);elsefor j=1:clif 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;endendendendif CL(1,2)bsf%藐视准则(aspiration criterion)bsf=CL(1,2);S=Si(CL(1,1),:);BSF=S;for m=1:CityNumfor n=1:CityNumif Tlist(m,n)=0Tlist(m,n)=Tlist(m,n)-1;endendendTlist(CL(1,3),CL(1,4)=tl;elsefor i=1:clif Tlist(CL(i,3),CL(i,4)=0S=Si(CL(i,1),:);for m=1:CityNumfor n=1:CityNumif Tlist(m,n)=0Tlist(m,n)=Tlist(m,n)-1;endendendTlist(CL(i,3),CL(i,4)=tl;break;endendendp=p+1;Arrbsf(p)=bsf;for i=1:CityNum-1plot(Clist(BSF(i),1),Clist(BSF(i+1),1),Clist(BSF(i),2),Clist(BSF(i+1),2),bo-); hold on;endplot(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)=1break;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)DistanV=0;n=size(s,2);for i=1:(n-1)DistanV=DistanV+dislist(s(i),s(i+1);endDistanV=DistanV+dislist(s(n),s(1);F=DistanV;end