計算智能大作業(yè)--蟻群算法解決TSP問題

1、（計算智能大作業(yè)）應(yīng)用蟻群算法求解TSP問題 目錄蟻群算法求解TSP問題3摘要：3關(guān)鍵詞：3一 、引言3二、蟻群算法原理4三、蟻群算法解決問題7四、解決個城市的TSP問題的算法步驟9五、程序?qū)崿F(xiàn)11六、蟻群算法優(yōu)缺點分析及展望18七、總結(jié)18采用蟻群算法解決TSP問題摘要：蟻群算法是通過螞蟻覓食而發(fā)展出的一種新的啟發(fā)算法，該算法已經(jīng)成功的解決了諸如TSP問題。本文簡要學(xué)習(xí)探討了螞蟻算法和TSP問題的基本內(nèi)容，嘗試通過matlab仿真解決一個實例問題。關(guān)鍵詞： 蟻群算法；TSP問題；matlab。一 、引言 TSP（Travelling Salesman Problem）又稱貨郎擔(dān)或巡回售貨員問

2、題。TSP問題可以描述為：有N個城市，一售貨員從起始城市出發(fā)，訪問所有的城市一次，最后回到起始城市，求最短路徑。TSP問題除了具有明顯的實際意義外，有許多問題都可以歸結(jié)為TSP問題。目前針對這一問題已有許多解法，如窮舉搜索法（Exhaustive Search Method）, 貪心法（Greedy Method）, 動態(tài)規(guī)劃法（Dynamic Programming Method）分支界定法（Branch-And-Bound），遺傳算法（Genetic Agorithm）模擬退火法(simulated annealing),禁忌搜索。本文介紹了一種求解TSP問題的算法蟻群算法，并通過matl

3、ab仿真求解50個城市之間的最短距離，經(jīng)過仿真試驗，證明是一種解決TSP問題有效的方法。20世紀(jì)90年代，意大利學(xué)者M(jìn).Dorigo等人在新型算法研究的過程中，通過模擬自然界螞蟻的覓食過程：即通過信息素（pheromone）的相互交流從而找到由蟻巢至食物的最短路徑，提出了一種基于信息正反饋原理的新型模擬進(jìn)化算法蟻群算法（Ant Colony algorithm）。蟻群算法是繼遺傳算法、人工神經(jīng)網(wǎng)絡(luò)等算法之后的又一種啟發(fā)式算法，它的基本原理借鑒了這樣一個客觀事實：螞蟻由自組織的合作能力所產(chǎn)生的群體智能來尋找路徑，它被認(rèn)為是用于解決組合優(yōu)化問題的又一種新方法。蟻群算法是一種適應(yīng)性好、魯棒性強,具有

4、正反饋結(jié)構(gòu)的并行算法。這些初步研究已顯示出蟻群算法在求解復(fù)雜優(yōu)化問題(特別是離散優(yōu)化問題)方面的一些優(yōu)越性,證明它是一種很有發(fā)展前景的方法。螞蟻算法在各個領(lǐng)域的應(yīng)用,說明該算法有著廣泛的適應(yīng)性,但由于該算法出現(xiàn)的較晚,對其研究還處于起步階段,遠(yuǎn)不如遺傳算法、人工神經(jīng)網(wǎng)絡(luò)和模擬退火算法那樣成熟。二、蟻群算法原理蟻群算法的基本原理來源于自然界螞蟻覓食的最短路徑原理，根據(jù)昆蟲學(xué)家的觀察，發(fā)現(xiàn)自然界的螞蟻雖然視覺不發(fā)達(dá)，但它可以在沒有任何提示的情況下找到從食物源到巢穴的最短路徑，并且能在環(huán)境發(fā)生變化（如原有路徑上有了障礙物）后，自適應(yīng)地搜索新的最佳路徑。螞蟻是如何做到這一點的呢？原來，單個的螞蟻為了避

5、免自己迷路，它在爬行時，同時也會釋放一種特殊的分泌物信息素（Pheromone），而且它也能覺察到一定范圍內(nèi)的其它螞蟻所分泌的信息素，并由此影響它自己的行為。當(dāng)一條路上的信息素越來越多（當(dāng)然，隨著時間的推移會逐漸減弱），后來的螞蟻選擇這條路徑的概率也就越來越大，從而進(jìn)一步增加了該路徑的信息素濃度，這種選擇過程稱為螞蟻的自催化過程，其原理是一種正反饋機制。這里我們可以用一個圖來說明螞蟻覓食的最短路徑選擇原理，如圖2-1所示。圖2-1 蟻群覓食原理如圖2-1（a）所示，我們假設(shè)A點是食物，而E點是螞蟻的巢穴，當(dāng)A、E兩點間沒有任何障礙物阻擋時，螞蟻不存在路徑選擇的問題，這種情況最簡單：由于兩點間直

6、線距離最短，螞蟻們搬運食物時，會以直線的形式往返爬行。但在圖2-1（b）中的情形有所變化，若某時刻忽然有一個障礙物出現(xiàn)在螞蟻經(jīng)過的路徑中，原有的路徑被切斷，那么從A點到E點的螞蟻就必須在B點決定應(yīng)該往左還是往右走，而從E點到A點的螞蟻也必須在D點決定選擇走哪條路徑；這種決定會受到各條路徑上以往螞蟻留下的信息素濃度（即殘留信息素濃度）的影響。如果往右走的路徑上的信息素濃度比較大，那么右邊的路徑被螞蟻選中的可能性也就大一些；但是對障礙出現(xiàn)后第一個到達(dá)B點或D點的螞蟻而言，因為沒有信息素的影響，所以它們選擇向左或者向右的可能性是一樣的，（b）圖所表示的正是此時的情況。若以從A點到E點的螞蟻為例進(jìn)行說

7、明（對于從E點到A點的螞蟻而言，過程也基本是一樣的），由于路徑BCD比路徑BHD要短，因此選擇BCD路徑的第一只螞蟻要比選擇BHD的第一只螞蟻早到達(dá)D點；此時，從D點向B點看，路徑DCB上的信息素濃度要比路徑DHB上的信息素濃度大。因此從下一時刻開始，從E點經(jīng)D點到A點的螞蟻，它們選擇DCB路徑的可能性要比選擇DHB路徑的可能性大得多，從而使路徑BCD（或DCB）上信息素濃度與路徑BHD（或DHB）上信息素濃度的差變大；而信息素濃度差變大的結(jié)果是選擇路徑BCD（或DCB）的螞蟻進(jìn)一步增加，這又導(dǎo)致信息素濃度差進(jìn)一步加大。如圖2-1（c）所示，隨著時間的推移，幾乎所有的螞蟻都會選擇路徑BCD搬運

8、食物，而我們同時也會發(fā)現(xiàn)：BCD路徑也正是事實上的最短路徑。這種蟻群尋徑的原理可簡單理解為：對于單個的螞蟻來說，它并沒有要尋找到最短路徑的主觀上的故意；但對于整個蟻群系統(tǒng)來說，它們又確實達(dá)到了尋找到最短路徑的客觀上的效果。在自然界中，蟻群的這種尋找路徑的過程表現(xiàn)為一種正反饋的過程，與蟻群算法中人工蟻群的尋優(yōu)算法極為一致。例如，我們把只具備了簡單功能的工作單元視為“螞蟻”，那么上述尋找路徑的過程可以用于解釋蟻群算法中人工蟻群的尋優(yōu)過程。三、蟻群算法解決問題我們來介紹一下如何用蟻群算法求解個城市的TSP設(shè)為城市，之間的幾何距離，。設(shè) 表示時刻位于城市的螞蟻的個數(shù)，螞蟻總數(shù)，表示時刻在連線上殘留的信

9、息量，初始時刻各條路徑上的信息量為（為常數(shù)）。用參數(shù)表示信息量的保留度，則經(jīng)過個時刻后，路徑上的信息量根據(jù)下式作調(diào)整： 表示第只螞蟻在本次循環(huán)中留在路徑上的信息量，表示本次循環(huán)所有經(jīng)過的螞蟻留在上的信息量。 定義。螞蟻（，）在運動過程中，表示在時刻螞蟻由位置轉(zhuǎn)移到位置的概率： 我們用記錄螞蟻目前已經(jīng)走過的城市集合，allow表示螞蟻下一步允許選擇的城市集合，它等于全部的城市集合除去第只螞蟻已走過的集合。 定義為第只螞蟻在本次循環(huán)中走過的路徑和。用蟻群算法解決問題是一個遞推過程 ，當(dāng)時，將螞蟻放在各城市，設(shè)定每條路徑上的信息量初值，每只螞蟻根據(jù)公式?jīng)Q定的概率從城市到城市。表示曾經(jīng)有多少螞蟻經(jīng)過路

10、徑（，）；說明較近的城市有更大的可能性被選中。，用來控制兩者對螞蟻選擇的影響力程度。經(jīng)過一個循環(huán)后，根據(jù)公式計算更新每條路徑的信息量。將所有的復(fù)原，最后求出本次循環(huán)的最短路徑min。這個過程不斷重復(fù)，直到所有的螞蟻都選擇同樣的路徑，或者循環(huán)次數(shù)達(dá)到預(yù)先設(shè)定的最高次數(shù)。四、解決個城市的TSP問題的算法步驟1.初始化：設(shè)定t=0，循環(huán)計數(shù)器nc=0，對每條路徑設(shè)定初始信息量C,將只螞蟻放在個城市上（為了使問題簡化，設(shè)定）。2.設(shè)定taub集合的索引，對從到，把第只螞蟻放在起始位置，對應(yīng)的設(shè)定集合3.重復(fù)下面的步驟，直到集合tabu滿為止（這一步將重復(fù)次）：設(shè)定；對從到，根據(jù)公式確定的概率，選擇下一

11、步移動的目標(biāo)城市在時間時，第只螞蟻所在的城市是；將第只螞蟻移到城市；把加入到集合中。4.對從到：將第只螞蟻從移動到；計算第只螞蟻所走過的路程和，并更新最小路徑min；對每條路徑（,）： 5.對每條路徑（,）根據(jù)計算；設(shè)定；設(shè)定；對每條路徑（,），設(shè)定。6.如果，則清空所有的集合tabu,轉(zhuǎn)到第二步；否則,得出最短的路徑。算法的流程如下圖: 五、程序?qū)崿F(xiàn)一： Matlab實現(xiàn)程序如下： %一始化變量clear;Alpha=1; %信息素重要程度的參數(shù)(對路徑選擇有很大影響)Beta=5; %啟發(fā)式因子重要程度的參數(shù)(對路徑選擇有很大影響)Rho=0.95; %信息素蒸發(fā)系數(shù)NC_max=200;

12、 %最大迭代次數(shù)(循環(huán)多結(jié)果更優(yōu)適度即可)Q=100; %信息素增加強度系數(shù) (對結(jié)果影響小)CityNum=50; %問題的規(guī)模（城市個數(shù)）dislist,Clist=tsp(CityNum);m=CityNum; %螞蟻個數(shù)Eta=1./dislist;%Eta為啟發(fā)因子，這里設(shè)為距離的倒數(shù)Tau=ones(CityNum,CityNum);%Tau為信息素矩陣Tabu=zeros(m,CityNum);%存儲并記錄路徑的生成NC=1;%迭代計數(shù)器R_best=zeros(NC_max,CityNum); %各代最佳路線L_best=inf.*ones(NC_max,1);%各代最佳路線的

13、長度L_ave=zeros(NC_max,1);%各代路線的平均長度figure(1);while NC=rand); to_visit=J(Select(1); Tabu(i,j)=to_visit; end end if NC=2 Tabu(1,:)=R_best(NC-1,:); end %四記錄本次迭代最佳路線 L=zeros(m,1); for i=1:m R=Tabu(i,:); L(i)=CalDist(dislist,R); end L_best(NC)=min(L); pos=find(L=L_best(NC); R_best(NC,:)=Tabu(pos(1),:); L_

14、ave(NC)=mean(L); drawTSP(Clist,R_best(NC,:),L_best(NC),NC,0); NC=NC+1; %五更新信息素 Delta_Tau=zeros(CityNum,CityNum); for i=1:m for j=1:(CityNum-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i); end Delta_Tau(Tabu(i,CityNum),Tabu(i,1)=Delta_Tau(Tabu(i,CityNum),Tabu(i,1)+Q/L(i); e

15、nd Tau=(1-Rho).*Tau+Delta_Tau; %六禁忌表清零 Tabu=zeros(m,CityNum); %pause; tauji(NC)=Tau(1,2);end%七輸出結(jié)果Pos=find(L_best=min(L_best);Shortest_Route=R_best(Pos(1),:);Shortest_Length=L_best(Pos(1);figure(2);plot(L_best L_ave);legend(最短距離,平均距離)；二：function DLn,cityn=tsp(n)if n=50 city50=31 32;32 39;40 30;37 69

16、;27 68;37 52;38 46;31 62;30 48;21 47;25 55;16 57;17 63;42 41;17 33;25 32;5 64;8 52;12 42;7 38;5 25; 10 77;45 35;42 57;32 22; 27 23;56 37;52 41;49 49;58 48;57 58;39 10;46 10;59 15;51 21;48 28;52 33; 58 27;61 33;62 63;20 26;5 6;13 13;21 10;30 15;36 16;62 42;63 69;52 64;43 67;%50 cities d=427.855 by D

17、B Fogel for i=1:50 for j=1:50 DL50(i,j)=(city50(i,1)-city50(j,1)2+(city50(i,2)-city50(j,2)2)0.5; end end DLn=DL50; cityn=city50;end三：function m=drawTSP(Clist,BSF,bsf,p,f)CityNum=size(Clist,1);for i=1:CityNum-1 plot(Clist(BSF(i),1),Clist(BSF(i+1),1),Clist(BSF(i),2),Clist(BSF(i+1),2),ms-,LineWidth,2,M

18、arkerEdgeColor,k,MarkerFaceColor,g); hold on;endplot(Clist(BSF(CityNum),1),Clist(BSF(1),1),Clist(BSF(CityNum),2),Clist(BSF(1),2),ms-,LineWidth,2,MarkerEdgeColor,k,MarkerFaceColor,g);title(num2str(CityNum),城市TSP);if f=0 text(1000,200,第 ,int2str(p), 步, 最短距離為 ,num2str(bsf);else text(1000,100,最終搜索結(jié)果：最短距離 ,num2str(bsf);endhold off;pause(0.05);附錄四：function F=CalDist(dislist,s)DistanV=0;n=size(s,2);for i=1:(n-1) DistanV=DistanV+dislist(s(i),s(i+1);endDistanV=D