蟻群算法及案例分析

蟻群算法及案例分析目錄蟻群算法原理蟻群算法計算步驟TSP算例分析蟻群算法的特點及應用領域蟻群算法原理1、螞蟻在路徑上釋放信息素。2、碰到還沒走過的路口，就隨機挑選一條路走。同時，釋放與路徑長度有關的信息素。3、信息素濃度與路徑長度成反比。后來的螞蟻再次碰到該路口時，就選擇信息素濃度較高路徑。4、最優(yōu)路徑上的信息素濃度越來越大．5、最終蟻群找到最優(yōu)尋食路徑。自然界中,蟻群的這種尋找路徑的過程表現(xiàn)為一種正反饋的過程,與人工蟻群的尋優(yōu)算法極為一致。如我們把只具備了簡單功能的工作單元視為”螞蟻”,那么上述尋找路徑的過程可以用于解釋人工蟻群的尋優(yōu)過程。人工蟻群具有一定的記憶能力。它能夠記憶已經(jīng)訪問過的節(jié)點;另外,人工蟻群在選擇下一條路徑的時候并不是完全盲目的,而是按一定的算法規(guī)律有意識地尋找最短路徑自然界蟻群不具有記憶的能力，它們的選路憑借外激素，或者道路的殘留信息來選擇，更多地體現(xiàn)正反饋的過程人工蟻群和自然界蟻群的相似之處在于,兩者優(yōu)先選擇的都是含“外激素”濃度較大的路徑;兩者的工作單元(螞蟻)都是通過在其所經(jīng)過的路徑上留下一定信息的方法進行間接的信息傳遞。蟻群算法原理開始初始化迭代次數(shù)Nc=Nc+1螞蟻k=1螞蟻k=k+1按照狀態(tài)轉移概率公式選擇下一個元素修改禁忌表K>=螞蟻總數(shù)m？按照公式進行信息量更新滿足結束條件？輸出程序計算結果結束YYNN蟻群算法計算步驟TSP算例分析給定n個城市和兩個兩個城市之間的距離，要求確定一條經(jīng)過各個城市一次當且僅當一次的最短路徑。旅行商問題（TSP）第一步:初始化將m只螞蟻隨機放到n個城市，每只螞蟻的禁忌表為螞蟻當前所在城市，各邊信息初始化為c。禁忌表體現(xiàn)了人工螞蟻的記憶性，使得螞蟻不會走重復道路，提高了效率。TSP算例分析

TSP算例分析

TSP算例分析第四步：輸出結果若迭代次數(shù)小于預定的迭代次數(shù)且無退化行為（找到的都是相同的解）則轉步驟二，否則，輸出目前的最優(yōu)解。

參數(shù)選取TSP算例分析%第一步：變量初始化n=size(C,1);%n表示問題的規(guī)模（城市個數(shù)）D=zeros(n,n);%D表示完全圖的賦權鄰接矩陣fori=1:nforj=1:nifi~=jD(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;%點i,j之間的距離elseD(i,j)=eps;endD(j,i)=D(i,j);endendEta=1./D;%Eta為啟發(fā)因子，這里設為距離的倒數(shù)Tau=ones(n,n);%Tau為信息素矩陣Tabu=zeros(m,n);%存儲并記錄路徑的生成NC=1;%迭代計數(shù)器R_best=zeros(NC_max,n);%各代最佳路線L_best=inf.*ones(NC_max,1);%各代最佳路線的長度L_ave=zeros(NC_max,1);%各代路線的平均長度

while

NC<=NC_max%停止條件之一：達到最大迭代次數(shù)%第二步：將m只螞蟻放到n個城市上Randpos=[];fori=1:(ceil(m/n))Randpos=[Randpos,randperm(n)];endTabu(:,1)=(Randpos(1,1:m))';%第三步：m只螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游forj=2:nfori=1:mvisited=Tabu(i,1:(j-1));%已訪問的城市J=zeros(1,(n-j+1));%待訪問的城市P=J;%待訪問城市的選擇概率分布Jc=1;fork=1:nifisempty(find(visited==k,1))J(Jc)=k;Jc=Jc+1;endend%計算待選城市的概率分布fork=1:length(J)P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);endP=P/(sum(P));%按概率原則選取下一個城市Pcum=cumsum(P);Select=find(Pcum>=rand);to_visit=J(Select(1));Tabu(i,j)=to_visit;endendifNC>=2Tabu(1,:)=R_best(NC-1,:);end%%第四步：記錄本次迭代最佳路線L=zeros(m,1);fori=1:mR=Tabu(i,:);forj=1:(n-1)L(i)=L(i)+D(R(j),R(j+1));endL(i)=L(i)+D(R(1),R(n));endL_best(NC)=min(L);pos=find(L==L_best(NC));R_best(NC,:)=Tabu(pos(1),:);L_ave(NC)=mean(L);NC=NC+1;%第五步：更新信息素Delta_Tau=zeros(n,n);fori=1:mforj=1:(n-1)Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);endDelta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);endTau=(1-Rho).*Tau+Delta_Tau;%第六步：禁忌表清零Tabu=zeros(m,n);end

%第七步：輸出結果Pos=find(L_best==min(L_best));Shortest_Route=R_best(Pos(1),:);Shortest_Length=L_best(Pos(1));subplot(1,2,1)DrawRoute(C,Shortest_Route)subplot(1,2,2);plot(L_best)holdonplot(L_ave)holdoffend子函數(shù)：functionDrawRoute(C,R)%畫路線圖的子函數(shù)%C:節(jié)點坐標，由一個N×2的矩陣存儲%R:Rout路線N=length(R);scatter(C(:,1),C(:,2));holdonplot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])hold

onfor

ii=2:Nplot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])hold

onend

endTSP算例分析Shortest_Length=1.5602e+04蟻群算法的特點及應用領域蟻群算法的特點優(yōu)點缺點不依賴于所求問題的具體數(shù)學表達式描述，具有很強的找到全局最優(yōu)解的優(yōu)化能力模型普適性不強，不能直接應用于實際優(yōu)化問題正反饋、較強的魯棒性、全局性、普遍性局部搜索能力較弱，易出現(xiàn)停滯和局部收斂、收斂速度慢等問題優(yōu)良的分布式并行計算機制長時間花費在解的構造上，導致搜索時間過長易于與其他方法相結合算法最先基于離散問題，