function?[R_bestL_bestL_aveShortest_RouteShortest_Length]=aca_tsp（CNC_maxmAlphaBetaRhoQ）
%%??主要符號說明
%?C?n個城市的坐標，n*2的矩陣
%?NC_max：蟻群算法MATLAB程序最大迭代次數
%?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;
????????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（1n-j+1）;??%?待訪問的城市
????????????P=J;??%?待訪問城市的選擇概率分布
????????????Jc=1;
????????????for?k=1:n
????????????????if?length（find（visited==k））==0
????????????????????J（Jc）=k;
????????????????????Jc=Jc+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）;??%?累加求和
????????????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）;
????for?i=1:m
????????R=Tabu（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
????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）;
????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）;
????????????%?此次循環在路徑?（ij）?上的信息素增量
????????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



NC
%?輸出結果
Pos=find（L_best==min（L_best））;
Shortest_Route=R_best（Pos（1）:）
Shortest_Length=L_best（Pos（1））
subplot（121）
draw_route（CShortest_Route）??%?畫路線圖
subplot（122）
plot（L_best）
hold?on
plot（L_ave‘r‘）
title（‘平均距離和最短距離‘）

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2016-07-02?16:32??ACO_TSP\
?????文件????????3196??2016-06-13?15:15??ACO_TSP\aco_tsp.m
?????文件?????????274??2016-06-11?15:15??ACO_TSP\draw_route.m
?????文件?????????690??2016-07-02?16:31??ACO_TSP\test_aco_tsp.m