function?[R_bestL_bestL_aveShortest_RouteShortest_Length]=ACATSP（CNC_maxmAlphaBetaRhoQ）

%%-------------------------------------------------------------------------

%%?主要符號說明

%%?C?n個城市的坐標，n×2的矩陣

%%?NC_max?最大迭代次數

%%?m?螞蟻個數

%%?Alpha?表征信息素重要程度的參數

%%?Beta?表征啟發式因子重要程度的參數

%%?Rho?信息素蒸發系數

%%?Q?信息素增加強度系數

%%?R_best?各代最佳路線

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

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



%%第一步：變量初始化

n=size（C1）;%n表示問題的規模（城市個數）

D=zeros（nn）;%D表示完全圖的賦權鄰接矩陣

for?i=1:n

for?j=1:n

if?i~=j

D（ij）=（（C（i1）-C（j1））^2+（C（i2）-C（j2））^2）^0.5;

else

D（ij）=eps;??????%i=j時不計算，應該為0，但后面的啟發因子要取倒數，用eps（浮點相對精度）表示

end

D（ji）=D（ij）;???%對稱矩陣

end

end

Eta=1./D;??????????%Eta為啟發因子，這里設為距離的倒數

Tau=ones（nn）;?????%Tau為信息素矩陣

Tabu=zeros（mn）;???%存儲并記錄路徑的生成

NC=1;???????????????%迭代計數器，記錄迭代次數

R_best=zeros（NC_maxn）;???????%各代最佳路線

L_best=inf.*ones（NC_max1）;???%各代最佳路線的長度

L_ave=zeros（NC_max1）;????????%各代路線的平均長度



while?NC<=NC_max????????%停止條件之一：達到最大迭代次數，停止

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

Randpos=[];???%隨即存取

for?i=1:（ceil（m/n））

Randpos=[Randposrandperm（n）];

end

Tabu（:1）=（Randpos（11:m））‘;????%此句不太理解？



%%第三步：m只螞蟻按概率函數選擇下一座城市，完成各自的周游

for?j=2:n?????%所在城市不計算

for?i=1:m?????

visited=Tabu（i1:（j-1））;?%記錄已訪問的城市，避免重復訪問

J=zeros（1（n-j+1））;???????%待訪問的城市

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

Jc=1;

for?k=1:n

if?length（find（visited==k））==0???%開始時置0

J（Jc）=k;

Jc=Jc+1;?????????????????????????%訪問的城市個數自加1

end

end

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

for?k=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）;?????%cumsum，元素累加即求和

Select=find（Pcum>=rand）;?%若計算的概率大于原來的就選擇這條路線

to_visit=J（Select（1））;

Tabu（ij）=to_visit;

end

end

if?NC>=2

Tabu（1:）=R_best（NC-1:）;

end



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

L=zeros（m1）;?????%開始距離為0，m*1的列向量

for?i=1:m

R=Tabu（i:）;

for?j=1:（n-1）

L（i）=L（i）+D（R（j）R（j+1））;????%原距離加上第j個城市到第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（nn）;????????%開始時信息素為n*n的0矩陣

for?i=1:m

for?j=1:（n-1）

Delta_Tau（Tabu（ij）Tabu（ij+1））=Delta_Tau（Tabu（ij）Tabu（ij+1））+Q/L（i）;???????????

%此次循環在路徑（i，j）上的信息素增量

end

Delta_Tau（Tabu（in）Tabu（i1））=Delta_Tau（Tabu（in）Tabu（i1））+Q/L（i）;

%此次循環在整個路徑上的信息素增量

end

Tau=（1-Rho）.*Tau+Delta_Tau;?%考慮信息素揮發，更新后的信息素

%%第六步：禁忌表清零

Tabu=zeros（mn）;?????????????%%直到最大迭代次數

end

%%第七步：輸出結果

Pos=find（L_best==min（L_best））;?%找到最佳路徑（非0為真）

Shortest_Route=R_best（Pos（1）:）?%最大迭代次數后最佳路徑

Shortest_Length=L_best（Pos（1））?%最大迭代次數后最短距離

subplot（121）??????????????????%繪制第一個子圖形

DrawRoute（CShortest_Route）?????%畫路線圖的子函數

subplot（122）??????????????????%繪制第二個子圖形

plot（L_best）

hold?on?????????????????????????%保持圖形

plot（L_ave‘r‘）

title（‘平均距離和最短距離‘）?????%標題

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????3581??2010-04-21?15:41??蟻群算法實例\ACATSP.m

?????文件????????590??2010-04-21?15:31??蟻群算法實例\DrawRoute.m

?????文件????????753??2010-04-21?15:39??蟻群算法實例\main.m

?????目錄??????????0??2010-04-21?20:22??蟻群算法實例

-----------?---------??----------?-----??----

?????????????????4924????????????????????4