【文章內(nèi)容簡介】 t=1時，8只螞蟻從巢穴出發(fā)已經(jīng)移動到了A點。這8只螞蟻會有一半的螞蟻選擇走AB，另外一半的螞蟻選擇走AC。在t=4時，最先到達食物源的4只螞蟻將會原路返回。在t=5時，原路返回的4只螞蟻走到了D點。這時路徑BD、CD上的信息素的數(shù)量相同。因此2只螞蟻選擇走DB，2只螞蟻選擇走DC。在t=8時，有2只螞蟻會走回到巢穴中，此時CA、DC、DB上卻各有2只螞蟻。在t=9時，最先回到巢穴的2只螞蟻再次出發(fā)走到A點，這2只螞蟻將會再次選擇是走AB還是走AC。 螞蟻從巢穴至食物源的模擬圖在t=9時，路徑AB上的信息素數(shù)量是8而路徑AC上的信息素量是6，因此有超過50%的螞蟻會選擇路徑A，從而使路徑AB上的信息素比AC上的信息素量進一步加大。當螞蟻覓食的次數(shù)不斷增多，路徑AB上的信息素的量和路徑AC上的信息素的量的差距也會越來越大，當覓食的次數(shù)無限增大時，所有的螞蟻都會選擇路徑“巢穴ABD食物”。 蟻群系統(tǒng)解決TSP的基本步驟下面以TSP問題為例說明蟻群算法流程[47]： 1. nc=0(nc為迭代步數(shù)或搜索次數(shù))；將各τij和錯誤！未找到引用源。Δτij初始化；將m只螞蟻置于n個頂點上；2．將各螞蟻的初始出發(fā)點置于當前解集中；對每個螞蟻k，按偽隨機比例規(guī)則（）移至下一頂點j；將頂點j置于當前解集； ()其中，J是根據(jù)概率公式（）給出的概率分布產(chǎn)生出來的一個隨機變量。 ()allowedk表示螞蟻k下一步允許選擇的城市集合，ηij=1/dij。3. 計算各螞蟻的目標函數(shù)值；記錄當前的最好解；4. 按更新方程（）修改軌跡強度； () ()5. 對各邊?。╥ , j），置nc=nc+1；6. 如果nc預定的迭代次數(shù)且無退化行為（即找到的都是相同解），則轉步驟2；7. 輸出目前最好解。 蟻群算法參數(shù)的控制選擇 算法中參數(shù)的選擇至關重要，如果選擇不當，對算法的適用性影響很大，嚴重可能導致算法的整體性能變差。以下介紹本文對各參數(shù)的選擇。參數(shù)a反映了在搜索過程中，螞蟻所積累的信息素在指導螞蟻搜索路徑的相對重要性[48]。如果a的值很大，就表示信息素量越重要，那么螞蟻選擇之前螞蟻所經(jīng)過的邊就越大，這樣搜索的隨機性、搜索范圍就會減小，從而使搜索易于陷入局部最優(yōu)解。如果a的值很小，就表示信息素的重要性較低，這說明螞蟻主要依靠啟發(fā)式因子β來引導搜索。所以a的值不同，算法求解的結果也不同，a值的恰當選擇，會使算法取得良好的效果。在文獻[10]中通過實驗認為a的取值范圍[1，2]是比較合理的，本文a的取值為a=1。隨著時間的推移，在蟻群算法中，以前螞蟻所留下的信息素將不斷地揮發(fā)，參數(shù)β表示信息素軌跡揮發(fā)的重要性，直接影響著算法的收斂速度和全局搜索能力。為了確保殘留信息的適應度，β的值選取應在0β1。因為β如果過小，啟發(fā)信息的作用會小，不僅使收斂速度受到影響，也會使大多數(shù)螞蟻都沿著同一條路徑搜索，致使算法陷入停滯局面；若β取值過大，會使路徑搜索范圍減小，以前訪問過的城市可能再次被訪問，對全局搜索能力的影響較大。本文β取β=2。從公式（）我們以知道，當q q0時，算法采用的是隨機搜索，當q q0時算法采用的是確定搜索。顯然，當q0較小時，更多的采用隨機搜索能夠增大搜索空間，提高找到最優(yōu)解的概率；當q0較大時，更少地采用隨機搜索能夠快速收斂。因此q0需要選擇一個大小適中的值，讓算法能夠盡可能快的收斂并且能夠盡可能的找到全局最優(yōu)解。通過實驗發(fā)現(xiàn)，當q0取值在[，]時，算法具有比較好的性能。本文q0 取值為q0 = 。 在搜尋的過程中，螞蟻表現(xiàn)出的復雜而有序的行為，與群體間的交流協(xié)作是分不開的。種群大小直接影響著算法的執(zhí)行效率和收斂速度，所以種群大小的選取也至關重要，如果m太小，尤其是所選問題規(guī)模較大時，會使搜索的隨機性減弱，收斂速度加快，易于過早出現(xiàn)停滯現(xiàn)象，不能保證找到最優(yōu)解；若m太大時，盡管提高了算法的隨機搜索能力，增加了找到最優(yōu)解的概率，但也增加了算法的復雜性，收斂速度減慢。本文中種群數(shù)量取m=20。167。 基于排序的螞蟻系統(tǒng)基于排序的螞蟻系統(tǒng)是在螞蟻系統(tǒng)或精英螞蟻系統(tǒng)中針對螞蟻釋放信息素的缺點進行改進的。在精英螞蟻系統(tǒng)和螞蟻系統(tǒng)中，更新信息素時會對系統(tǒng)中所有的螞蟻進行信息素的更新，這樣，所有的螞蟻所經(jīng)過的路徑上的信息素濃度差異會越來越小，使得螞蟻選擇出最優(yōu)路徑的可能性變小。為了解決這個問題，基于排序的螞蟻系統(tǒng)改進如下[49]：1. 在所有螞蟻都構建路徑以后，把螞蟻所走的路徑按長度大小進行排序，只允許構建至今最優(yōu)路徑的螞蟻和排在最前面的(m1)只螞蟻釋放信息素。2. 信息素更新規(guī)則如下： 其中。表示排在前面的第t只螞蟻所建立的路徑的長度，為至今最優(yōu)路徑的長度。 167。 MAX—MIN螞蟻系統(tǒng)MAX—MIN螞蟻系統(tǒng)是由T．Stuetzle和HH．Hoos提出的，由于在蟻群系統(tǒng)中，只允許最優(yōu)螞蟻釋放信息素，這樣一些邊上信息素就會過快增加，很容易出現(xiàn)過早的停滯現(xiàn)象。所以最大最小螞蟻系統(tǒng)提出如下改進思想[50]：1．將信息素濃度值設置在一個區(qū)間內(nèi)。2．將信息素的初值設為一個最大值。以便螞蟻在開始階段有更大的搜索空間。3．在每次迭代過程中，只允許一只螞蟻進行信息素更新。更新如下：其中，被允許釋放信息素的螞蟻是當前具有最優(yōu)路徑的螞蟻。當被選擇的邊由于正反饋機制使得邊上的信息素明顯高于其他邊時，就會出現(xiàn)停滯現(xiàn)象。在MAX—MIN螞蟻系統(tǒng)中將每條邊上的信息素濃度值限定在一個區(qū)間之內(nèi)。這樣，位于城市i的螞蟻在選擇下一個訪問城市j時的概率就會被限制在之內(nèi)，并且路徑ij被選擇的概率pij的取值范圍是。167。 小結本章以蟻群算法基本原理為開端，系統(tǒng)的介紹了蟻群算法的模型，參數(shù)選擇和以TSP問題為例的算法流程和步驟。并對蟻群算法的研究進展進行了綜述。最后對基于排序的螞蟻系統(tǒng)和最大最小螞蟻系統(tǒng)進行了簡述。第三章 改進的混合型蟻群算法及其在TSP中的應用167。 改進策略 基本蟻群算法ACS在求解TSP問題時經(jīng)常會陷入局部最優(yōu)解而得不到全局最優(yōu)解，為了能夠提高基本蟻群算法找到最優(yōu)解的能力，可以將基本蟻群算法和啟發(fā)式算法結合在一起形成混合型蟻群算法。常見的啟發(fā)式算法包括最近鄰算法、插入式算法、最小樹算法和ropt局部搜索算法等[10]。ropt算法是局部搜索算法的一種，本文采取了2opt局部搜索算法。下面將簡單介紹下局部搜索算法、2opt算法和改進的混合型蟻群算法。 局部搜索法 局部搜索法以貪心思想為基礎，利用鄰域函數(shù)總是向著離目標最近的方向進行搜索的。也就是說利用鄰域函數(shù)，從某個初始解開始，持續(xù)不斷地在當前解的領域范圍內(nèi)搜索更好的解。如果找到比當前解更好的解，則讓它成為新解集，繼續(xù)重復上面的過程；否則，終止搜索過程，還原舊解集解。當然，搜索的過程中也可能陷入局部最優(yōu)解，或者錯過最優(yōu)解，在實際應用中可采取適當?shù)姆椒▽植孔顑?yōu)問題、步長問題、起始點問題等進行修正，以提高算法的效能。 2opt算法ropt算法是一種局部搜索策略。在得到一個可行解后，每次交換可行解中的r條邊來改進可行解。直觀而言每次進行對換的邊數(shù)r越大，我們找到最優(yōu)解的概率越大，但是實際實驗結果證明r取值為3時，能夠獲得比取值為2時更好的解，但是r取值5或更大的值時算法不能獲得比r取值為3時更好的解。r取值越大時算法的計算量就越大，為了能夠較快的得到最優(yōu)解，本文r取值為2。該算法是對局部搜索算法的一種改進，它的主要思想是：依次交換所獲得的解中的兩條邊，交換后重新計算得到的路徑的長度，如果得到的路徑長度小于交換前的長度，則保留新的路徑順序，否則保持原來的行進城市順序不變。我們以求解TSP問題為例進行說明。假設一個旅行商必須要經(jīng)過ABCD 這4個城市，目標函數(shù)是路程最短。我們可以先任選一個可行解S={A,B,C,D}，并假設S是最優(yōu)解Smin。然后使用2opt算法進行問題的求解—對S中的任意兩個元素進行位置對調(diào)，一共有6種可能，分別是：S1={B,A,C,D}。S2={B,C,A,D}。S3={B,C,D,A}。S4={A,C,B,D}。S5={A,C,D,B}。S6={A,B,D,C}.即每一步對調(diào)其中的兩個元素，獲得一個新的可行解。將可行解代入目標函數(shù)得到目標函數(shù)值，并與Smin的目標函數(shù)值比較，取兩者目標函數(shù)值較小的可行解為Smin，然后依次循環(huán)上述步驟，分別代入S2~S6，便可找到最優(yōu)解。 改進的混合型蟻群算法 本文在ACS基礎上進行了改進，改進內(nèi)容包括以下三點：（1）為了提高找到最優(yōu)解的概率，使用2opt局部搜索策略對每一次迭代中的最優(yōu)解和次優(yōu)解進行二次搜索。這里不對所有螞蟻走過的路徑執(zhí)行2opt局部搜索策略，其原因是，對排名靠后的螞蟻執(zhí)行2opt局部搜索策略是基本得不到比當前最優(yōu)解和次優(yōu)解更好的解的。（2）在執(zhí)行完2opt局部搜索策略之后，重新對得到的結果排序，然后對排名第一和第二的路徑執(zhí)行全局信息素更新。Δτij的取值按照公式（）進行更新： () 其中，Lbest是全局最優(yōu)解的路徑長度，Lbest2是全局次優(yōu)解的路徑長度。對排名第二的路徑也執(zhí)行更新是為了擴大搜索范圍，使算法避免停留在局部最優(yōu)解上，而信息素更新權值取值小于1的原因是,使全局最優(yōu)解和全局次優(yōu)解路徑上的信息素濃度保持一定的差距。（3） 為了防止程序進入停滯現(xiàn)象，為全局信息素設置最大值和最小值，最大值和最小值的取值采用公式（）的啟發(fā)式規(guī)則。全局信息素的最小值取值為最大值的1%，即Δτmin = ()167。 改進的蟻群算法求解TSP問題為了證明和驗證改進的蟻群算法的有效性，將改進的蟻群算法在TSP問題實例上做了實驗。用于數(shù)值實驗的TSP實例可以在 TSPLIB中找到。本文選取了d19eil7kroa200、krob150、kroc100、lin10pr12pr13pr14pr15rd100、rat9u159這13個TSP問題實例做為研究對象。本次采用MATLAB工具進行模擬，參數(shù)選取為：m=20，α=1，β=2，ρ=。為了證明算法的有效性，將本論文的結果與文獻5文獻52同本論文所共同選取的5個實例得到的最優(yōu)解進行了比較。表 與2種改進蟻群算法比較5個TSP實例的近似解實例文獻51近似解文獻52近似解本文近似解最優(yōu)解eil76552547544538kroa20029875296742953429368lin10514554143821438214379pr136100176978779680096772pr15273881739337368373682，本文算法所得到的近似解都優(yōu)于文獻[51]和文獻[52]中的近似解，且與最優(yōu)解的差距非常小，其中pr152得到的解和最優(yōu)解相差只有1，說明本文的算法具有很好的求解能力。本算法求解這幾個問題所得到的運行結果路線圖,~。 eil76運行結果線路圖 kroa200運行結果線路圖 lin105運行結果線路圖 pr136運行結果線路圖 pr152運行結果線路圖為了進一步證明本文算法的有效性，將其他8個問題的結果與文獻[53]中作者所介紹的兩種自組織算法（NCSOM, ASOM）所得的結果做了比較，其比較結果如表2所示。，本文算法的求解能力也優(yōu)于NCSOM、ASOM的結果。并且rd100得到了和已知最優(yōu)解相同的解，pr144和u159得到了優(yōu)于已知最優(yōu)解的解。下面給出這三個問題求解的城市訪問順序。rd100的城市訪問順序是：7 34 41 22 5 61 11 52 45 16 31 84 88 66 98 94 6 79 53 99 47 57 36 64 91 81 80 30 48 65 90 51 83 68 71 8 69 60 1 18 62 87 15 63 86 97 67 13 49 21 75 82 85 14 12 4 32 9 26 74 20 78 3 33 10 27 92 17 72 70 38 54 73 50 46 56 19 37 28 93 77 95 59 76 58 89 2 23 35 29 44 100 39 96 55 40 43 25 24 42表 8個TSP實例用算法 NCSOM, ASOM和改進算法比較的結果序號實例城市數(shù)最優(yōu)解三種算法近似最優(yōu)解誤差(%)1 d19819815780NCSOM17413ASOM16054改進算法160342krob15015026130NCSOM27336ASOM26716改進算法261873kroc10010020749NCSOM21470ASOM20911改進算法207694pr12412459030NCSOM59516ASOM59112改進算法590745rat99991211NCSOM1258ASOM1228