1、大連理工大學研究生必修課作業(yè)課程名稱：現代物流管理研究生姓名：徐靛學號：21511149作業(yè)成績：任課教師（簽名）交作業(yè)日時間：2016年6月1日蟻群算法在TSP問題上的應用摘要蟻群算法是受現實螞蟻群體行為啟發(fā)而得出的一類仿生算法。本文以解決TSP問題為基礎，系統(tǒng)地介紹了蟻群算法從誕生到成熟過程中幾個代表性的算法。在闡述算法基本思想的前提下，著重論述算法的創(chuàng)新之處。關鍵詞蟻群算法，TSP問題，蟻群優(yōu)化1引言蟻群算法也稱作蟻群優(yōu)化(AntColonyOptimization,ACO),最早是由Dorigo及其研究同伴所提出，用于求解諸如旅行商問題之類的組合優(yōu)化問題。自然界螞蟻在其經過的路徑上會留

2、下某種生物信息物質(信息素)，該物質會吸引蟻群中的其它成員再次選擇該段路徑；食物與巢穴之前較短的路徑容易積累較多的信息素，因而使得更多的螞蟻選擇走該段路徑，最終幾乎所有的螞蟻都集中在最短路徑上完成食物的搬運。Dorigo等從此現象中抽象出路徑選擇和信息素積累的數學模型，作為蟻群算法的核心，并通過對螞蟻尋找最短路徑的計算機模擬，實現了對TSP問題的求解。自此，蟻群算法越來越多地被用于求解其它的組合優(yōu)化問題，也被推廣到工業(yè)工程上應用。蟻群算法特點是并發(fā)性、魯棒性、正反饋性等。在蟻群算法求解問題的過程中，利用蟻群在問題空間中同時構造問題的多個解體現了算法的并發(fā)性。蟻群不會因為單個螞蟻尋找到較差的解或

3、者因為問題空間發(fā)生改變而使得算法喪失作用，這體現了算法的魯棒性。在螞蟻構造問題解的過程中，以蟻群覓食行為為例，會在經過的解路徑上釋放信息素，而解空間中獲得信息素越多的路徑，對螞蟻的吸引力就越大，使更多的螞蟻經過該路徑并進一步在上面釋放信息素，這體現了算法的正反饋性。TSP問題代表一類組合優(yōu)化問題，在實際工程中有許多應用，如計算機聯網、電子地圖、交通誘導、電氣布線、VLSI單元布局、ATM分組交換網等。鑒于其重要的工程與理論價值，TSP常作為算法性能研究的典型算例。求其最優(yōu)解的代價是指數級的，因此對其近似解的研究一直是算法設計的一個重要課題。TSP問題是典型的NP完全問題，許多算驗證法及算法效率

4、測試都以TSP問題為基礎。在蟻群算法研究中，第一個蟻群算法，螞蟻系統(tǒng)，就是在TSP問題的基礎上提出來的。而后，依據TSP問題，又提出了蟻群算法系列中具有代表性的蟻群系統(tǒng)、最大一一最小螞蟻系統(tǒng)。本文以TSP問題為基礎，對蟻群算法的基本問題及典型的蟻群算法進行了綜述。涉及到算法的基本問題、算法描述、算法改進及意義。通過研究總結了蟻群算法的發(fā)展歷程和實現思想。2蟻群行為和TSP問題2.1 蟻群行為蟻群的行為是整體協(xié)作，相互分工，以一個整體去解決一些對單個螞蟻看上去是不可能完成的任務。就目前來講，蟻群至少有三個方面的行為特征對算法研究有很好的啟發(fā)意義，分別是覓食行為、任務分配、死蟻堆積閣。蟻群的覓食行

5、為指螞蟻從巢穴出發(fā)尋找食物并且將食物搬回巢穴的行為，當螞蟻出外尋找食物時，會在自己走過的路徑上釋放一種稱為信息素的物質，后續(xù)的螞蟻一般更愿意走那些信息素強度更高的路徑。這樣，較短路徑上單位時間內通過的螞蟻數目較多，留下的信息素也較多(濃度更高)，對媽蟻產生了更強的吸引，使得更多的螞蟻走較短的路徑。這就形成了一個正反饋機制，使得最終所有的螞蟻都走蟻穴到食物源的最短路徑。蟻群的任務分配指蟻群內部能根據所需要完成的任務合理分配螞蟻數to研究表明，從事不同任務的螞蟻之間的比例是會變動的，也就是說從事任務A的螞蟻可能會根據需要而從事任務Bo在基于這種蟻群行為的模型中，規(guī)定了每只媽蟻的反應閾值，同時每一個

6、任務都有一個相關的激勵(task-relatedstimuli)。反應閾值與激勵間的關系是：當某個任務的激勵數值比螞蟻的反映閾值大，那么這只螞蟻就會加人到該任務執(zhí)行者的行列中。蟻群中，如果一群螞蟻在執(zhí)行某任務時出現執(zhí)行滯后情況，那么該任務的激勵數值就會變大，直到其數值大于某些未執(zhí)行該任務的螞蟻的反映閾值，從而吸引更多的螞蟻來完成該任務，由此實現了任務的自動分配。死蟻堆積與蟻穴清理行為：在蟻群的巢穴中，工蟻會對死螞蟻進行搬運，使得那些死螞蟻堆積到一起。在這一堆積行為中，死蟻堆越大對工蟻的吸引力越大，使得更多的死螞蟻被堆積到該蟻堆中，這樣同樣也形成了一個正反饋現象。但是，并不是說所有的死媽蟻都會堆

7、積到一起，而是最終會形成幾個規(guī)模較大的蟻堆。研究者對蟻群的這3種行為特征進行了深入的研究，并應用于最短路徑優(yōu)化、任務分配調度以及數據聚類等問題領域，得到了效率較高的許多啟發(fā)式算法。2.2 TSP問題TSP問題是給定一個城市的集合以及城市之間的旅行代價，尋找經過每個城市一次且僅一次而最終回到起始城市旅行代價最小的路徑。如果構造一個圖如下：圖中的頂點為城市，頂點間的邊表示城市間的交通線，邊上的權為沿該交通線旅行的費用。那么，TSP問題就抽象為在這個圖中尋找最短哈密爾頓回路。任意兩個城市A、B,如果A到B的旅行代價和B到A旅行代價相等，稱這本的TSP問題是對稱的TSP問題(symmetrictrav

8、elingsalesmanproblem,STSP),否則稱為不對稱的TSP問題(asymmetrictravelingsalesmanproblem,ATSP)。通常，在沒有特別申明的情況下所提及的TSP問題指對稱的TSP問題。n個頂點的TSP問題中的路徑指頂點的序列：L=xi,X2xn,其中Xi與Xi+1(1三i三n-l)之間有邊。一'條路徑被稱為合法路徑，如果XiwXj(iwj,1=i=n,1=j-n)oTSP問題本質上是數學優(yōu)化問題，可以形式化地描述為：n-1Min(dXi,Xi+1+dXn,X1)i=1其中，d(Xi,Xi+1)表示頂點xi與頂點Xi+1之間的距離。算法研究表

9、明，TSP問題是NP完全問題，其計算復雜度為(n!)。自TSP問題提出以來，其求解方法得到了不斷的改進。目前已經可以對上萬個城市的TSP問題進行求解閣。近年來，以蟻群行為為基礎的蟻群算法已成為一種較為有效的TSP問題求解方法。3典型的蟻群算法這里我們僅討論與TSP問題相關的蟻群算法。在蟻群算法研究及實現中，并不是直接模擬現實蟻群，而是采用人工螞蟻(artificialant)。人工蟻群與現實蟻群的區(qū)別主要包括：(1)人工螞蟻是有一定的記憶能力的，它可以記住己經走過的路徑，以保證不會重復走相同的城市?，F實的蟻群是沒有記憶的，螞蟻間的信息交換主要依靠留在所經過路徑上的信息素。(2)人工螞蟻不僅僅是

10、依據信息素來確定要走的路徑的，還依據一定的啟發(fā)信息，比如相鄰邊的長度，這意味著人工螞蟻具有一定的視覺能力，而真實螞蟻幾乎沒有視覺。(3)人工螞蟻是生活在一個離散的時間環(huán)境下的。我們僅考慮人工螞蟻位于某個城市，而不考慮螞蟻在城市間的移動過程，即只考慮在某些離散時間點上的螞蟻。而現實世界中的螞蟻處于一個連續(xù)的時間維中。3.1螞蟻系統(tǒng)(AntSystem)螞蟻系統(tǒng)是第一個蟻群算法，它是Dorige等人于1991年首先提出來的。螞蟻系統(tǒng)有三種基本模型，分別是蟻周模型、蟻密模型、蟻量模型。三種模型的實現大致相同，主要區(qū)別是在信息素的更新方式上。在用螞蟻系統(tǒng)解決TSP問題時，蟻量模型和蟻密模型是螞蟻在構建

11、一條合法路徑的過程中進行信息素的更新的，當螞蟻走過一條邊之后，就對該邊進行信息素的更新，后文將這種更新稱為局部更新。而蟻周模型是在所有螞蟻都構建了一條合法路徑之后才對各邊進行信息素更新的，后文將這種更新稱為全局更新，并且三者在螞蟻釋放信息素的量上面也不同。蟻密模型中，螞蟻在自己所走過的邊上所釋放的信息素是一個常量Q,而蟻量模型中，螞蟻在自己所走過的邊上釋放的信息素是Q/dj,其中Q是一個常量，而dj是螞蟻走過邊的長度。蟻周模型中螞蟻釋放信息素的量在后文說明。由于蟻周模型是三種模型中性能最好的，下面主要從蟻周模型的角度來討論螞蟻系統(tǒng)。螞蟻系統(tǒng)的基本思想是：(1)預先初始化各邊信息素強度、以及各螞

12、蟻的禁忌表。各螞蟻按照一定的概率規(guī)則，在禁忌表的制約下選擇下一個要到達的結點，直到最終形成一條合法路徑。(2)計算各螞蟻所產生的路徑長度，路徑長度是路徑中各邊長度之和。(3)更新各邊的信息素。各邊先進行信息素揮發(fā)操作，然后根據各螞蟻產生的路徑長度獲取螞蟻所釋放的信息素。(4)當所有螞蟻均完成了信息素的更新操作之后，記錄當前的最短路徑，并且對禁忌表以及信息素的增加值a叼進行初始化，并轉到步驟2。依此循環(huán)下去，直到滿足算法的終了條件為止，比如解無法得到進一步的改進或者達到了事先規(guī)定的循環(huán)次數。在螞蟻系統(tǒng)具體包括了三個方面的內容。第一、初始化。對于每條邊上的信息素初始化為一個較小的數值0;對每只螞蟻

13、，需要一個禁忌表記錄自己已經走過的結點，初始化其禁忌表為該螞蟻所在的結點，禁忌表長度為1。螞蟻在各邊上釋放信息素的量被初始化為0。第二、螞蟻構造路徑。螞蟻按照一定的概率確定下一步要到達的城市。概率的計算如下10,otherwise,上式表示螞蟻在t時刻由城市i選擇城市j的概率。”是信息素在概率計算中的權重，它的值越大，信息素在螞蟻選擇下一個要到的城市中起到的作用越大。3是啟發(fā)因子(在TSP問題中常以dij的倒數來表示)在概率計算中所占的權重，它的值越大，啟發(fā)因子在螞蟻選擇城市的過程中所起的作用越大。Nh(i)是不在螞蟻禁忌表中的城市集合。上式說明，螞蟻不會選擇禁忌表中的城市，這樣就保證了解的合

14、法性。第三、對信息素的操作。在蟻周模型中，當所有的螞蟻都找到了一條合法路徑之后，就進行信息素的更新，如下式。北+l)=p4(fu+1)其中，口工法示在x時刻邊ij上的信息素。P是信息素維持因子，1-P是信息素的揮發(fā)因子。小0卜)是所有螞蟻在邊ij上所釋放的信息素的總和，如下式。I一|其中m是螞蟻的數量，L是媽蟻k在t至Ut+l時間內在邊ij上所釋放的信息素，如果螞蟻也所形成的路輕包括邊。I0否則大部分的蟻群算法都是在螞蟻系統(tǒng)的基礎上發(fā)展而來的。它們都是將螞蟻系統(tǒng)與具體問題相Z合，并且在螞蟻系統(tǒng)的基礎之上引入一些新的控制機制。故，通常都是把螞蟻系統(tǒng)認為是蟻群算法的先驅與研究的基礎。3.2蟻群系統(tǒng)

15、螞蟻系統(tǒng)(AntColonySystem,ACS)是第一個蟻群算法，在解決規(guī)模較小的TSP問題的時候效果很好，但是隨著問題的規(guī)模擴大，螞蟻系統(tǒng)就會出現收斂速度過慢的問題。在1996年，Dorigo在螞蟻系統(tǒng)的基礎之上又提出了蟻群系統(tǒng)。蟻群系統(tǒng)的基本思想是：將m只螞蟻按照一定的規(guī)則(隨機)放于n個結點。每一只螞蟻通過偽隨機規(guī)則，也稱狀態(tài)轉移規(guī)則創(chuàng)建一條合法路徑。在創(chuàng)建路徑的過程中，每一只螞蟻通過局部更新規(guī)則對自己所走過的邊進行信息素的更新操作。當所有的螞蟻都完成了路徑的構造之后，再對最佳路徑上的邊進行信息素的全局更新。蟻群系統(tǒng)較螞蟻系統(tǒng)改進的地方主要體現在三個方面。第一、蟻群系統(tǒng)全局更新時僅針對

16、當前最好路徑上的邊進行，更新規(guī)則如下式所示。=(1A>>r(nrA,Xi,，)其中，入是信息素衰退因子，是當前最好路徑長度的倒數。第二、蟻群系統(tǒng)在螞蟻創(chuàng)建路徑的過程中所使用的狀態(tài)轉移規(guī)則不同于螞蟻系統(tǒng)，如下式所示。Iarg皿力迎正汽人加*Tg'G了)$<ify0(exploititm)1)otherwise(.biasedexpIuration)其中，qC(0,1)是一個隨機數，q0c(0,1)是一個常量，它在算法的求解效率與算法的運行效率之間起平衡作用。一般地，想使算法收斂于全局最優(yōu)解，獲得較高的求解效率就務必要求搜索范圍盡可能地大，不能局限在已有路徑這個空間周圍，

17、而這不可避免就使得算法的運行效率降低。反之，假如要想算法的運行速度加快，獲得滿意的運行效率，那么算法的搜索空間就不能太大，這樣使得算法有收斂于局部最優(yōu)解的風險。蟻群系統(tǒng)的做法是：當q三q0時，則增強已有的較好的路徑上的信息素，即選擇當前轉移概率最大的那個城市。而當q>q0時，就按照螞蟻系統(tǒng)中的選路方式來選擇下一個要到的城市，以擴大搜索空間。這樣做的優(yōu)點是在保障算法求解效率的基礎上同時又提高了算法的運行效率。第三、蟻群系統(tǒng)在對信息素更新時，除了進行全局更新，還要進行信息素的局部更新。局部更新如下式所示。其中，p任(0,1)。在關于蟻群系統(tǒng)的后續(xù)研究中，ACS引人了局部搜索(LocalSea

18、rch)策略，它使用restriet3-opt,這個搜索策略可以同時滿足ATSP和STSP兩類問題，并且可以明顯提高算法的性能。實驗研究表明，ACS在解決規(guī)模較大的TSP問題時，可以取得比較令人滿意的結果。3.3蟻群優(yōu)化算法隨著對蟻群算法研究的深人，蟻群算法的應用領域也隨之不斷擴充。繼TSP問題之后，蟻群算法又相繼應用于QAP,VRP等組合優(yōu)化問題，網絡路由問題，圖的著色問題以及機器人路徑規(guī)劃等問題。蟻群算法與不同具體問題相結合而產生了不同的蟻群算法。這些不同的蟻群算法在外在形式和內在運行機制方面都有相似之處。從Dorige等人于1999年提出了蟻群優(yōu)化算法(AntColonyoptimiza

19、tion,ACO),該算法給出了蟻群算法的一個一般化的框架。蟻群優(yōu)化算法的提出在蟻群算法發(fā)展歷程中具有重要的意義。ACO的主要思想是：如果求解的問題能夠轉換為在一個圖中尋找最優(yōu)路徑，那么ACO就能夠用于尋找滿足給定限定條件的最優(yōu)路徑，進而完成對問題的求解。ACO對蟻群算法的實現進進行了高度的概括，將蟻群算法主要概括為螞蟻的行為，信息素的揮發(fā)操作和一些守護操作。其中守護操作是可選的。ACO的偽代碼如下：procedureACO()while£terminanon_critenon_notsati&iied)schedule_activitiesants_generation_a

20、nd_acti¥ity()ipheromone_evaporation()*da亡monClio忤四()Iendschedule_acuvitiesendwhileendprocedure螞蟻的行為可以描述為一群螞蟻同時異步地在問題空間中相鄰的狀態(tài)之間移動，可以形象化為在一個圖中的相鄰結點之間移動。移動依靠問題的啟發(fā)信息和信息素所決定的選擇策略以及問題本身的限制條件。通過移動，逐步地構建問題的解。一旦螞蟻構建出了問題的解，或者螞蟻正在構建問翅解的過程時，螞蟻會對解進行評估，然后依據解的好壞來釋放一定的信息素到路徑上。而這些信息素將進一步指導后續(xù)螞蟻構造路徑。在ACO中，螞蟻的行為用a

21、nt_geneariton_and_activity()來表示.。信息素的揮發(fā)操作可以描述為圖的邊上的信息素隨著時間而逐漸消失。這樣做是為了避免算法過快收斂于局部解，信息素的揮發(fā)操作同樣有利于螞蟻對新的解空間進行搜索，進而找出更好的解。在ACO中，信息素的揮發(fā)操作用pheormone_evaporation()來表示。守護操作可以描述為實現一些螞蟻所不能完成的集中控制任務。比如一些局部搜索策略；比較各螞蟻所產生的路徑長度，僅僅對其中的最短路徑再次進行信息素的全局更新等等。在ACO中，守護操作可以用daemon_actions表示。需要指出的是，ACO對以上三個行為之間的進度和具體實現方式并沒有

22、嚴格的限制，比如它們三者之間是否需要同步或者是否要彼此并行且獨立。這就意味著在利用ACO解決實際問題的時候，可以自由安排以上三個行為之間的實現進度以及具體的實現方式。ACO適用于離散優(yōu)化問題的求解，相應問題的特征在文獻中有詳細的說明。如果說，前期的蟻群算法基本都是圍繞螞蟻系統(tǒng)而展開的，那么在蟻群優(yōu)化算法提出之后，有關蟻群算法的研究和相關應用就基本上是圍繞蟻群優(yōu)化算法而進行的。4結論本文主要從解決TSP問題的角度出發(fā)，按照時間先后順序分別介紹了蟻群算法系列中比較有代表性的幾個算法。描繪了蟻群算法從AS到ACO發(fā)展完善的過程。在介紹各算法基本思想的基礎上，著重闡述了算法的主要特點和創(chuàng)新點及其意義，從上述蟻群算法的發(fā)展過程中可以看出，蟻群算法的核心就是對信息素的合理操作，整個蟻群利用信息素作為一種間接通信工具而形成解決問題的合力。故，如果要實現蟻群算法進一步的發(fā)展，關于信息素的操作是一個主要的人手點。目前蟻群算法的應用越來越廣，國際上已經有專門的學術會議來討論蟻群算法。相信隨著研究的深人，蟻群算法必將可以得到進一步的發(fā)展，進一步拓寬蟻群的應用領域。最后需要補充的是，在蟻群算法發(fā)展的歷程中，除了文中介紹的蟻群算法之外，還有其他一些同樣具有代表性的蟻群算法。比如：帶精英策略的螞蟻系統(tǒng)(AntSystemwithelitistStrategy,ASelist),基于優(yōu)化排序的螞蟻系