蟻群算法求解TSP問題

1、HUNAN UNIVERSITY課 程 作 業(yè)課程題目 智能優(yōu)化算法 學(xué)生姓名 李小燕學(xué)生學(xué)號 S131020016專業(yè)班級 計算機科學(xué)與技術(shù)學(xué)院名稱 信息科學(xué)與工程學(xué)院指導(dǎo)老師 楊圣洪2014 年6月 8日蟻群算法求解TSP問題摘要：蟻群算法是一種分布式內(nèi)在并行算法。單個螞蟻的搜索過程是彼此獨立的，易于局部最優(yōu)，通過個體間不斷的信息交流和傳遞有利于發(fā)現(xiàn)較好解；并且該算法是一種正反饋算法。路徑上的信息素濃度較高，將吸引更多的螞蟻沿這條路徑運動，又使得信息素濃度增加，加快了算法的進化過程。本文通過求解TSP問題，通過在特定情況下對路徑進行逐步遍歷比較來降低陷入局部最優(yōu)解的可能性, 找出最優(yōu)解。關(guān)

2、鍵詞：蟻群算法；TSP；信息素；遍歷1. 引言 TSP問題又稱最短路徑問題，還稱為旅行商問題，是一種比較經(jīng)典的 NP 難題，問題描述較簡單，而獲得最優(yōu)解卻十分困難。求解 TSP 問題不僅為其他算法提供了使用平臺，而且算法的優(yōu)劣性能也可通過其求得 TSP 問題的解集來驗證。旅行商問題的經(jīng)典描述為：已知N 個城市及相互間的距離，旅行商從某城市出發(fā)遍歷這 N 個城市后再回到原點，在旅行商每個城市都只訪問一次的前提下確定一條最短路徑。蟻群算法是一種基于種群的啟發(fā)式仿生進化系統(tǒng)。該算法通過模擬自然界的螞蟻覓食過程對目標(biāo)進行搜索，而在搜索過程中人工螞蟻會在其經(jīng)過的路徑上釋放信息素，蟻群依賴于同類散發(fā)在周圍

3、環(huán)境中的特殊物質(zhì)信息素的軌跡來決定自己的去向。當(dāng)某些路徑上走過的螞蟻越來越多時，留下的信息素也會越來越多，以致后螞蟻選擇該路徑的概率也越來越高，從而更增加了該路徑的吸引強度，逐漸形成了一條它們自己事先并未意識到的最短路線。 蟻群算法實現(xiàn)TSP 過程為：將 m 只螞蟻放入到 n 個隨機選擇的城市中，那么每個螞蟻每步的行動是：根據(jù)一定的依據(jù)選擇下一個它還沒有訪問的城市；同時在完成一步（從一個城市到達另一個城市）或者一個循環(huán)（完成對所有 n 個城市的訪問）后，更新所有路徑上的信息素濃度。2. 蟻群算法的數(shù)學(xué)模型（1）、基本參數(shù)、信息素濃度公式、擇路概率設(shè)螞蟻的數(shù)量為m，城市的數(shù)量為n，城市i與城市j

4、之間的距離為dij，t時刻城市i與城市j之間的信息素濃度為tij(t)，初始時刻，各個城市間連接路徑上的信息素濃度相同，不妨記為tij(0)=t0。螞蟻k(k=1,2,.,m)根據(jù)各城市間連接路徑上的信息素濃度，決定其下一個要訪問的城市，設(shè)Pijk(t)表示t時刻，螞蟻k從城市i到城市j的概率，其計算公式為如下：其中：hij(t)為啟發(fā)式函數(shù)，hij(t)=1/dij，表示螞蟻從城市i轉(zhuǎn)移到城市j的期望程序；allowk(k=1,2,m)表示螞蟻k待訪問的城市的集合，開始時allowk為其他n-1城市，隨著時間推進，其中的元素不斷減少，直至為空，表示所有城市訪問完，即遍歷所有城市。a為信息素的

5、重要程度因子，其值越大，轉(zhuǎn)移中起的作用越大b為啟發(fā)函數(shù)的重要程度因子，其值越大，表示啟發(fā)函數(shù)在轉(zhuǎn)移中的作用越大，即螞蟻以較大的概率轉(zhuǎn)移到距離短的城市。螞蟻釋放的信息素會隨時間的推進而減少，設(shè)參數(shù)r(0<r<1)表示信息素的揮發(fā)度，當(dāng)所有螞蟻完成一次循環(huán)后，各個城市間連接路徑上的信息素濃度，需要實時更新。tij(t+1)=(1-r)tij(t)+Dtij，Dtij=其中：Dtijk表示螞蟻k在城市i與城市j的連接路徑上，釋放的信息素濃度Dtij表示所有螞蟻在城市i與城市j的連接路徑上，釋放的信息素濃度。（2）、Dtijk的計算方法Dtijk=其中：Q為常數(shù)，表示螞蟻循環(huán)一次釋放的信息

6、素的總量；dij為第k只螞蟻經(jīng)過路徑的長度，Length；3. 算法實現(xiàn)步驟 1、初始化參數(shù)螞蟻數(shù)量m，信息素重要程度a，啟發(fā)函數(shù)重要程度b，信息素揮發(fā)因子r，信息素釋放總量Q，最大迭代次數(shù)iter_max。獲取各城市之間的距離dij，為了保證啟發(fā)式函數(shù)hij=1/dij能順利進行，對于i=j即自己到自己的距離不能給為0，而是給成一個很小的距離，如10-4或10-5。2、構(gòu)建解空間將各個螞蟻隨機地置于不同出發(fā)點，對每個螞蟻按歸照下式，確定下一城市。3、更新信息素計算各個螞蟻經(jīng)過的路徑長度Lk，記錄當(dāng)前迭代次數(shù)中的最優(yōu)解(即最短路徑)，根據(jù)如下公式更新信息素：tij(t+1)=(1-r)tij(

7、t)+Dtij，Dtij=Dtijk=4、判斷是否終止若沒有到最大次數(shù)，則清空螞蟻經(jīng)過路徑的記錄表，返回步驟2。4. 相關(guān)實驗4.1 實驗內(nèi)容1、訪問我國每個省會城市一次也僅一次的最短路徑，共有31個2、如果采用枚舉法，巡回路徑可能1.326´1032種。3、城市的坐標(biāo)citys，這是直角坐標(biāo)，根據(jù)二個城市的坐標(biāo)值，可以用D=可計算出任意二個城市間的距離。citys = 1304 2312 3639 1315 4177 2244 3712 1399 3488 1535 3326 1556 3238 1229 4196 1004 4312 790 4386 570 3007 1970

8、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 2826 2370 29754.2 實驗代碼 % 清空環(huán)境變量clear allclcload citys_data.mat % 導(dǎo)入數(shù)據(jù)% 計算城市間相互距離n = size(citys,1); %城市的個數(shù)D = zeros(n

9、,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); % 信息素矩陣,全1矩陣Table = zeros(m,n);

10、% 路徑記錄表，全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 % 隨機產(chǎn)生各個螞蟻的起點城市 start = zeros(m,1); %m是螞蟻的個數(shù),m行1列的矩陣，記錄每個螞蟻的城市編號 fo

11、r i = 1:m temp = randperm(n); start(i) = temp(1); end Table(:,1) = start; %路徑記錄表的1列，為每個螞蟻的起點城市 % 構(gòu)建解空間 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的城市就是要訪問的城市 allow = citys_index(allow_inde

12、x); % 待訪問的城市集合 P = allow; for k = 1:length(allow) % 計算城市間轉(zhuǎn)移概率 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); Table(i,j) = target; end end% 結(jié)果顯

13、示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_Rou

14、te(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('城市位置橫坐標(biāo)')ylabel('城市位置

15、縱坐標(biāo)')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('各代最短距離與平均距離對比')4.3 實驗結(jié)果與分析使用不同的蟻群數(shù)量和迭代次數(shù)后求得的最

16、短距離和最短路徑如下所示：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，迭代次數(shù)100最短距離:15601.9195最短路徑:14 12

17、 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 8 9 10 3 18 17 19 24 25 20 21 22

18、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 從以上的實驗結(jié)果可看出，蟻群數(shù)量和迭代次數(shù)對算法的實驗結(jié)果有一定影響，當(dāng)蟻群數(shù)確定時，隨著迭代次數(shù)的增加，最短距離會有所減小，但增加到一定的程度，最短距離將不再變化；當(dāng)