基于MATLAB的蟻群算法解決旅行商問題 (附帶源程序、仿真)

1、摘 要：旅行商問題的傳統(tǒng)求解方法是遺傳算法，但此算法收斂速度慢，并不能獲得問題的最優(yōu)化解。蟻群算法是受自然界中蟻群搜索食物行為啟發(fā)而提出的一種智能優(yōu)化算法，通過介紹蟻群覓食過程中基于信息素的最短路徑的搜索策略，給出基于MATLAB的蟻群算法在旅行商問題中的應(yīng)用，對(duì)問題求解進(jìn)行局部?jī)?yōu)化。經(jīng)過計(jì)算機(jī)仿真結(jié)果表明，這種蟻群算法對(duì)求解旅行商問題有較好的改進(jìn)效果。關(guān)鍵詞：蟻群算法；旅行商問題；MATLAB；優(yōu)化一、意義和目標(biāo) 旅行商問題是物流領(lǐng)域中的典型問題，它的求解具有十分重要的理論和現(xiàn)實(shí)意義。采用一定的物流配送方式，可以大大節(jié)省人力物力，完善整個(gè)物流系統(tǒng)。 已被廣泛采用的遺傳算法是旅行商問題的傳統(tǒng)求

2、解方法，但遺傳算法收斂速度慢，具有一定的缺陷。本文采用蟻群算法，充分利用蟻群算法的智能性，求解旅行商問題，并進(jìn)行實(shí)例仿真。進(jìn)行仿真計(jì)算的目標(biāo)是，該算法能夠獲得旅行商問題的優(yōu)化結(jié)果，平均距離和最短距離。2、 國(guó)內(nèi)外研究現(xiàn)狀仿生學(xué)出現(xiàn)于20世紀(jì)50年代中期，人們從生物進(jìn)化機(jī)理中受到啟發(fā)，提出了遺傳算法、進(jìn)化規(guī)劃、進(jìn)化策略等許多用以解決復(fù)雜優(yōu)化問題的新方法。這些以生物特性為基礎(chǔ)的演化算法的發(fā)展及對(duì)生物群落行為的發(fā)現(xiàn)引導(dǎo)研究人員進(jìn)一步開展了對(duì)生物社會(huì)性的研究，從而出現(xiàn)了基于群智能理論的蟻群算法，并掀起了一股研究的熱潮。20世紀(jì)90年代意大利科學(xué)家M.Dorigo M最早提出了蟻群優(yōu)化算法螞蟻系統(tǒng)（An

3、t system, AS），在求解二次分配、圖著色問題、車輛調(diào)度、集成電路設(shè)計(jì)以及通信網(wǎng)絡(luò)負(fù)載問題的處理中都取得了較好的結(jié)果。旅行商問題（TSP, Traveling Salesman Problem）被認(rèn)為是一個(gè)基本問題，是在1859年由威廉漢密爾頓爵士首次提出的。所謂TSP問題是指：有N個(gè)城市，要求旅行商到達(dá)每個(gè)城市各一次，且僅一次，并回到起點(diǎn)，且要求旅行路線最短。這是一個(gè)典型的優(yōu)化問題，對(duì)一個(gè)具有中等頂點(diǎn)規(guī)模的圖來說，精確求解也是很復(fù)雜的，計(jì)算量隨著城市個(gè)數(shù)的增加而呈指數(shù)級(jí)增長(zhǎng)，即屬于所謂的 NP問題。TSP在工程領(lǐng)域有著廣泛的應(yīng)用 ，并常作為比較算法性能的標(biāo)志。如網(wǎng)絡(luò)通訊、貨物運(yùn)輸、電

4、氣布線、管道鋪設(shè)、加工調(diào)度、專家系統(tǒng)、柔性制造系統(tǒng)等方面，都是TSP廣泛應(yīng)用的領(lǐng)域。求解算法包括貪婪法（GM）、極小代數(shù)法（MA）、模擬退火法（SA）和遺傳算法（GA）等。而應(yīng)用蟻群算法求解旅行商問題是近年來研究的新方向，由于其并行性與分布性，特別適用于大規(guī)模啟發(fā)式搜索，實(shí)驗(yàn)結(jié)果證明了其可行性和有效性。三、蟻群系統(tǒng)基本原理 在螞蟻群找到食物時(shí)，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素（phero-mone）。當(dāng)它們碰到一個(gè)還沒有走過的路口時(shí)，就隨機(jī)地挑選一條路徑前行。與此同時(shí)釋放出與路徑長(zhǎng)度有關(guān)的信息素。路徑越長(zhǎng)，釋放的激素濃度越低。

5、當(dāng)后來的螞蟻再次碰到這個(gè)路口的時(shí)候，選擇激素濃度較高路徑概率就會(huì)相對(duì)較大。這樣形成了一個(gè)正反饋。最優(yōu)路徑上的激素濃度越來越大，而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。在整個(gè)尋徑過程中，雖然單個(gè)螞蟻的選擇能力有限，但是通過激素的作用，整個(gè)蟻群之間交換著路徑信息，最終找出最優(yōu)路徑。4、 基于MATLAB的蟻群算法求解旅行商問題TSP問題描述如下：設(shè)有n個(gè)城市C=（1，2,.,n），任意兩個(gè)城市i，j之間的距離為dij ，求一條經(jīng)過每個(gè)城市的路徑=（1），（2），.，（n），使得距離最小。主要符號(hào)說明 C n個(gè)城市的坐標(biāo)，n2的矩陣 NC_max 最大迭代次數(shù) m

6、 螞蟻個(gè)數(shù) Alpha 表征信息素重要程度的參數(shù) Beta 表征啟發(fā)式因子重要程度的參數(shù) Rho 信息素蒸發(fā)系數(shù) Q 信息素增加強(qiáng)度系數(shù) R_best 各代最佳路線 L_best 各代最佳路線的長(zhǎng)度 求解TSP問題的螞蟻算法中，每只螞蟻是一個(gè)獨(dú)立的用于構(gòu)造路線的過程，若干螞蟻過程之間通過自適應(yīng)的信息素值來交換信息，合作求解，并不斷優(yōu)化。這里的信息素值分布式存儲(chǔ)在圖中，與各弧相關(guān)聯(lián)。螞蟻算法求解TSP問題的過程如下：（1）首先初始化，設(shè)迭代的次數(shù)為NC。初始化NC=0（2）將m個(gè)螞蟻置于n個(gè)頂點(diǎn)上（3）m只螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游每個(gè)螞蟻按照狀態(tài)變化規(guī)則逐步地構(gòu)造一個(gè)解，即生

7、成一條回路。螞蟻的任務(wù)是訪問所有的城市后返回到起點(diǎn)，生成一條回路。設(shè)螞蟻k當(dāng)前所在的頂點(diǎn)為i，那么，螞蟻k由點(diǎn)i向點(diǎn)j移動(dòng)要遵循規(guī)則而不斷遷移，按不同概率來選擇下一點(diǎn)。（4）記錄本次迭代最佳路線（5）全局更新信息素值應(yīng)用全局信息素更新規(guī)則來改變信息素值。當(dāng)所有m個(gè)螞蟻生成了m個(gè)解，其中有一條最短路徑是本代最優(yōu)解，將屬于這條路線上的所有弧相關(guān)聯(lián)的信息素值進(jìn)行更新。全局信息素更新的目的是在最短路線上注入額外的信息素，即只有屬于最短路線的弧上的信息素才能得到加強(qiáng)，這是一個(gè)正反饋的過程，也是一個(gè)強(qiáng)化學(xué)習(xí)的過程。在圖中各弧上，伴隨著信息素的揮發(fā)，全局最短路線上各弧的信息素值得到增加。（6） 終止若終止條

8、件滿足，則結(jié)束；否則NC=NC+1，轉(zhuǎn)入步驟（2）進(jìn)行下一代進(jìn)化。終止條件可指定進(jìn)化的代數(shù)，也可限定運(yùn)行時(shí)間，或設(shè)定最短路長(zhǎng)的下限。（7）輸出結(jié)果5、 數(shù)據(jù)實(shí)驗(yàn)及結(jié)果 通過計(jì)算機(jī)仿真，得出旅行商問題優(yōu)化結(jié)果和平均距離和最短距離，如圖所示：6、 分析與總結(jié) 本文設(shè)計(jì)了一種基于MATLAB實(shí)現(xiàn)的蟻群算法，用以求解組合優(yōu)化難題中的典型代表旅行商問題。對(duì)30個(gè)城市旅行商問題進(jìn)行了測(cè)試，所得結(jié)果能達(dá)到優(yōu)化作用，實(shí)現(xiàn)了本文的研究目標(biāo)。 經(jīng)過對(duì)旅行商問題的深入理解，得到了能解決問題的基本數(shù)學(xué)模型，然后設(shè)計(jì)算法的基本思想，技術(shù)路線，最后編碼。在多次調(diào)試，修改后，本算法成功運(yùn)行，并實(shí)現(xiàn)了最初的設(shè)定目標(biāo)。另外，M

9、ATLAB具有豐富的繪圖函數(shù)，對(duì)于繪圖十分方便，這是選擇MATLAB解決TSP問題的算法編寫、調(diào)試的原因。蟻群算法研究處于初期，還有許多問題值得研究，如算法的參數(shù)選擇、螞蟻數(shù)的比例等只能通過仿真實(shí)驗(yàn)，無法給出理論指導(dǎo)。附 錄：蟻群算法解決旅行商問題MATLAB程序function yy=ACATSPx=41 37 54 25 7 2 68 71 54 83 64 18 22 83 91 25 24 58 71 74 87 18 13 82 62 58 45 41 44 4;y=94 84 67 62 64 99 58 44 62 69 60 54 60 46 38 38 42 69 71 78

10、 76 40 40 7 32 35 21 26 35 50;C=x y;NC_max=50;m=30;Alpha=1.5;Beta=2;Rho=0.1;Q=106;%-% 主要符號(hào)說明% C n個(gè)城市的坐標(biāo)，n2的矩陣% NC_max 最大迭代次數(shù)% m 螞蟻個(gè)數(shù)% Alpha 表征信息素重要程度的參數(shù)% Beta 表征啟發(fā)式因子重要程度的參數(shù)% Rho 信息素蒸發(fā)系數(shù)% Q 信息素增加強(qiáng)度系數(shù)% R_best 各代最佳路線% L_best 各代最佳路線的長(zhǎng)度%=%第一步：變量初始化n=size(C,1);%n表示問題的規(guī)模（城市個(gè)數(shù)）D=zeros(n,n);%D表示完全圖的賦權(quán)鄰接矩陣fo

11、r 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; %i=j時(shí)不計(jì)算，應(yīng)該為0，但后面的啟發(fā)因子要取倒數(shù)，用eps（浮點(diǎn)相對(duì)精度）表示 end D(j,i)=D(i,j); %對(duì)稱矩陣 endendEta=1./D; %Eta為啟發(fā)因子，這里設(shè)為距離的倒數(shù)Tau=ones(n,n); %Tau為信息素矩陣Tabu=zeros(m,n); %存儲(chǔ)并記錄路徑的生成NC=1; %迭代計(jì)數(shù)器，記錄迭代次數(shù)R_best=zeros(NC_max,n); %各代最佳路線L_best=in

12、f.*ones(NC_max,1); %各代最佳路線的長(zhǎng)度L_ave=zeros(NC_max,1); %各代路線的平均長(zhǎng)度while NC=rand); %若計(jì)算的概率大于原來的就選擇這條路線 to_visit=J(Select(1); Tabu(i,j)=to_visit; endendif NC=2 Tabu(1,:)=R_best(NC-1,:);end%第四步：記錄本次迭代最佳路線L=zeros(m,1); %開始距離為0，m*1的列向量for i=1:m R=Tabu(i,:);for j=1:(n-1) L(i)=L(i)+D(R(j),R(j+1); %原距離加上第j個(gè)城市到第

13、j+1個(gè)城市的距離endL(i)=L(i)+D(R(1),R(n); %一輪下來后走過的距離endL_best(NC)=min(L); %最佳距離取最小pos=find(L=L_best(NC);R_best(NC,:)=Tabu(pos(1),:); %此輪迭代后的最佳路線L_ave(NC)=mean(L); %此輪迭代后的平均距離NC=NC+1; %迭代繼續(xù)%第五步：更新信息素Delta_Tau=zeros(n,n); %開始時(shí)信息素為n*n的0矩陣for i=1:m for j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(

14、i,j),Tabu(i,j+1)+Q/L(i); %此次循環(huán)在路徑（i，j）上的信息素增量 endDelta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);%此次循環(huán)在整個(gè)路徑上的信息素增量endTau=(1-Rho).*Tau+Delta_Tau; %考慮信息素?fù)]發(fā)，更新后的信息素%第六步：禁忌表清零Tabu=zeros(m,n); %直到最大迭代次數(shù)end%第七步：輸出結(jié)果Pos=find(L_best=min(L_best); %找到最佳路徑（非0為真）Shortest_Route=R_best(Pos(1),:) %最大迭代次數(shù)后最佳路徑Shortest_Length=L_best(Pos(1) %最大迭代次數(shù)后最短距離subplot(1,2,1); %繪制第一個(gè)子圖形DrawRoute(C,Shortest_Route); %畫路線圖的子函數(shù)subplot(1,2,2); %繪制第二個(gè)子圖形plot(L_best);hold on %保持圖形plot(L_ave,r);title(平均距離和最短距離) %標(biāo)題function DrawRoute(C,R)%=% DrawRoute.m% 畫路線圖的子函數(shù)%-%