蟻群優(yōu)化算法在解決TSP問題中的應用

還有頁眉沒有添加，頁眉上寫章標題，把我給你標注的問題改完就

可以打印了摘要根據(jù)螞蟻生態(tài)學提出的蟻群算法是一種新穎的用于求解復雜組合優(yōu)化問題的模擬進化算法，具有典型的群體智能特征，表現(xiàn)出較強的學習能力和適應能力。本文闡述了該算法的基本原理、算法模型和在TSP（TravelingSalesmanProblem，旅行商）問題中的具體應用過程,并對算法進行了總結(jié)和展望。關(guān)鍵詞：蟻群算法，旅行商問題，外激素摘要I目錄IITOC\o"1-5"\h\z\o"CurrentDocument"第一章引言 1\o"CurrentDocument"第二章蟻群算法的基本原理和模型 2\o"CurrentDocument"2.1蟻群算法的基本原理 2\o"CurrentDocument"2.2蟻群算法的模型 3\o"CurrentDocument"第三章基于蟻群算法的TSP求解 5\o"CurrentDocument"3.1TSP問題的描述 5\o"CurrentDocument"3.2基于蟻群算法的TSP求解 5\o"CurrentDocument"3.3蟻群算法的局限性 6\o"CurrentDocument"第四章蟻群算法的改進 8\o"CurrentDocument"4.1優(yōu)選參數(shù)m 8\o"CurrentDocument"4.2參數(shù)的調(diào)整 8\o"CurrentDocument"4.3信息素的更新 8\o"CurrentDocument"4.4信息素鏈表L和禁忌鏈表TL的構(gòu)建 9\o"CurrentDocument"第五章改進的算法基本流程 10\o"CurrentDocument"第六章結(jié)論 11\o"CurrentDocument"參考文獻 12第一章引言研究群居性昆蟲行為的科學家發(fā)現(xiàn)，昆蟲在群落一級上的合作基本上是自組織的，在許多場合中盡管這些合作可能很簡單，但它們卻可以解決許多復雜的問題。蟻群算法就是利用群集智能解決組合優(yōu)化問題的典型例子。蟻群算法(AntColonyAlgorithm,ACA)是由意大利學者M.Dorigo，V.Mzniezzo，A.Colorni等人在20世紀90年代初首先提出來的。它是繼模擬退火算法、遺傳算法、禁忌搜索算法、人工神經(jīng)網(wǎng)絡(luò)算法等元啟發(fā)式搜索算法以后的又一種應用于組合優(yōu)化問題的啟發(fā)式搜索算法。蟻群算法不僅能夠智能搜索、全局優(yōu)化，而且具有穩(wěn)健ttA、魯棒性8、正反饋、分布式計算、易與其它算法結(jié)合等特點。利用正反饋原理，可以加快進化過程；分布式計算使該算法易于并行實現(xiàn)，個體之間不斷進行信息交流和傳遞，有利于找到較好的解，不容易陷入局部最優(yōu)；該算法易與多種啟發(fā)式算法結(jié)合，可改善算法的性能；由于魯棒性強，故在基本蟻群算法模型的基礎(chǔ)上進行修改，便可用于其它問題。因此，蟻群算法的問世為諸多領(lǐng)域解決復雜優(yōu)化問題提供了有力的工具。TSP問題，又稱旅行商問題，就是一個銷售商從n個城市中的某一城市出發(fā)，不重復地走完其余n-1個城市并回到原出發(fā)點，在所有可能的路徑中求出路徑長度最短的一條。它是組合優(yōu)化中研究最多的問題之一，是一個經(jīng)典的NP難題。第二章蟻群算法的基本原理和模型2.1蟻群算法的基本原理蟻群系統(tǒng)本來是生物學家為更好揭示昆蟲的交互作用而提出的一種昆蟲自組織模式。盡管建立這種模式的初衷是為了幫助人們?nèi)ダ斫膺@類昆蟲的復雜行為，螞蟻也不可能從這些解釋中獲益，但是數(shù)學及計算機方面的專家和工程師卻把這種超越生物本身的模型轉(zhuǎn)化成了一項有用的優(yōu)化和控制算法！蟻群算法，也稱蟻群系統(tǒng)(AntColonySystem,ACS)。蟻群優(yōu)化(AntColonyOptimization,ACO)是該系統(tǒng)的核心內(nèi)容，其原理可大致描述如下：螞蟻屬于群居昆蟲，個體行為極其簡單，而群體行為卻相當復雜。相互協(xié)作的一群螞蟻很容易找到從蟻巢到食物源的最短路徑，而單個螞蟻則不能。此外，螞蟻還能夠適應環(huán)境的變化，例如在蟻群的運動路線上突然出現(xiàn)障礙物時，它們能夠很快地重新找到最優(yōu)路徑。人們通過大量的研究發(fā)現(xiàn)，螞蟻個體之間是通過在其所經(jīng)過的路上留下一種可稱之為“信息素”(Pheromone)的物質(zhì)來進行信息傳遞的。隨后的螞蟻遇到信息素時，不僅能檢測出該物質(zhì)的存在以及量的多少，而且可根據(jù)信息素的濃度來指導自己對前進方向的選擇。同時，該物質(zhì)隨著時間的推移會逐漸揮發(fā)掉，于是路徑的長短及該路徑上通過的螞蟻的多少就對殘余信息素的強度產(chǎn)生影響，反過來信息素的強弱又指導著其它螞蟻的行動方向。因此，某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。這就構(gòu)成了螞蟻群體行為表現(xiàn)出的一種信息正反饋現(xiàn)象。螞蟻個體之間就是通過這種信息交流達到最快捷搜索到食物源的目的。圖1能更具體地說明蟻群系統(tǒng)的原理。圖1蟻群優(yōu)化系統(tǒng)示意圖圖中設(shè)A是蟻巢，E是食物源，H、C為障礙物，距離為d。由于障礙物的存在，由A外出覓食或由E返回巢穴的螞蟻只能經(jīng)由H或C到達目的地。假設(shè)螞蟻以“1單位長度/R單位時間”的速度往返于A和E,每經(jīng)過一個單位時間各有30只螞蟻離開A和E到達B和D（圖1a）。初始時，各有30只螞蟻在B和D點遇到障礙物，開始選擇路徑。由于此時路徑上無信息素，螞蟻便以相同的概率隨機地走兩條路中的任意一條，因而15只選往C，15只選往H（圖1b）。經(jīng)過一個單位時間以后，路徑BCD被30只螞蟻爬過，而路徑BHD上則只被15只螞蟻爬過（因BCD距離為1而BHD距離為2），BCD上的信息量是BHD上信息量的兩倍。此時，又有30只螞蟻離開B和D，于是各20只選擇往C方向，而另外各10只則選往H（圖1c）。這樣，更多的信息素量被留在更短的路徑BCD上。隨著時間的推移和上述過程的重復，短路徑上的信息量便以更快的速度增長，于是會有越來越多的螞蟻選擇這條短路徑，以致最終完全選擇這條短路徑。由上述可見，蟻群算法的核心有三條。第一，選擇機制：信息素越多的路徑，被選中的概率越大。螞蟻群體行為表現(xiàn)出正反饋的過程，通過反饋機制的調(diào)整，可對系統(tǒng)中的較優(yōu)解起到一個自增強的作用，從而使問題的解向著全局最優(yōu)的方向演變，最終能有效地獲得全局相對較優(yōu)解；第二，信息素更新機制：路徑越短，跡增加越快。螞蟻個體之間通過不斷進行信息交流和傳遞有利于較好解的發(fā)現(xiàn)，并在很大程度上減少了陷于局部最優(yōu)的可能；第三，協(xié)作機制：個體之間通過信息素進行交流，也就是進行間接通信。2.2蟻群算法的模型設(shè)T0t為時刻連接節(jié)點ij路段上的外激素濃度，在初始時刻，各條路段上的外信息素濃度相等，設(shè)tij（0）=C（C為常數(shù)）。為邊門ij啟發(fā)信息，該啟發(fā)信息是由所要求解的問題給出的,。t時刻位于交叉點i的螞蟻k選擇交叉點j為目標點的概率取決于啟發(fā)信息與螞蟻目前所在地到目的地點路段上殘留的外激素濃度，其函數(shù)表示為Ta^P(t)iipk(t)=<乙TiI?(t),jeallowedkij keallowedk0,else式（1）中，allowedk={0，1，2，…n-1}表示螞蟻下一步允許選擇的城市，a表示外激素的相對重要tt（a>0），P表示啟發(fā)信息的相對重要性（?>0）。隨著時間的推移，可能會出現(xiàn)兩種情況：（1）先前留下的外激素逐漸消失；⑵殘留的外激素過多，從而淹沒了啟發(fā)信息。為了避免這兩種情況，在每一只螞蟻從起點到達終點后，必須對殘留的外激素進行更新。用參數(shù)p(0<p<1)來表示外激素物質(zhì)的保留率，則1-p就表示外激素的揮發(fā)率，經(jīng)過m個時間單位后，螞蟻完成一次循環(huán)，各路徑上的信息量要根據(jù)以下式子作調(diào)整：TOC\o"1-5"\h\z\o"CurrentDocument"Tij(t+m)=pij(t)+ATij(t+m) (2)ATij=史Atk (3)k=1ATk=\lk ，若第k只螞蟻在本次循環(huán)中經(jīng)過ij ⑷lJ [0,else式中Atj表示在本次循環(huán)中留在路徑ij上的信息量，Atij表示螞蟻k在路段ij上留下的殘留外激素濃度。式(4)中，Q是常數(shù)，Lk表示第k只螞蟻在本次循環(huán)中所走路徑的長度ij;初始時刻，"(0)=A,At0=0,(i,j=0,1,2,…，n-1)。第三章基于蟻群算法的TSP求解由于螞蟻尋食的過程與旅行商問題（TravelingSalesmanProblem,TSP）的求解非常相似，所以蟻群算法最早的應用就是TSP的求解。下面以求解n個城市的TSP為例來說明蟻群算法。3.1TSP問題的描述旅行商問題中，設(shè)有n個城市集C二（1，2,…，n）,任意兩個城市i，j之間的距離為禹。問題是找到一條使總長度最短的閉環(huán)路線，其中除了起點之外的每個城市都只被訪問一次，即求一條經(jīng)過每個城市僅一次的路徑兀二（丸（1），丸（2），…兀（n）），使得Min（U1d丸（i）丸（i+1）+d丸（n）丸（1）） ⑸i=13.2基于蟻群算法的TSP求解在TSP求解中，參與路徑搜尋的每只螞蟻都具有下列特征：⑴在一次周游中，螞蟻只能游走未訪問過的城市，直到本輪周游完成后，才允許螞蟻游走已訪問過的城市；⑵選擇城市的概率函數(shù)由城市之間的距離和連接支路上所包含的當前外激素余量確定；⑶當完成一次周游，每只螞蟻都會在每條訪問過的路徑上留下外激素。m只螞蟻同時從某個城市出發(fā)，由公式⑴選擇下一次旅行的城市，已游走過的城市放入tabuk集中，一次循環(huán)完成后，更新每條邊上的外激素，反復重復上述過程，直到終止條件成立。蟻群算法的實現(xiàn)步驟如下：步驟1:首先初始化，設(shè)迭代次數(shù)為NC，初始化NC=0，各T（r,s）,AT（r,s）初始化，將m個螞蟻置于n個頂點上；步驟2:將各個螞蟻置于當前的解集z中，然后對每個螞蟻k（k=1,2,…，m），按照概率Pk轉(zhuǎn)移到下一個城市S，將S置于當前的解集中，如此循環(huán)，直到所有的螞蟻訪問完所有的城市；步驟3:計算每個螞蟻行走的總路徑Lk，并將最優(yōu)解保存；步驟4:按信息素濃度更新公式，更新各邊的信息素濃度；步驟5:各邊的At（r,s）初始化，NC=NC+1；步驟6:如果NC小于預定值并且沒有穩(wěn)定解，則轉(zhuǎn)步驟2,否則轉(zhuǎn)步驟7；步驟7:將得到的結(jié)果蟻群及函數(shù)值記錄到R[i，j]及A[i，j]中；若性能滿足則結(jié)束；否則，對R[1,…，n]，A[1,…，n]進行選擇，轉(zhuǎn)步驟8；步驟8:對新的M個子種群重新開始蟻群算法操作，轉(zhuǎn)步驟1，具體流程見圖2。

圖2蟻群算法流程圖實驗結(jié)果表明，在TSP問題中應用蟻群算法進行最短路徑求解，在城市數(shù)量不多時，結(jié)果還是挺令人滿意的。3.3蟻群算法的局限性由前面對蟻群算法的介紹可知，蟻群算法在運算過程中，蟻群的轉(zhuǎn)移是由各條路徑上留下的信息量的強度和城市之間的距離來引導的。蟻群運動的路徑總是趨近于信息量最強的路徑。通過對蟻群以及蟻群算法的研究表明，不論是真實蟻群系統(tǒng)還是人工蟻群系統(tǒng)，通常情況下，信息量最強的路徑與所需要的最優(yōu)路徑比較接近。然而，信息量最強的路徑不是所需要的最優(yōu)路徑的情況仍然存在，而且在人工蟻群系統(tǒng)中，這種現(xiàn)象經(jīng)常出現(xiàn)。這是由于在人工蟻群系統(tǒng)中，各路徑上的初始信息量是相同的，蟻群創(chuàng)建的第一條路徑所用到的信息就主要是城市之間的距離信息。這時，蟻群算法等價于貪婪算法，這一次，蟻群在所經(jīng)過的路徑上留下的信息就不一定能反映出最優(yōu)路徑的方向，特別是蟻群中個體數(shù)目較少或者所計算的路徑的組合較多時，就更不能保證蟻群創(chuàng)建的一條路徑能引導蟻群走向全局最優(yōu)路徑。這一次循環(huán)中，蟻群留下的信息會因正反饋作用使這條路徑不是最優(yōu)，而且可能是離最優(yōu)解相差很遠的路徑上的信息得到不應有的增強，而阻礙以后的螞蟻發(fā)現(xiàn)更好的全局最優(yōu)解。不僅是第一次循環(huán)所創(chuàng)建的路徑可能對蟻群產(chǎn)生誤導，任何一次循環(huán)，只要這次循環(huán)所利用的信息較平均地分布在各個方向上，這次循環(huán)所產(chǎn)生的路徑就可能會對以后蟻群的選擇產(chǎn)生誤導。蟻群算法的主要依據(jù)是信息正反饋原理和某種啟發(fā)式算法的有機結(jié)合，這種算法在構(gòu)造解的過程中，利用隨機選擇策略，這種選擇策略使得進化速度較慢，正反饋原理旨在強化性能較好的解，卻容易出現(xiàn)停滯現(xiàn)象，這是造成蟻群算法不足之處的根本原因。當問題規(guī)模比較大時，由于信息量的揮發(fā)系數(shù)1-P的存在，使那些從未被搜索到的解上信息量會減小到接近于0，降低了算法的全局搜索能力，而且1-P過大時，當解的信息量增大時，以前搜索過的解被選擇的可能性過大，也會影響到算法的全局搜索能力。通過減小1-p雖然可以提高算法的全局搜索能力，但又會使算法的收斂速度降低。也就是說蟻群算法與遺傳算法等模擬進化算法一樣，也存在著易于陷于局部最小值的缺陷。因此，蟻群所找出的解需要通過一定的方法來增強，使蟻群所留下的信息盡可能地不對以后的蟻群產(chǎn)生誤導，而且能夠克服計算時間較長的缺陷，從而提高蟻群算法的全局搜索能力，提高其搜索速度。第四章蟻群算法的改進為了克服算法收斂速度慢，易陷于局部最優(yōu)解的缺陷，算法可從如下幾個方面進行改進。4.1優(yōu)選參數(shù)m用蟻群算法求解問題，都存在算法有關(guān)參數(shù)的設(shè)定問題，較好的參數(shù)組合將會使算法具有全局的搜索能力和較快的收斂速度。在其他參數(shù)不變的情況下，當螞蟻數(shù)量太少,在能導致最優(yōu)路徑的那些邊(優(yōu)選邊)走過的次數(shù)較少，難以留下較多的信息素，不利于算法迅速向最優(yōu)解收斂，而且當優(yōu)選邊在數(shù)代之內(nèi)不能被再次選擇時，其信息素將會揮發(fā)殆盡，從而造成之前數(shù)代螞蟻的優(yōu)選結(jié)果浪費；而當m值太大，一方面會增加計算量，另一方面因為在最初的幾代因為選擇路徑隨機性比較大，最初的最優(yōu)值因為螞蟻多以至于得到強化的速度太快，容易造成局部最優(yōu)解。蟻群算法中螞蟻數(shù)目m，信息素殘留系數(shù)p，參數(shù)a和。4個參數(shù)之間是相互耦合的，具有復雜的關(guān)系,所以算法中的4個參數(shù)應當綜合考慮。4.2參數(shù)p的調(diào)整p是表示信息素的殘留程度，該參數(shù)受城市n的影響較大，當城市n太大時,若揮發(fā)系數(shù)1-p太大，算法的全局搜索能力會降低；若1-p太小，算法的全局搜索能力會隨之提高，但收斂速度會變慢，因此可以對p采取自適應控制策略，即p的初始值可取大些，隨著循環(huán)次數(shù)的不斷增加，p可根據(jù)下列函數(shù)做調(diào)整：TOC\o"1-5"\h\z\o"CurrentDocument"p(t+n)=< pmi__， ￡ ⑹[p+^T，0<T<n(N-1)/2minc c式子中的Tc表示禁忌表[tabu]k中的元素，禁忌表[tabu]k用來記錄螞蟻k當前已經(jīng)走過的城市，仇為揮發(fā)約束系數(shù)，LX——PmaxPmin— (7)n(n-1)/24.3信息素的更新在進行路徑尋優(yōu)過程中，為了避免算法停滯和擴散，可以將殘留信息素數(shù)量限制在[Tmin,Tmax],Tmin可以有效地避免算法的停滯，而Tmax可以避免某條路徑上的信息素遠大于其他路徑，使得所有的螞蟻都集中到同一條路徑上來，從而限制了算法的擴散，因此可以采用如下方式來對信息素進行更新。

T(t+n)=〈T(t),TT(t+n)=〈T(t),Tj〃 mm<"j"EmaxTmaxTj>Tmax4.4信息素鏈表L和禁忌鏈表TL的構(gòu)建在蟻群算法中構(gòu)建一個鏈表L,當算法運行h次后，將各條邊上的信息素存放在鏈表L中，同時為了加快收斂速度，把信息素含量特少的一定數(shù)量的邊加入到TL(Tabulist)中，TL中的路徑將被排除在選取的范圍外，即忘記“不好”的路徑。禁忌表[tabu]k(k=1，2，…，m)用來記錄螞蟻k當前走過的城市，[tabu]k中的元素將隨著進化過程做動態(tài)的調(diào)整。螞蟻在運動的過程中，根據(jù)鏈表中各條路徑上的信息素以及路徑的啟發(fā)信息來計算轉(zhuǎn)移概率Pkij(t),r ,、T?np(t) i—i- ,jg[allowed];j①TL,Pk(t)=仲g[allowed]t叩p(t)J k ⑼0,else第五章改進的算法基本流程初始化各參數(shù)a,P,p,m,Tmin,Tmax,n,n每只螞蟻從起點城市開始周游城市，利用禁忌表來判斷螞蟻的一次周游是否完成；若沒有完成，則根據(jù)式子(8)計算出來的轉(zhuǎn)移概率來決定選擇下一個城市，并更改禁忌表；對每只螞蟻經(jīng)過的路徑執(zhí)行局部更新規(guī)則(根據(jù)(6)式調(diào)整參數(shù);根據(jù)(7)式對信息素進行更新),得到新的最優(yōu)解，并對最優(yōu)解進行更新；若尚未達到指定的周游次數(shù)，轉(zhuǎn)到步驟(2)輸出最優(yōu)解。第六章結(jié)論本文通過對蟻群優(yōu)化算法的基本原理和模型進行分析來解決TSP問題并且提出了一種改進的蟻群算法，該方法通過改變信息素和揮發(fā)系數(shù)的更新方式、構(gòu)造信息素鏈表和禁忌鏈表等方法來加快算法的收斂速度，擴大子解的搜索空間，有效地緩解了基本蟻群算法容易出現(xiàn)的早熟、停滯現(xiàn)象。實驗表明改進后的算法有效地提高了蟻群的收斂速度，并且表現(xiàn)出良好的穩(wěn)定性。蟻群算法是一種原理相對簡單的新興仿生進化算法,在眾多領(lǐng)域中已展現(xiàn)出它的特點和魅力。但蟻群算法理論與遺傳算法、禁忌搜索算法等理論相比還遠不成熟，實際應用也遠未挖掘出其真正潛力，還有很多富有挑戰(zhàn)性的課題亟待解決。主要體現(xiàn)在以下幾個方面：⑴加強蟻群算法的基礎(chǔ)理論研究，進一步發(fā)展新的數(shù)學分析和建模工具，尤其對算法的基礎(chǔ)理論研究非常重要，包括對解決不同優(yōu)化問題時收斂性和收斂速度的估計、避免陷入局部最優(yōu)值、魯棒性分析以及A,B,F,Q等參數(shù)的設(shè)計理論。目前尚未發(fā)現(xiàn)有關(guān)合理選擇螞蟻數(shù)量以及算法運行時間數(shù)學分析的論述。因此，該算法的數(shù)學基礎(chǔ)理論研究將成為今后研究的一個重要課題。⑵可將蟻群算法與其他類型方法綜合使用以開發(fā)混合優(yōu)化方法，進而發(fā)展思想更先進、功能更強大、解決更復雜系統(tǒng)的智能行為。將蟻群算法與神經(jīng)網(wǎng)絡(luò)、模糊控制、遺傳算法、模擬退火算法等相融合，必將成為今后蟻群算法領(lǐng)域內(nèi)新的研究熱點。⑶新的理論必須通過實踐進行檢驗，在實踐過程中，可以發(fā)現(xiàn)新問題，從而促進理論向前發(fā)展。近年來，蟻群算法雖在眾多領(lǐng)域得到了推廣應用，但其中大多僅僅是對蟻群算法在該領(lǐng)域應用的一個簡單仿真。因此，今后應充分挖掘蟻群算法在實際應用中的潛力，在對現(xiàn)有應用領(lǐng)域進行深化研究的同時，進一步擴大其應用范圍。此外，蟻群算法的硬件實現(xiàn)也將成為研究的熱點方向之一。對上述問題的深入研究必將大大促進蟻群算法理論和應用的發(fā)展，蟻群算法也必將在智能計算領(lǐng)域中展現(xiàn)出更加光明的前景。參考文獻:吳桂芳，