蟻群算法求解TSP問題

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

2、ij(t)=1/dij，表示螞蟻從城市i轉(zhuǎn)移到城市j的期望程序；allowk(k=1,2,m)表示螞蟻k待訪問的城市的集合，開始時(shí)allowk為其他n-1城市，隨著時(shí)間推進(jìn)，其中的元素不斷減少，直至為空，表示所有城市訪問完，即遍歷所有城市。a為信息素的重要程度因子，其值越大，轉(zhuǎn)移中起的作用越大b為啟發(fā)函數(shù)的重要程度因子，其值越大，表示啟發(fā)函數(shù)在轉(zhuǎn)移中的作用越大，即螞蟻以較大的概率轉(zhuǎn)移到距離短的城市。螞蟻釋放的信息素會隨時(shí)間的推進(jìn)而減少，設(shè)參數(shù)r(0r1)表示信息素的揮發(fā)度，當(dāng)所有螞蟻完成一次循環(huán)后，各個(gè)城市間連接路徑上的信息素濃度，需要實(shí)時(shí)更新。tij(t+1)=(1-r)tij(t)+Dti

3、j，Dtij=其中：Dtijk表示螞蟻k在城市i與城市j的連接路徑上，釋放的信息素濃度Dtij表示所有螞蟻在城市i與城市j的連接路徑上，釋放的信息素濃度。（2）、Dtijk的計(jì)算方法Dtijk=其中：Q為常數(shù)，表示螞蟻循環(huán)一次釋放的信息素的總量；dij為第k只螞蟻經(jīng)過路徑的長度，Length；4. 相關(guān)程序1、訪問每個(gè)城市一次也僅一次的最短路徑，共有30個(gè)2、城市的坐標(biāo)citys，這是直角坐標(biāo)，根據(jù)二個(gè)城市的坐標(biāo)值，可以用D=可計(jì)算出任意二個(gè)城市間的距離。citys = 1304 2312 3639 1315 4177 2244 3712 1399 3488 1535 3326 1556 32

4、38 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 28263、代碼clear allclcload citys_data.mat% 計(jì)算城市間相互距離n = size(citys,1); %

5、城市的個(gè)數(shù)D = zeros(n,n); %n行n列的矩陣，即任意二個(gè)城市之間的距離for i = 1:n for j = 1:n if i = j D(i,j) = sqrt(sum(citys(i,:) - citys(j,:).2); else D(i,j) = 1e-4; end end end% 初始化參數(shù)m = 50; % 螞蟻數(shù)量alpha = 1; % 信息素重要程度因子beta = 5; % 啟發(fā)函數(shù)重要程度因子rho = 0.1; % 信息素?fù)]發(fā)因子Q = 1; % 常系數(shù)Eta = 1./D; % 啟發(fā)函數(shù)Tau = ones(n,n); % 信息素矩陣,全1矩陣Tabl

6、e = zeros(m,n); % 路徑記錄表，全0矩陣，每只螞蟻依次走過的城市iter = 1; % 迭代次數(shù)初值iter_max = 200; % 最大迭代次數(shù) Route_best = zeros(iter_max,n); % 各代最佳路徑 Length_best = zeros(iter_max,1); % 各代最佳路徑的長度 Length_ave = zeros(iter_max,1); % 各代路徑的平均長度 % 迭代尋找最佳路徑while iter = rand); target = allow(target_index(1); Table(i,j) = target; end

7、end% 結(jié)果顯示Shortest_Length,index = min(Length_best);Shortest_Route = Route_best(index,:);disp(最短距離: num2str(Shortest_Length);disp(最短路徑: num2str(Shortest_Route Shortest_Route(1);% 繪圖figure(1)plot(citys(Shortest_Route,1);citys(Shortest_Route(1),1),. citys(Shortest_Route,2);citys(Shortest_Route(1),2),o-)

8、;grid onfor i = 1:size(citys,1) text(citys(i,1),citys(i,2), num2str(i);endtext(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2), 起點(diǎn));text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2), 終點(diǎn));xlabel(城市位置橫坐標(biāo))ylabel(城市位置縱坐標(biāo))title(蟻群算法優(yōu)化路徑(最短距離: num2str(Shortest_Length) )figure(2)plot(1:i

9、ter_max,Length_best,b,1:iter_max,Length_ave,r:)legend(最短距離,平均距離)xlabel(迭代次數(shù))ylabel(距離)title(各代最短距離與平均距離對比)end5.結(jié)果與分析使用不同的蟻群數(shù)量和迭代次數(shù)后求得的最短距離和最短路徑如下所示：1. 蟻群數(shù)50，迭代次數(shù)200最短距離:15601.9195最短路徑:14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 1 15 14 2. 蟻群數(shù)50，迭代次數(shù)100 最短距離:15972.7

10、648最短路徑:1 15 13 12 14 29 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 13. 蟻群數(shù)100，迭代次數(shù)100最短距離:15601.9195最短路徑:14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 1 15 144. 蟻群數(shù)50，迭代次數(shù)300最短距離:15601.9195最短路徑:1 15 14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17

11、19 24 25 20 21 22 26 28 27 30 31 29 15. 蟻群數(shù)100，迭代次數(shù)200最短距離:15601.9195最短路徑:14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 1 15 146. 蟻群數(shù)100，迭代次數(shù)300最短距離:15553.0468最短路徑:10 9 8 4 2 5 6 7 13 12 14 15 1 29 31 30 27 28 26 21 22 18 3 17 19 24 20 25 11 23 16 107. 蟻群數(shù)150，迭代次數(shù)300最短距離:15601.9195最短路徑:1 15 14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 1 從以上的實(shí)驗(yàn)結(jié)果可看出，蟻群數(shù)量和迭代次數(shù)對算法的實(shí)驗(yàn)結(jié)果有一定影響，當(dāng)蟻群數(shù)確定時(shí)，隨著迭代次數(shù)的增加，最短距離會有所減小，但增加到一定的程度，最短距離將不再變化；當(dāng)?shù)螖?shù)不變，隨著蟻群數(shù)量的增加，最短距離也有一定的改進(jìn)。但增加到一定程度，最短距離還可能有所增加。6.