蟻群算法求解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(t)，初始時刻，各個城市間連接路徑上的信息素濃度相同，不妨記為tij(0)=t0。螞蟻k(k=1,2,.,m)根據(jù)各城市間連接路徑上的信息素濃度，決定其下一個要訪問的城市，設Pijk(t)表示t時刻，螞蟻k從城市i到城市j的概率，其計算公式為如下：其中：hij(

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

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

4、 1535 3326 1556 3238 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% 計算城市間相互距離n

5、= size(citys,1); %城市的個數(shù)D = zeros(n,n); %n行n列的矩陣，即任意二個城市之間的距離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ā)因子Q = 1; % 常系數(shù)Eta = 1./D; % 啟發(fā)函數(shù)Tau = ones(n,n)

6、; % 信息素矩陣,全1矩陣Table = 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 <= iter_max % 隨機產生各個螞蟻的起點城市 start = zeros(m,1

7、); %m是螞蟻的個數(shù),m行1列的矩陣，記錄每個螞蟻的城市編號 for i = 1:m temp = randperm(n); start(i) = temp(1); end Table(:,1) = start; %路徑記錄表的1列，為每個螞蟻的起點城市 % 構建解空間 citys_index = 1:n; % 逐個螞蟻路徑選擇 for i = 1:m % 逐個城市路徑選擇 for j = 2:n tabu = Table(i,1:(j - 1); % 已訪問的城市集合(禁忌表) allow_index = ismember(citys_index,tabu);%不是tabu的城市就是要訪問

8、的城市 allow = citys_index(allow_index); % 待訪問的城市集合 P = allow; for k = 1:length(allow) % 計算城市間轉移概率 P(k) = Tau(tabu(end),allow(k)alpha * Eta(tabu(end),allow(k)beta; end P = P/sum(P);%規(guī)一化 % 輪盤賭法選擇下一個訪問城市 Pc = cumsum(P);%依次累加，是實現(xiàn)輪盤賭法選擇的方法 target_index = find(Pc >= rand); target = allow(target_index(1);

9、 Table(i,j) = target; end end% 結果顯示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(Sh

10、ortest_Route,2);citys(Shortest_Route(1),2),'o-');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),' 起點');text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),' 終點');xlabel(

11、'城市位置橫坐標')ylabel('城市位置縱坐標')title('蟻群算法優(yōu)化路徑(最短距離:' num2str(Shortest_Length) ')')figure(2)plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:')legend('最短距離','平均距離')xlabel('迭代次數(shù)')ylabel('距離')title('各代最短距離與平均距離對比&#

12、39;)end5.結果與分析使用不同的蟻群數(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.7648最短路徑: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

13、，迭代次數(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 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

14、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ù)量和迭代次數(shù)對算法的實驗結果有一定影響，當蟻群數(shù)確定時，隨著迭代次數(shù)的增加，最短距離會有所減小，但增加到一定的程度，最短距離將不再變化；當?shù)螖?shù)不變，隨著蟻群數(shù)