蟻群算法求解TSP問題

1、廣東工業(yè)大學課程作業(yè)課程題目基于ACO算法求解城市tsp學生姓名朱美霞學生學號2111405091專業(yè)班級計算機技術2015年2月15日1.AOC算法的數(shù)學模型(1)、基本參數(shù)、信息素濃度公式、擇路概率設螞蟻的數(shù)量為m,城市的數(shù)量為n,城市i與城市j之間的距離為dij,t時刻城市i與城市j之間的信息素濃度為tij，初始時刻，各個城市間連接路徑上的信息素濃度相同，不妨記為tj(0)=t0。螞蟻k(k=1,2,.,m)根據(jù)各城市間連接路徑上的信息素濃度，決定其下一個要訪問的城市，設Pijk(t)表示t時刻，螞蟻k從城市i到城市j的概率，其計算公式為如下：sallowksallowktij(t):M

2、t)：Rk='、3：j(t)1|s三allow0其中：%(t)為啟發(fā)式函數(shù)，/(t)=1/dij,表示螞蟻從城市i轉移到城市j的期望程序；allowk(k=1,2，,m)表示螞蟻k待訪問的城市的集合，開始時allowk為其他n-1城市，隨著時間推進，其中的元素不斷減少，直至為空，表示所有城市訪問完，即遍歷所有城市。二為信息素的重要程度因子，其值越大，轉移中起的作用越大P為啟發(fā)函數(shù)的重要程度因子，其值越大，表示啟發(fā)函數(shù)在轉移中的作用越大，即螞蟻以較大的概率轉移到距離短的城市。螞蟻釋放的信息素會隨時間的推進而減少，設參數(shù)P(0<P<1)表示信息素的揮發(fā)度，當所有螞蟻完成一次循環(huán)

3、后，各個城市間連接路徑上的信息素濃度，需要實時更新。ntij(t+1)=(1-P)tij(t)+5ij,%=£箋k土其中：Atijk表示螞蟻k在城市i與城市j的連接路徑上，釋放的信息素濃度tij表示所有螞蟻在城市i與城市j的連接路徑上，釋放的信息素濃度。(2)、Atijk的計算方法k；Q/Lk第k只螞蟻從城市i訪問城市jj=10其他其中：Q為常數(shù)，表示螞蟻循環(huán)一次釋放的信息素的總量；dij為第k只螞蟻經過路徑的長度，Length；4.相關程序1、訪問每個城市一次也僅一次的最短路徑，共有30個2、城市的坐標citys,這是直角坐標，根據(jù)二個城市的坐標值，可以用D=J(x1x2)2+(y

4、1-y2)2可計算出任意二個城市間的距離。citys=1304231236391315417722443712139934881535332615563238122941961004431279043865703007197025621756278814912381167613326953715167839182179406123703780221236762578402928384263293134291908350723673394264334393201293532403140355025452357277828263、代碼clearallclcloadcitys_data.mat%計算

5、城市間相互距離n=size(citys,1);%市的個數(shù)D=zeros(n,n);%n行n列的矩陣，即任意二個城市之間的距離fori=1:nforj=1:nifi=jD(i,j)=sqrt(sum(citys(i,:)-citys(j,:).A2);elseD(i,j)=1e-4;endendend%初始化參數(shù)m=50;alpha=1;beta=5;rho=0.1;Q=1;Eta=1./D;Tau=ones(n,n);Table=zeros(m,n);依次走過的城市iter=1;iter_max=200;Route_best=zeros(iter_max,n);Length_best=zero

6、s(iter_max,1);%螞蟻數(shù)量%信息素重要程度因子%啟發(fā)函數(shù)重要程度因子%信息素揮發(fā)因子%常系數(shù)%啟發(fā)函數(shù)%信息素矩陣，全1矩陣%路徑記錄表，全0矩陣，每只螞蟻%迭代次數(shù)初值%最大迭代次數(shù)%各代最佳路徑%各代最佳路徑的長度%各代路徑的平均長度Length_ave=zeros(iter_max,1);%迭代尋找最佳路徑whileiter<=itermax%隨機產生各個螞蟻的起點城市start=zeros(m,1);%m是螞蟻的個數(shù)，m行1列的矩陣，記錄每個螞蟻的城市編號fori=1:mtemp=randperm(n);start(i)=temp(1);endTable(:,1)=s

7、tart;%路徑記錄表的1歹！J,為每個螞蟻的起點城市%構建解空間citys_index=1:n;%逐個螞蟻路徑選擇fori=1:m%逐個城市路徑選擇forj=2:ntabu=Table(i,1:(j-1);%已訪問的城市集合(禁忌表)allow_index=ismember(citys_index,tabu);%是tabu的城市就是要訪問的城市allow=citys_index(allow_index);%待訪問的城市集合P=allow;fork=1:length(allow)%計算城市間轉移概率P(k)=Tau(tabu(end),allow(k)Aalpha*Eta(tabu(end),

8、allow(k)Abeta;endP=P/sum(P);%B一化%輪盤賭法選擇下一個訪問城市Pc=cumsum(P);%依次累加，是實現(xiàn)輪盤賭法選擇的方法target_index=find(Pc>=rand);target=allow(target_index(1);Table(i,j)=target;endend%結果顯示Shortest_Length,index=min(Length_best);Shortest_Route=Route_best(index,:);disp('最短距離:'num2str(Shortest_Length);disp('最短路徑：

9、'num2str(Shortest_RouteShortest_Route(1);%繪圖figure(1)plot(citys(Shortest_Route,1);citys(Shortest_Route(1),1),citys(Shortest_Route,2);citys(Shortest_Route(1),2),'o-');gridonfori=1:size(citys,1)text(citys(i,1),citys(i,2),''num2str(i);endtext(citys(Shortest_Route(1),1),citys(Shortes

10、t_Route(1),2),'起點');text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),'終點');xlabel('城市位置橫坐標')ylabel('城市位置縱坐標')title('蟻群算法優(yōu)化路徑(最短距離：'num2str(Shortest_Length)')')figure(2)plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:&

11、#39;)legend(最短距離','平均距離')xlabel('迭代次數(shù))ylabel('距離')t田e（'各代最短距離與平均距離對比'）end5.結果與分析使用不同的蟻群數(shù)量和迭代次數(shù)后求得的最短距離和最短路徑如下所示：1 .蟻群數(shù)50,迭代次數(shù)200最短距離:15601.9195最短路徑：14121311231656724891031817192425202122262827303129115142 .蟻群數(shù)50,迭代次數(shù)100最短距離:15972.7648最短路徑：11513121429112316567248910318

12、17192425202122262827303113 .蟻群數(shù)100,迭代次數(shù)100最短距離:15601.9195最短路徑：14121311231656724891031817192425202122262827303129115144 .蟻群數(shù)50,迭代次數(shù)300最短距離:15601.9195最短路徑：1151412131123165672489103181719242520212226282730312915 .蟻群數(shù)100,迭代次數(shù)200最短距離:15601.9195最短路徑：14121311231656724891031817192425202122262827303129115146 .蟻群數(shù)100,迭代次數(shù)300最短距離:15553.0468最短路徑：10984256713121415129313027282621221831719242025112316107 .蟻群數(shù)150,迭代次數(shù)300最短距離:15601.9195最短路徑：11514121311231656724810318171924252021222628273031291從以上的實驗結果可看出，蟻群數(shù)量和迭代次數(shù)對算法的實驗結果有一定影響，當蟻群數(shù)確定時，隨著迭代次數(shù)的增加，最短距離會有所減小，但增加到一定的程度，最短距離將不再變化；當?shù)螖?shù)不變，隨著蟻群數(shù)量的增加，最短距離也有一定的改進。但增