蟻群算法解決TSP問題程序(共4頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 蟻群算法用于求解TSP問題，經(jīng)過仿真測試，發(fā)現(xiàn)此程序的優(yōu)化效率和魯棒性都非常好。這與在無線多媒體傳感器網(wǎng)絡(luò)路由算法應(yīng)用到的尋找最佳路徑的蟻群算法非常相似。function R_best,L_best,L_ave,Shortest_Route,Shortest_Length=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)%=%  主要符號(hào)說明%  C     n個(gè)城市的坐標(biāo)，n×2的矩陣%  NC_max   最大迭代次數(shù)% 

2、 m     螞蟻個(gè)數(shù)%  Alpha   表征信息素重要程度的參數(shù)%  Beta    表征啟發(fā)式因子重要程度的參數(shù)%  Rho    信息素蒸發(fā)系數(shù)%  Q     信息素增加強(qiáng)度系數(shù)%  R_best   各代最佳路線%  L_best   各代最佳路線的長度%=%第一步：變量初始化n=size(*,1

3、);%*表示問題的規(guī)模（城市個(gè)數(shù)）*=zeros(n,n);%D表示完全圖的賦權(quán)鄰接矩陣for i=1:n    for j=1:n        if i=j            D(i,j)=(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2)0.5;        else  &

4、#160;         D(i,j)=eps;        end        D(j,i)=D(i,j);    endendEta=1./D;%Eta為啟發(fā)因子，這里設(shè)為距離的倒數(shù)Tau=ones(n,n);%Tau為信息素矩陣Tabu=zeros(m,n);%存儲(chǔ)并記錄路徑的生成NC=1;%迭代計(jì)數(shù)器R_best=zeros(NC_m

5、ax,n);%各代最佳路線L_best=inf.*ones(NC_max,1);%各代最佳路線的長度L_ave=zeros(NC_max,1);%各代路線的平均長度while NC<=NC_max%停止條件之一：達(dá)到最大迭代次數(shù)    %第二步：將m只螞蟻放到n個(gè)城市上    Randpos=;    for i=1:(ceil(m/n)        Randpos=Randpos,randperm(n);  

6、;  end    Tabu(:,1)=(Randpos(1,1:m)'       %第三步：m只螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游    for j=2:n        for i=1:m            visited=Tabu(i,1:(j-1);%已訪問

7、的城市            J=zeros(1,(n-j+1);%待訪問的城市            P=J;%待訪問城市的選擇概率分布            Jc=1;        &

8、#160;   for k=1:n                if length(find(visited=k)=0                    J(Jc)=k;     &#

9、160;              Jc=Jc+1;                end            end       

10、60;    %下面計(jì)算待選城市的概率分布            for k=1:length(J)                P(k)=(Tau(visited(end),J(k)Alpha)*(Eta(visited(end),J(k)Beta);    

11、60;       en*            *=*/(sum(P);            %按概率原則選取下一個(gè)城市            Pcum=cumsum(P);  

12、0;         Select=find(Pcum>=rand);            to_visit=J(Select(1);            Tabu(i,j)=to_visit;        end&#

13、160;   end    if NC>=2        Tabu(1,:)=R_best(NC-1,:);    end       %第四步：記錄本次迭代最佳路線    L=zeros(m,1);    for i=1:m        R=Tab

14、u(i,:);        for j=1:(n-1)            L(i)=L(i)+D(R(j),R(j+1);        end        L(i)=L(i)+D(R(1),R(n);    end  &

15、#160; L_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);    for i=1:m 

16、0;      for j=1:(n-1)            Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i);        end        Delta_Tau(Tabu(i,n),Tabu(i,

17、1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);    end    Tau=(1-Rho).*Tau+Delta_Tau;       %第六步：禁忌表清零    Tabu=zeros(m,n);end%第七步：輸出結(jié)果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)hold onplot(L_ave) function DrawRoute(C,R)%=%  DrawRoute.m%  畫路線圖的子函數(shù)%-%  C    Coordinate        節(jié)點(diǎn)坐標(biāo)，由一個(gè)N×2的矩陣存儲(chǔ)%  R    Route