模擬退火算法及禁忌搜索算法的matlab源程序

1、%模擬退火算法源程序%此題以中國31省會城市的最短旅行路徑為例：%clear;clc;functionMinD,BestPath=MainAneal(pn)%CityPosition存儲的為每個城市的二維坐標(biāo)x和y；CityPosition=13042312;36391315;41772244;37121399;34881535;33261556;32381229;.41961044;4312790;4386570;30071970;25621756;27881491;23811676;.1332695;37151678;39182179;40612370;37802212;36762578;

2、40292838;.42632931;34291908;35072376;33942643;34393201;29353240;31403550;.25452357;27782826;23702975;figure(1);plot(CityPosition(:,1),CityPosition(:,2),'o')m=size(CityPosition,1);%城市的數(shù)目%D=sqrt(CityPosition(:,ones(1,m)-CityPosition(:,ones(1,m)').A2+.(CityPosition(:,2*ones(1,m)-CityPositio

3、n(:,2*ones(1,m)').A2);path=zeros(pn,m);fori=1:pnpath(i,:)=randperm(m);enditer_max=100;%im_max=5;%Len1=zeros(1,pn);Len2=zeros(1,pn);path2=zeros(pn,m);t=zeros(1,pn);T=1e5;tau=1e-5;N=1;whileT>=tauiter_num=1;m_num=1;whilem_num<m_max&&iter_num<iter_maxfori=1:pnLen1(i)=sum(D(path(i,1:

4、m-1)+m*(path(i,2:m)-1)D(path(i,m)+m*(path(i,1)-1);path2(i,:)=ChangePath2(path(i,:),m);Len2(i)=sum(D(path2(i,1:m-1)+m*(path2(i,2:m)-1)D(path2(i,m)+m*(path2(i,1)-1);endR=rand(1,pn);iffind(Len2-Len1<t&exp(Len1-Len2)/T)>R)=0)path(find(Len2-Len1<t&exp(Len1-Len2)/T)>R)=0),:)=path2(find

5、(Len2-Len1<t&exp(Len1-Len2)/T)>R)=0),:);%#ok<FNDSB>Len1(find(Len2-Len1<t&exp(Len1-Len2)/T)>R)=0)=Len2(find(Len2-Len1<t&exp(Len1-Len2)/T)>R)=0);TempMinD,TempIndex=min(Len1);TracePath(N,:)=path(TempIndex,:);%#ok<AGROW>Distance(N)=TempMinD;%#ok<AGROW>N=N+

6、1;elsem_num=m_num+1;endenditer_num=iter_num+1;T=T*0.9;endMinD,Index=min(Distance);BestPath=TracePath(Index,:);%disp(MinD)%畫出路線圖figure(2);plot(CityPosition(BestPath(1:end-1),1),CityPosition(BestPath(1:end-1),2),'r*-');functionp2=ChangePath2(p1,CityNum)while(1)R=unidrnd(CityNum,1,2);ifabs(R(1)

7、-R(2)>0break;endendI=R(1);J=R(2);ifI<Jp2(1:I)=p1(1:I);p2(I+1:J)=p1(J:-1:I+1);p2(J+1:CityNum)=p1(J+1:CityNum);elsep2(1:J-1)=p1(1:J-1);p2(J:I+1)=p1(I+1:-1:J);p2(I:CityNum)=p1(I:CityNum);end%禁忌搜索算法解決TSP問題%此題以中國31省會城市的最短旅行路徑為例：%禁忌搜索是對局部領(lǐng)域搜索的一種擴(kuò)展,是一種全局逐步尋優(yōu)算法,搜索過程可以接受劣解有較強(qiáng)的爬山能力.領(lǐng)域結(jié)構(gòu)對收斂性有很大影響。functio

8、nBestShortcut,theMinDistance=TabuSearchclear;clc;Clist=13042312;36391315;41772244;37121399;34881535;33261556;32381229;.41961044;4312790;4386570;30071970;25621756;27881491;23811676;.1332695;37151678;39182179;40612370;37802212;36762578;40292838;.42632931;34291908;35072376;33942643;34393201;29353240;31

9、403550;.25452357;27782826;23702975;CityNum=size(Clist,1);%TSP問題的規(guī)模,即城市數(shù)目dislist=zeros(CityNum);fori=1:CityNumforj=1:CityNumdislist(i,j)=(Clist(i,1)-ClistO,1)A2+(Clist(i,2)-ClistO,2)A2)A0.5;endendTabuList=zeros(CityNum);%(tabulist)TabuLength=round(CityNum*(CityNum-1)/240.5);%禁忌長度(tabulength)Candidate

10、s=200;%候選集的個數(shù)(全部領(lǐng)域解個數(shù))CandidateNum=zeros(Candidates,CityNum);%候選解集合S0=randperm(CityNum);%隨機(jī)產(chǎn)生初始解BSF=S0;BestL=Inf;clf;figure(1);stop=uicontrol('style','toggle','string','stop','background','white');tic;p=1;StopL=80*CityNum;whilep<StopLifCandidates>

11、;CityNum*(CityNum-1)/2disp('候選解個數(shù)不大于n*(n-1)/2!');break;endALong(p)=Fun(dislist,S0);i=1;A=zeros(Candidates,2);whilei<=CandidatesM=CityNum*rand(1,2);M=ceil(M);ifM(1)=M(2)A(i,1)=max(M(1),M(2);A(i,2)=min(M(1),M(2);ifi=1isa=0;elseforj=1:i-1ifA(i,1)=A(j,1)&&A(i,2)=A(j,2)isa=1;break;else

12、isa=0;endendendifisai=i+1;elseendelseendendBestCandidateNum=100;%保留前BestCandidateNum個最好候選解BestCandidate=Inf*ones(BestCandidateNum,4);F=zeros(1,Candidates);fori=1:CandidatesCandidateNum(i,:)=S0;CandidateNum(i,A(i,2),A(i,1)=S0(A(i,1),A(i,2);F(i)=Fun(dislist,CandidateNum(i,:);ifi<=BestCandidateNumBe

13、stCandidate(i,2)=F(i);BestCandidate(i,1)=i;BestCandidate(i,3)=S0(A(i,1);BestCandidate(i,4)=S0(A(i,2);elseforj=1:BestCandidateNumifF(i)<BestCandidate(j,2)BestCandidate(j,2)=F(i);BestCandidate(j,1)=i;BestCandidate(j,3)=S0(A(i,1);BestCandidate(j,4)=S0(A(i,2);break;endendendend%對BestCandidateJL,Index

14、=sort(BestCandidate(:,2);SBest=BestCandidate(Index,:);BestCandidate=SBest;ifBestCandidate(1,2)<BestLBestL=BestCandidate(1,2);S0=CandidateNum(BestCandidate(1,1),:);BSF=S0;form=1:CityNumforn=1:CityNumifTabuList(m,n)=0TabuList(m,n)=TabuList(m,n)-1;endendendTabuList(BestCandidate(1,3),BestCandidate(1

15、,4)=TabuLength;elsefori=1:BestCandidateNumifTabuList(BestCandidate(i,3),BestCandidate(i,4)=0S0=CandidateNum(BestCandidate(i,1),:);form=1:CityNumforn=1:CityNumifTabuList(m,n)=0TabuList(m,n)=TabuList(m,n)-1;endendendTabuList(BestCandidate(i,3),BestCandidate(i,4)=TabuLength;break;endendendp=p+1;ArrBest

16、L(p)=BestL;%#ok<AGROW>fori=1:CityNum-1plot(Clist(BSF(i),1),Clist(BSF(i+1),1),Clist(BSF(i),2),Clist(BSF(i+1),2),'bo-');holdon;plot(Clist(BSF(CityNum),1),Clist(BSF(1),1),Clist(BSF(CityNum),2),Clist(BSF(1),2),'ro-');title('Counter:',int2str(p*Candidates),'TheMinDistance:',num2str(BestL);holdoff;pause(0.005);ifget(stop,'value')=1break;endendtoc;BestShortcut=BSF;theMinDistance=BestL;set(stop,'style','pushbutton','string','close','callback','close(gcf)');figure(2);plot(ArrBestL,'r'