【正文】 廣泛。 。它的思想是從某一初始解開始，通過對當(dāng)前解進行不斷地局部調(diào)整來達到預(yù)期的效果?？傮w上來說，蟻群優(yōu)化算法能夠較好的求解VRP問題，但是當(dāng)問題的規(guī)模變大時，蟻群優(yōu)化算法的運行時間較長且易陷入局部最優(yōu)解。167。其次，把改進的算法應(yīng)用到了中國旅行商問題，對實驗結(jié)果進行了詳細地分析，并且對改進算法通過統(tǒng)計邊數(shù)的方法對TSP問題的種群多樣性進行了分析，通過實驗仿真與基本蟻群算法從平均的邊數(shù)和、最大的邊數(shù)以及最小的邊數(shù)和進行了比較分析，從數(shù)據(jù)上說明了改進的算法具有種群多樣性。167。第二章：在介紹基本蟻群算法原理及數(shù)學(xué)模型的基礎(chǔ)上，給出了以TSP問題為例的蟻群系統(tǒng)的算法流程，分析了蟻群算法的重要參數(shù)對蟻群算法性能的選擇控制，并對國內(nèi)外蟻群算法的研究現(xiàn)狀進行了總結(jié)與概括，還重點介紹了兩種典型、有效的改進的蟻群算法：最大最小螞蟻系統(tǒng)和基于排序的螞蟻系統(tǒng)。第三章：詳細地介紹了一種改進的混合型蟻群算法，在ASC的基礎(chǔ)上主要提出了三處改進：加入了2 opt算法；基于排序的思想：對排在第一和第二的螞蟻進行信息素的更新；為了防止程序陷入停滯，給全局信息素設(shè)置最大值和最小值。第四章：介紹了改進的混合型蟻群算法在10個典型的VRP問題中的應(yīng)用，并詳細地介紹了算法的流程。第二章 蟻群算法167。1995年，、引入了局部信息素更新機制和全局信息，避免了過早停滯[28]。1997年，（RANK—BASED AS）[30]，在所有螞蟻都走完一遍后，對螞蟻的路徑長度進行排序，只允許排列在最前面的m只螞蟻和生成最優(yōu)路徑的螞蟻釋放信息素。雖然國內(nèi)對蟻群算法的引入研究開始的比較晚，但是已在幾年之間發(fā)展成為熱點領(lǐng)域。1999年，吳慶紅和張紀(jì)會等人[34]引入2opt變異機制，提出了具有變異特征的蟻群算法。為了克服算法易于陷入局部最優(yōu)解的劣勢，王穎和謝劍英提出了一種自適應(yīng)的蟻群算法[36]，覃剛力等人通過調(diào)整路徑上的信息素的變化，提出了自適應(yīng)調(diào)整信息素的蟻群算法[37]。1994年,A coloni等人將螞蟻系統(tǒng)應(yīng)用于車間作業(yè)調(diào)度問題[38]。1999年，V Maniozzo成功地將螞蟻系統(tǒng)應(yīng)用于指派問題[40]，而后Gambardellab又發(fā)表了用蟻群系統(tǒng)來解決指派問題的相關(guān)論文[41]。Gambardella對車輛路徑問題進行了更深入的研究，得到了比以往更優(yōu)的解[43]。2003年汪鐳、吳啟迪[45]把蟻群算法用于解決系統(tǒng)識別。167。螞蟻在尋找食物的過程中，會在其經(jīng)過的路徑上釋放一種被稱為信息素（pheromone）的化學(xué)物質(zhì)，信息素能夠沉積在路徑上，并隨著時間的推移逐漸揮發(fā)。經(jīng)過一段時間的搜索后，螞蟻最終可以找到一條從巢穴到食物源的最短路徑。實驗中Jean Louis Deneubourg及其同事建造了一座有兩個分支的橋，其中一個分支的長度是另一個分支的二倍，同時把蟻巢和食物源分隔開來，實驗發(fā)現(xiàn)，螞蟻通常在幾分鐘內(nèi)就選擇了較短的那條分支[46]?，F(xiàn)假設(shè)路徑“巢穴ACD食物”和路徑“巢穴ABD食物”的長度分別是6和4。在開始前所有路徑上的信息素都為0。這8只螞蟻會有一半的螞蟻選擇走AB，另外一半的螞蟻選擇走AC。在t=5時，原路返回的4只螞蟻走到了D點。因此2只螞蟻選擇走DB，2只螞蟻選擇走DC。在t=9時，最先回到巢穴的2只螞蟻再次出發(fā)走到A點，這2只螞蟻將會再次選擇是走AB還是走AC。當(dāng)螞蟻覓食的次數(shù)不斷增多，路徑AB上的信息素的量和路徑AC上的信息素的量的差距也會越來越大，當(dāng)覓食的次數(shù)無限增大時，所有的螞蟻都會選擇路徑“巢穴ABD食物”。Δτij初始化；將m只螞蟻置于n個頂點上；2．將各螞蟻的初始出發(fā)點置于當(dāng)前解集中；對每個螞蟻k，按偽隨機比例規(guī)則（）移至下一頂點j；將頂點j置于當(dāng)前解集； ()其中，J是根據(jù)概率公式（）給出的概率分布產(chǎn)生出來的一個隨機變量。3. 計算各螞蟻的目標(biāo)函數(shù)值；記錄當(dāng)前的最好解；4. 按更新方程（）修改軌跡強度； () ()5. 對各邊?。╥ , j），置nc=nc+1；6. 如果nc預(yù)定的迭代次數(shù)且無退化行為（即找到的都是相同解），則轉(zhuǎn)步驟2；7. 輸出目前最好解。以下介紹本文對各參數(shù)的選擇。如果a的值很大，就表示信息素量越重要，那么螞蟻選擇之前螞蟻所經(jīng)過的邊就越大，這樣搜索的隨機性、搜索范圍就會減小，從而使搜索易于陷入局部最優(yōu)解。所以a的值不同，算法求解的結(jié)果也不同，a值的恰當(dāng)選擇，會使算法取得良好的效果。隨著時間的推移，在蟻群算法中，以前螞蟻所留下的信息素將不斷地?fù)]發(fā)，參數(shù)β表示信息素軌跡揮發(fā)的重要性，直接影響著算法的收斂速度和全局搜索能力。因為β如果過小，啟發(fā)信息的作用會小，不僅使收斂速度受到影響，也會使大多數(shù)螞蟻都沿著同一條路徑搜索，致使算法陷入停滯局面；若β取值過大，會使路徑搜索范圍減小，以前訪問過的城市可能再次被訪問，對全局搜索能力的影響較大。從公式（）我們以知道，當(dāng)q q0時，算法采用的是隨機搜索，當(dāng)q q0時算法采用的是確定搜索。因此q0需要選擇一個大小適中的值，讓算法能夠盡可能快的收斂并且能夠盡可能的找到全局最優(yōu)解。本文q0 取值為q0 = 。種群大小直接影響著算法的執(zhí)行效率和收斂速度，所以種群大小的選取也至關(guān)重要，如果m太小，尤其是所選問題規(guī)模較大時，會使搜索的隨機性減弱，收斂速度加快，易于過早出現(xiàn)停滯現(xiàn)象，不能保證找到最優(yōu)解；若m太大時，盡管提高了算法的隨機搜索能力，增加了找到最優(yōu)解的概率，但也增加了算法的復(fù)雜性，收斂速度減慢。167。在精英螞蟻系統(tǒng)和螞蟻系統(tǒng)中，更新信息素時會對系統(tǒng)中所有的螞蟻進行信息素的更新，這樣，所有的螞蟻所經(jīng)過的路徑上的信息素濃度差異會越來越小，使得螞蟻選擇出最優(yōu)路徑的可能性變小。2. 信息素更新規(guī)則如下： 其中。 167。所以最大最小螞蟻系統(tǒng)提出如下改進思想[50]：1．將信息素濃度值設(shè)置在一個區(qū)間內(nèi)。以便螞蟻在開始階段有更大的搜索空間。更新如下：其中，被允許釋放信息素的螞蟻是當(dāng)前具有最優(yōu)路徑的螞蟻。在MAX—MIN螞蟻系統(tǒng)中將每條邊上的信息素濃度值限定在一個區(qū)間之內(nèi)。167。并對蟻群算法的研究進展進行了綜述。第三章 改進的混合型蟻群算法及其在TSP中的應(yīng)用167。常見的啟發(fā)式算法包括最近鄰算法、插入式算法、最小樹算法和ropt局部搜索算法等[10]。下面將簡單介紹下局部搜索算法、2opt算法和改進的混合型蟻群算法。也就是說利用鄰域函數(shù)，從某個初始解開始，持續(xù)不斷地在當(dāng)前解的領(lǐng)域范圍內(nèi)搜索更好的解。當(dāng)然，搜索的過程中也可能陷入局部最優(yōu)解，或者錯過最優(yōu)解，在實際應(yīng)用中可采取適當(dāng)?shù)姆椒▽植孔顑?yōu)問題、步長問題、起始點問題等進行修正，以提高算法的效能。在得到一個可行解后，每次交換可行解中的r條邊來改進可行解。r取值越大時算法的計算量就越大，為了能夠較快的得到最優(yōu)解，本文r取值為2。我們以求解TSP問題為例進行說明。我們可以先任選一個可行解S={A,B,C,D}，并假設(shè)S是最優(yōu)解Smin。S2={B,C,A,D}。S4={A,C,B,D}。S6={A,B,D,C}.即每一步對調(diào)其中的兩個元素，獲得一個新的可行解。 改進的混合型蟻群算法 本文在ACS基礎(chǔ)上進行了改進，改進內(nèi)容包括以下三點：（1）為了提高找到最優(yōu)解的概率，使用2opt局部搜索策略對每一次迭代中的最優(yōu)解和次優(yōu)解進行二次搜索。（2）在執(zhí)行完2opt局部搜索策略之后，重新對得到的結(jié)果排序，然后對排名第一和第二的路徑執(zhí)行全局信息素更新。對排名第二的路徑也執(zhí)行更新是為了擴大搜索范圍，使算法避免停留在局部最優(yōu)解上，而信息素更新權(quán)值取值小于1的原因是,使全局最優(yōu)解和全局次優(yōu)解路徑上的信息素濃度保持一定的差距。全局信息素的最小值取值為最大值的1%，即Δτmin = ()167。用于數(shù)值實驗的TSP實例可以在 TSPLIB中找到。本次采用MATLAB工具進行模擬，參數(shù)選取為：m=20，α=1，β=2，ρ=。表 與2種改進蟻群算法比較5個TSP實例的近似解實例文獻51近似解文獻52近似解本文近似解最優(yōu)解eil76552547544538kroa20029875296742953429368lin10514554143821438214379pr136100176978779680096772pr15273881739337368373682，本文算法所得到的近似解都優(yōu)于文獻[51]和文獻[52]中的近似解，且與最優(yōu)解的差距非常小，其中pr152得到的解和最優(yōu)解相差只有1，說明本文的算法具有很好的求解能力。 eil76運行結(jié)果線路圖 kroa200運行結(jié)果線路圖 lin105運行結(jié)果線路圖 pr136運行結(jié)果線路圖 pr152運行結(jié)果線路圖為了進一步證明本文算法的有效性，將其他8個問題的結(jié)果與文獻[53]中作者所介紹的兩種自組織算法（NCSOM, ASOM）所得的結(jié)果做了比較，其比較結(jié)果如表2所示。并且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和改進算法比較的結(jié)果序號實例城市數(shù)最優(yōu)解三種算法近似最優(yōu)解誤差(%)1 d19819815780NCSOM17413ASOM16054改進算法160342krob15015026130NCSOM27336ASOM26716改進算法261873kroc10010020749NCSOM21470ASOM20911改進算法207694pr12412459030NCSOM59516ASOM59112改進算法590745rat99991211NCSOM1258ASOM1228改進算法12196rd100997910NCSOM8092ASOM7960改進算法79107pr14414458537NCSOM60286ASOM59051改進算法585358u15915942080NCSOM43381ASOM42794改進算法42075pr144的城市訪問順序是：119 118 117 116 92 91 73 74 75 76 77 78 89 90 98 97 94 93 95 96 99 100 101 102 103 88 87 61 62 63 64 65 66 67 68 69 70 72 71 45 44 43 14 13 12 11 10 9 7 8 19 20 18 17 16 15 42 41 21 40 39 38 37 23 22 6 5 4 3 1 2 28 29 27 26 25 24 36 35 30 34 33 32 31 49 50 51 52 53 54 55 56 57 58 46 47 48 59 60 79 80 81 82 83 84 85 86 109 108 105 104 106 107 110 111 112 113 114 144 143 142 141 140 139 138 137 136 135 134 133 132 131 115 130 129 128 127 126 125 124 123 122 121 120u159的城市訪問順序是：139 140 138 137 136 135 133 134 132 131 128 127 126 125 129 124 130 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 93 92 91 90 89 94 88 87 96 95 107 106 105 104 103 102 101 100 99 98 97 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 36 37 35 34 33 32 31 30 29 28 27 26 25