模拟退火算法及禁忌搜索算法的matlab源程序_第1页
模拟退火算法及禁忌搜索算法的matlab源程序_第2页
模拟退火算法及禁忌搜索算法的matlab源程序_第3页
模拟退火算法及禁忌搜索算法的matlab源程序_第4页
模拟退火算法及禁忌搜索算法的matlab源程序_第5页
已阅读5页,还剩1页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

% 模拟退火算法源程序% 此题以中国31省会城市的最短旅行路径为例:% clear;clc;function MinD,BestPath=MainAneal(pn)% CityPosition存储的为每个城市的二维坐标x和y;CityPosition=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;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;figure(1);plot(CityPosition(:,1),CityPosition(:,2),o)m=size(CityPosition,1);%城市的数目%D = sqrt(CityPosition(:,ones(1,m) - CityPosition(:,ones(1,m).2 + . (CityPosition(:,2*ones(1,m) - CityPosition(:,2*ones(1,m).2);path=zeros(pn,m);for i=1:pn path(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=tau iter_num=1; m_num=1; while m_numm_max & iter_numiter_max for 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); end R=rand(1,pn); if find(Len2-Len1R)=0) path(find(Len2-Len1R)=0),:)=path2(find(Len2-Len1R)=0),:); %#ok Len1(find(Len2-Len1R)=0)=Len2(find(Len2-Len1R)=0); TempMinD,TempIndex=min(Len1); TracePath(N,:)=path(TempIndex,:); %#ok Distance(N)=TempMinD; %#ok N=N+1; else m_num=m_num+1; endend iter_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=ChangePath2(p1,CityNum)while(1) R=unidrnd(CityNum,1,2); if abs(R(1)-R(2) 0 break; endendI=R(1);J=R(2);if IJ p2(1:I)=p1(1:I); p2(I+1:J)=p1(J:-1:I+1); p2(J+1:CityNum)=p1(J+1:CityNum);else p2(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省会城市的最短旅行路径为例:%禁忌搜索是对局部领域搜索的一种扩展,是一种全局逐步寻优算法,搜索过程可以接受劣解,有较强的爬山能力.领域结构对收敛性有很大影响。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;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问题的规模,即城市数目dislist=zeros(CityNum); for i=1:CityNum for j=1:CityNum dislist(i,j)=(Clist(i,1)-Clist(j,1)2+(Clist(i,2)-Clist(j,2)2)0.5; endendTabuList=zeros(CityNum);% (tabu list)TabuLength=round(CityNum*(CityNum-1)/2)0.5);%禁忌长度(tabu length)Candidates=200;%候选集的个数 (全部领域解个数)CandidateNum=zeros(Candidates,CityNum);%候选解集合S0=randperm(CityNum);%随机产生初始解BSF=S0;BestL=Inf;clf; figure(1);stop = uicontrol(style,toggle,string,stop,background,white);tic;p=1;StopL=80*CityNum;while pCityNum*(CityNum-1)/2 disp(候选解个数不大于n*(n-1)/2!); break; end ALong(p)=Fun(dislist,S0); i=1; A=zeros(Candidates,2); while i=Candidates M=CityNum*rand(1,2); M=ceil(M); if M(1)=M(2) A(i,1)=max(M(1),M(2); A(i,2)=min(M(1),M(2); if i=1 isa=0; else for j=1:i-1 if A(i,1)=A(j,1) & A(i,2)=A(j,2) isa=1; break; else isa=0; end end end if isa i=i+1; else end else end end BestCandidateNum=100;%保留前BestCandidateNum个最好候选解 BestCandidate=Inf*ones(BestCandidateNum,4); F=zeros(1,Candidates); for i=1:Candidates CandidateNum(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=BestCandidateNum BestCandidate(i,2)=F(i); BestCandidate(i,1)=i; BestCandidate(i,3)=S0(A(i,1); BestCandidate(i,4)=S0(A(i,2); else for j=1:BestCandidateNum if F(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; end end end end %对BestCandidate JL,Index=sort(BestCandidate(:,2); SBest=BestCandidate(Index,:); BestCandidate=SBest; if BestCandidate(1,2)BestL BestL=BestCandidate(1,2); S0=CandidateNum(BestCandidate(1,1),:); BSF=S0; for m=1:CityNum for n=1:CityNum if TabuList(m,n)=0 TabuList(m,n)=TabuList(m,n)-1; end end end TabuList(BestCandidate(1,3),BestCandidate(1,4)=TabuLength; else for i=1:BestCandidateNum if TabuList(BestCandidate(i,3),BestCandidate(i,4)=0 S0=CandidateNum(BestCandidate(i,1),:); for m=1:CityNum for n=1:CityNum if TabuList(m,n)=0 TabuList(m,n)=TabuList(m,n)-1; end end end TabuList(BestCandidate(i,3),BestCandidate(i,4)=TabuLength; break; end end end p=p+1; ArrBestL(p)=BestL; %#ok 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),ro-); title(Counter:,int2str(p*Candidates), The Min Distance:,num2str(BestL); hold off; pause(0.005); if get(stop,value)=1 break; endendtoc;BestShortcut=BSF;theMinDistance=BestL;set(stop,style,pushbutton,string,close, callback,close

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论