解决蚁群算法TSP问题程序
蚁群算法用于求解TSP经过模拟测试，发现该程序的优化效率和鲁棒性都很好。
这与应用于无线多媒体传感器网络路由算法的蚁群算法非常相似。
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length] ACATSP C,NC_max,m,Alpha,Beta,Rho,Q %% %%? 主要符号说明% C n一个城市的坐标，n×2的矩阵%% NC_max?? 最大迭代次数% m 蚂蚁的数量%%% Alpha???表征信息素重要性的参数% Beta??? 表征启发因子重要性参数%% Rho????信息素蒸发系数% Q 信息素增加强度系数% R_best?? 各代最佳路线% L_best?? 各代最佳路线长度% %%第一步:变量初始化n size *,1 ;%*表示问题的规模(城市数量)* zeros n,n ;%D授权邻接矩阵表示完矩阵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 D i,j eps; end D j,i D i,j ; endendEta 1./D;%Eta为了启发因素，这里是距离的倒数Tau ones n,n ;%Tau信息素矩阵Tabu zeros m,n ;存储和记录生成路径的%NC 1；%迭代计数器R_best zeros NC_max,n ;%各代最佳路线L_best inf.*ones NC_max,1 ;各代最佳路线长度%L_ave zeros NC_max,1 ;各代路线平均长度%while NC NC_max%停止条件之一:达到最大迭代次数 第二步:把m只蚂蚁放在n个城市 Randpos []; for i 1: ceil m/n Randpos [Randpos,randperm n ]; end Tabu :,1 Randpos 1,1:m '; 第三步:%%%:m蚂蚁根据概率函数选择下一个城市，完成自己的周游 for j 2:n for i 1:m visited Tabu i,1: j-1 ;已访问的城市% J zeros 1, n-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 ; en* * */ sum P ; 按概率原则选择下一个城市 Pcum cumsum P ; Select find Pcum rand ; to_visit J Select 1 ; Tabu i,j to_visit; end end if NC 2 Tabu 1,: R_best NC-1,: ; end 第四步：记录迭代的最佳路线 L zeros m,1 ; 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 n,n ; for i 1:m 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,1 Delta_Tau Tabu i,n ,Tabu i,1 Q/L i ; end Tau 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