PAGE第13頁共13頁利用蟻群算法求解tsp問題

TSP問題又稱最短路徑問題，還稱為旅行商問題，是一種比較經(jīng)典的

NP

難題，問題描述較簡單，而獲得最優(yōu)解卻十分困難。求解

TSP

問題不僅為其他算法提供了使用平臺，而且算法的優(yōu)劣性能也可通過其求得

TSP

問題的解集來驗證。旅行商問題的經(jīng)典描述為：已知N

個城市及相互間的距離，旅行商從某城市出發(fā)遍歷這

N

個城市后再回到原點，在旅行商每個城市都只訪問一次的前提下確定一條最短路徑。

蟻群算法是一種基于種群的啟發(fā)式仿生進(jìn)化系統(tǒng)。該算法通過模擬自然界的螞蟻覓食過程對目標(biāo)進(jìn)行搜索，而在搜索過程中人工螞蟻會在其經(jīng)過的路徑上釋放信息素，蟻群依賴于同類散發(fā)在周圍環(huán)境中的特殊物質(zhì)—信息素的軌跡來決定自己的去向。當(dāng)某些路徑上走過的螞蟻越來越多時，留下的信息素也會越來越多，以致后螞蟻選擇該路徑的概率也越來越高，從而更增加了該路徑的吸引強度，逐漸形成了一條它們自己事先并未意識到的最短路線。

蟻群算法實現(xiàn)TSP

過程為：將

m

只螞蟻放入到

n

個隨機選擇的城市中，那么每個螞蟻每步的行動是：根據(jù)一定的依據(jù)選擇下一個它還沒有訪問的城市；同時在完成一步（從一個城市到達(dá)另一個城市）或者一個循環(huán)（完成對所有

n

個城市的訪問）后，更新所有路徑上的信息素濃度蟻群算法的實現(xiàn)步驟步驟1初始化相關(guān)參數(shù)如螞蟻的數(shù)目。步驟2將螞蟻隨機或均勻分布到各個城市。步驟3每只螞蟻通過訪問各個城市而形成一個解并在訪問的過程中將已訪問到的城市保留在i中。在城市i中每只螞蟻要從沒有訪問的城市中選擇訪問下一個城市j時須根據(jù)概率公式(1)進(jìn)行選擇如此循環(huán)直到所有的螞蟻訪問完所有的城市。步驟4計算每只螞蟻行走的總路徑長度Lk并保存最優(yōu)解。數(shù)學(xué)模型的建立蟻群算法解決TSP問題的MATLAB實現(xiàn)出動m只螞蟻，每只螞蟻各隨機選擇一條路徑，記為I=[123···m]，長度記為long(I);計算出每條路徑的信息素濃度，記為P(I)=1/long(I)，并進(jìn)行歸一化處理;重新出動m只螞蟻，按如下規(guī)則選擇路徑：1,每只螞蟻都以一個概率p1選擇新路徑(路徑隨機)2,未選擇新路徑的螞蟻以概率P(I)選擇路徑I；3,所有螞蟻都以一個小概率p2對自己的路徑進(jìn)行局部變化；更新所有路徑，計算出每條路徑的信息素濃度；重復(fù)上述步驟，直至僅剩一條路徑。Matlab算法實現(xiàn)function[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)

%%=========================================================================

%%ACATSP.m

%%AntColonyAlgorithmforTravelingSalesmanProblem

%%ChengAihua,PLAInformationEngineeringUniversity,ZhengZhou,China

%%Email:aihuacheng@

%%Allrightsreserved

%%

%%主要符號說明

%%Cn個城市的坐標(biāo)，n×2的矩陣

%%NC_max最大迭代次數(shù)

%%m螞蟻個數(shù)

%%Alpha表征信息素重要程度的參數(shù)

%%Beta表征啟發(fā)式因子重要程度的參數(shù)

%%Rho信息素蒸發(fā)系數(shù)

%%Q信息素增加強度系數(shù)

%%R_best各代最佳路線

%%L_best各代最佳路線的長度

%%=========================================================================第一步：變量初始化

n=size(C,1);%n表示問題的規(guī)模（城市個數(shù)）

D=zeros(n,n);%D表示完全圖的賦權(quán)鄰接矩陣

fori=1:n

forj=1:n

ifi~=j

D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;

else

D(i,j)=eps;

end

D(j,i)=D(i,j);

end

end

Eta=1./D;%Eta為啟發(fā)因子，這里設(shè)為距離的倒數(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);%各代路線的平均長度whileNC<=NC_max%停止條件之一：達(dá)到最大迭代次數(shù)

第二步：將m只螞蟻放到n個城市上

Randpos=[];

fori=1:(ceil(m/n))

Randpos=[Randpos,randperm(n)];

end

Tabu(:,1)=(Randpos(1,1:m))';第三步：m只螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游

forj=2:n

fori=1:m

visited=Tabu(i,1:(j-1));%已訪問的城市

J=zeros(1,(n-j+1));%待訪問的城市

P=J;%待訪問城市的選擇概率分布

Jc=1;

fork=1:n

iflength(find(visited==k))==0

J(Jc)=k;

Jc=Jc+1;

end

end

%下面計算待選城市的概率分布

fork=1:length(J)

P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);

end

P=P/(sum(P));

%按概率原則選取下一個城市

Pcum=cumsum(P);

Select=find(Pcum>=rand);

to_visit=J(Select(1));

Tabu(i,j)=to_visit;

end

end

ifNC>=2

Tabu(1,:)=R_best(NC-1,:);

end第四步：記錄本次迭代最佳路線

L=zeros(m,1);

fori=1:m

R=Tabu(i,:);

forj=1:(n-1)

L(i)=L(i)+D(R(j),R(j+1));

end

L(i)=L(i)+D(R(1),R(n));

end

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);

fori=1:m

forj=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,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)

holdon

plot(L_ave)functionDrawRoute(C,R)

%%=========================================================================

%%DrawRoute.m

%%畫路線圖的子函數(shù)

%%

%%CCoordinate節(jié)點坐標(biāo)，由一個N×2的矩陣存儲

%%RRoute路線

%%=========================================================================N=length(R);

scatter(C(:,1),C(:,2));

holdon

plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])

holdon

forii=2:N

plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])

holdon

end代碼運行：現(xiàn)在輸入31個城市的坐標(biāo)進(jìn)行計算設(shè)置初始參數(shù)如下：

m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;

31城市坐標(biāo)為：

[1304,2312;

3639,1315;

4177,2244;

3712,1399;

3488,1535;

3326,1556;

3238,1229;

4196,1004;

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,2367;

3394,2643;

3439,3201;

2935,3240;

3140,3550;

2545,2357;

2778,2826;

2370,2975];運行后得到15602的巡游路徑，路線圖和收斂曲線如下：87，791，83)(83，46)(71，44)(64，60)(68，58)(83，69)(87，76)(74，78)(71，71)(58，69)(54，6