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

1、% 模擬退火算法源程序% 此題以中國(guó) 31 省會(huì)城市的最短旅行路徑為例：% clear;clc;function MinD,BestPath=MainAneal(pn)% CityPosition 存儲(chǔ)的為每個(gè)城市的二維坐標(biāo) x 和 y ；CityPosition=1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;.41961044;4312790;4386570;30071970;25621756;27881491;23811676;.1332695;37151678;39182179;40612370

2、;37802212;36762578;40292838;.42632931;34291908;35072376;33942643;34393201;29353240;31403550;.2545 2357;2778 2826;2370 2975;figure(1); plot(CityPosition(:,1),CityPosition(:,2),'o')m=size(CityPosition,1);% 城市的數(shù)目%D = sqrt(CityPositio n(:,o nes(1,m) - CityPositio n(:,o nes(1,m)')92 + . (City

3、Positio n(:,2*o nes(1,m) - CityPositio n(:,2*o nes(1,m)')42); path=zeros(pn,m);for i=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;while T>=tauiter_num=1;m_num=1;while m_num<m_max && iter_n

4、um<iter_maxfor i=1:pn Len1(i)=sum(D(path(i,1: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);if find(Len2-Len1<t&exp(Len1-Len2)/T)>R)=0)path(find(Len2-Len1

5、<t&exp(Len1-Len2)/T)>R)=0),:)=path2(find(Len2-Len1<t&exp(Len1-L en2)/T)>R)=0),:); %#ok<FNDSB>Len1(find(Len2-Len1<t&exp(Len1-Len2)/T)>R)=0)=Len2(find(Len2-Len1<t&exp(Len1-Le n2)/T)>R)=0);TempMinD,TempIndex=min(Len1);TracePath(N,:)=path(TempIndex,:); %#ok&

6、lt;AGROW>Distance(N)=TempMinD; %#ok<AGROW>N=N+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*-');function p2=ChangePa

7、th2(p1,CityNum)while(1)R=unidrnd(CityNum,1,2);if abs(R(1)-R(2) > 0break;endendI=R(1);J=R(2);if I<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 問(wèn)題%此題以中國(guó) 31 省會(huì)城市的最短旅行路徑為例：%禁忌搜索是

8、對(duì)局部領(lǐng)域搜索的一種擴(kuò)展,是一種全局逐步尋優(yōu)算法,搜索過(guò)程可以接受劣解有較強(qiáng)的爬山能力 .領(lǐng)域結(jié)構(gòu)對(duì)收斂性有很大影響。function BestShortcut,theMinDistance=TabuSearchclear;clc;Clist=1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;.4196 1044;4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;.1332 695;3715 1678;3918 2179;4061 2370

9、;3780 2212;3676 2578;4029 2838;.4263 2931;3429 1908;3507 2376;3394 2643;3439 3201;2935 3240;3140 3550;.2545 2357;2778 2826;2370 2975;CityNum=size(Clist,1);%TSP 問(wèn)題的規(guī)模 , 即城市數(shù)目dislist=zeros(CityNum);for i=1:CityNumfor j=1:CityNum dislist(i,j)=(Clist(i,1)-Clist(j,1)F2+(Clist(i,2)-Clist(j,2)A2)A0.5;enden

10、dTabuList=zeros(CityNum);% (tabu list)TabuLength=round(CityNum*(CityNum-1)/2)A0.5);%禁忌長(zhǎng)度(tabu length)Candidates=200;%候選集的個(gè)數(shù)(全部領(lǐng)域解個(gè)數(shù))CandidateNum=zeros(Candidates,CityNum);% 候選解集合S0=randperm(CityNum);% 隨機(jī)產(chǎn)生初始解BSF=S0;BestL=Inf;clf;figure(1);stop = uic on trol('style','toggle','stri

11、 ng','stop','background','white');tic;p=1;StopL=80*CityNum;while p<StopLif Candidates>CityNum*(CityNum-1)/2disp(' 候選解個(gè)數(shù)不大于 n*(n-1)/2!');break;endALong(p)=Fun(dislist,S0);i=1;A=zeros(Candidates,2);while i<=CandidatesM=CityNum*rand(1,2);M=ceil(M);if M(1)=M(

12、2)A(i,1)=max(M(1),M(2);A(i,2)=min(M(1),M(2);if i=1isa=0;elsefor j=1:i-1if A(i,1)=A(j,1) && A(i,2)=A(j,2)isa=1;break;elseisa=0;endendendif isai=i+1;elseendelseendendBestCandidateNum=100;% 保留前 BestCandidateNum 個(gè)最好候選解BestCandidate=Inf*ones(BestCandidateNum,4);F=zeros(1,Candidates);for i=1:Candi

13、datesCandidateNum(i,:)=S0;CandidateNum(i,A(i,2),A(i,1)=S0(A(i,1),A(i,2);F(i)=Fun(dislist,CandidateNum(i,:);if i<=BestCandidateNumBestCandidate(i,2)=F(i);BestCandidate(i,1)=i;BestCandidate(i,3)=S0(A(i,1);BestCandidate(i,4)=S0(A(i,2);elsefor j=1:BestCandidateNumif F(i)<BestCandidate(j,2) BestCan

14、didate(j,2)=F(i); BestCandidate(j,1)=i; BestCandidate(j,3)=S0(A(i,1); BestCandidate(j,4)=S0(A(i,2); break;endendendend%對(duì) BestCandidate JL,Index=sort(BestCandidate(:,2);SBest=BestCandidate(Index,:); BestCandidate=SBest;if BestCandidate(1,2)<BestLBestL=BestCandidate(1,2); S0=CandidateNum(BestCandid

15、ate(1,1),:);BSF=S0;for m=1:CityNumfor n=1:CityNumif TabuList(m,n)=0 TabuList(m,n)=TabuList(m,n)-1;endendend TabuList(BestCandidate(1,3),BestCandidate(1,4)=TabuLength;elsefor i=1:BestCandidateNumif TabuList(BestCandidate(i,3),BestCandidate( i,4)=0 S0=CandidateNum(BestCandidate(i,1),:);for m=1:CityNum

16、for n=1:CityNumif TabuList(m,n)=0 TabuList(m,n)=TabuList(m,n)-1;endendend TabuList(BestCandidate(i,3),BestCandidate(i,4)=TabuLength; break;endendendp=p+1;ArrBestL(p)=BestL; %#ok<AGROW>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-'); hol

17、d on;plot(Clist(BSF(CityNum),1),Clist(BSF(1),1),Clist(BSF(CityNum),2),Clist(BSF(1),2),'ro-'); title('Counter:',int2str(p*Candidates),' The Min Distance:',num2str(BestL); hold off;pause(0.005);if get(stop,'value')=1break;endendtoc;BestShortcut=BSF;theMinDistance=BestL;set(stop,'style','pushbutt on ','stri ng','close', 'callback','close(gcf)');figure(2);plot(ArrBestL,'r'); h