【正文】 力的影響較大。以下介紹本文對各參數(shù)的選擇。在t=9時，最先回到巢穴的2只螞蟻再次出發(fā)走到A點，這2只螞蟻將會再次選擇是走AB還是走AC。在開始前所有路徑上的信息素都為0。螞蟻在尋找食物的過程中，會在其經(jīng)過的路徑上釋放一種被稱為信息素（pheromone）的化學(xué)物質(zhì)，信息素能夠沉積在路徑上，并隨著時間的推移逐漸揮發(fā)。1999年，V Maniozzo成功地將螞蟻系統(tǒng)應(yīng)用于指派問題[40]，而后Gambardellab又發(fā)表了用蟻群系統(tǒng)來解決指派問題的相關(guān)論文[41]。雖然國內(nèi)對蟻群算法的引入研究開始的比較晚，但是已在幾年之間發(fā)展成為熱點領(lǐng)域。第四章：介紹了改進的混合型蟻群算法在10個典型的VRP問題中的應(yīng)用，并詳細地介紹了算法的流程。其次，把改進的算法應(yīng)用到了中國旅行商問題，對實驗結(jié)果進行了詳細地分析，并且對改進算法通過統(tǒng)計邊數(shù)的方法對TSP問題的種群多樣性進行了分析，通過實驗仿真與基本蟻群算法從平均的邊數(shù)和、最大的邊數(shù)以及最小的邊數(shù)和進行了比較分析，從數(shù)據(jù)上說明了改進的算法具有種群多樣性。 。假設(shè)每一個客戶只能被訪問一次，每輛車所訪問的城市的需求總和不能超過車輛的負載能力，并且所使用的車輛數(shù)量是固定的。2) 總長限制。167。后來研究者提出使用近似算法或啟發(fā)式算法進行研究，并且融合多種方法成為研究主流。下面我們用數(shù)學(xué)的語言進行描述[10]：記G=(V,E)為賦權(quán)圖，V=(1,2…..,n)為頂點集，E為邊集，各頂點間的距離dij已知(dij 0，dii=∞，i，j∈V)。在求解著名復(fù)雜的優(yōu)化問題——旅行商問題（Traveling Salesman Problem）上取得成效以后，其應(yīng)用已經(jīng)逐漸滲透到各個領(lǐng)域，比如車輛路徑問題(Vehicle Routing Problem)[4,5]、工件的排序問題[6]、圖著色問題[7,8]等。 37167。 改進策略 15 局部搜索法 15 2opt算法 15 改進的混合型蟻群算法 16167。 VRP問題 3 VRP問題的提出 3 VRP問題的研究現(xiàn)狀 5167。通過仿真實驗可以看出本文改進的算法在求解TSP問題時具有很好的效果，在求解很多問題時已經(jīng)非常接近最優(yōu)解或者優(yōu)于最優(yōu)解，和最優(yōu)解相差的百分比基本都在1%以下，并和兩種最新改進的蟻群算法以及兩種自組織算法進行比較，比較結(jié)果充分證明了該改進算法的有效性。在眾多求解TSP算法中，蟻群算法具有較好的性能，該仿生智能算法和傳統(tǒng)的算法截然不同，具有魯棒性、正反饋、并行性和易與其他方法相結(jié)合等特點。 the better results indicated us our mixed ant colony algorithm is a better one to solve the VRP.Key words: Mixed Ant Colony Algorithm, TSP, population diversity, VRP目 錄摘 要 Abstract 第一章 緒論 1167。 基于排序的螞蟻系統(tǒng) 12167。 求解VRP問題的算法流程 30 求解VRP與求解TSP的不同點 30 求解VRP的程序流程圖 30167。螞蟻是一種群居性生活的動物，社會結(jié)構(gòu)和分工明確，他們通過釋放信息素來搜索最短路徑，螞蟻在運動過程中能夠感知這種物質(zhì)的存在及強度，并借此來引導(dǎo)自己的行動方向，濃度越高吸引的螞蟻就越多，經(jīng)過一段時間的搜索，個體間通過這種信息的交流最終達到搜索食物的目的。 TSP問題 TSP問題的提出TSP問題是組合優(yōu)化問題中最典型的問題，最早在1759年由歐拉提出[9]。當(dāng)對所有，有不等式成立時，被稱為是滿足三角不等式的，簡記為ΔTSP。TSP問題是眾多領(lǐng)域中出現(xiàn)的優(yōu)化問題的集中概括和簡化形式，是各種啟發(fā)式算法的間接比較標準[12]，也就是說假如提出的一個算法在求解TSP問題是有效的，那么在其他類型的組合優(yōu)化問題上稍加修改也將會取得良好的性能，因此，該算法已經(jīng)成為了測試新的算法或算法間進行比較的標準問題，具有重大的理論研究意義。配送中心 VRP示意圖 常見的約束條件1) 容量限制。CVRP問題是實際應(yīng)用中最為廣泛和最為基本的一類問題，研究CVRP問題對優(yōu)化物流配送具有十分重要的意義。隨著電子商務(wù)的崛起和物流越來越受到人們的重視，國內(nèi)研究VRP問題的人也越來越多。由于精確法的局限性，所以在求解大規(guī)模VRP問題上尋找到求解比較理想的可行解的近似算法是必要和現(xiàn)實的。因此，利用蟻群優(yōu)化算法易于和其他算法結(jié)合的特點，本文將蟻群優(yōu)化算法和局部搜索策略相結(jié)合來求解VRP問題。這些基本理論與思想為第三章提出的改進策略奠定了基礎(chǔ)。1996年，“Ant System：Optimization by a Colony of Cooperating Agents”一文[29]，提出了蟻群系統(tǒng)(ACS)，詳細的論述了蟻群算法的原理及其應(yīng)用。蟻群算法不僅在理論方面引起國際學(xué)術(shù)界許多研究學(xué)者的重視，在應(yīng)用方面也得到了廣泛關(guān)注，使蟻群算法除了應(yīng)用于TSP問題以外，在其他領(lǐng)域也得到了迅速的擴大。所以，對蟻群算法理論及其應(yīng)用的探索定將成為一個長期的研究熱點問題，具有更加廣闊的科研價值和發(fā)展前景。Jean Louis Deneubourg 。這時路徑BD、CD上的信息素的數(shù)量相同。 ()allowedk表示螞蟻k下一步允許選擇的城市集合，ηij=1/dij。在文獻[10]中通過實驗認為a的取值范圍[1，2]是比較合理的，本文a的取值為a=1。通過實驗發(fā)現(xiàn)，當(dāng)q0取值在[，]時，算法具有比較好的性能。為了解決這個問題，基于排序的螞蟻系統(tǒng)改進如下[49]：1. 在所有螞蟻都構(gòu)建路徑以后，把螞蟻所走的路徑按長度大小進行排序，只允許構(gòu)建至今最優(yōu)路徑的螞蟻和排在最前面的(m1)只螞蟻釋放信息素。3．在每次迭代過程中，只允許一只螞蟻進行信息素更新。最后對基于排序的螞蟻系統(tǒng)和最大最小螞蟻系統(tǒng)進行了簡述。如果找到比當(dāng)前解更好的解，則讓它成為新解集，繼續(xù)重復(fù)上面的過程；否則，終止搜索過程，還原舊解集解。假設(shè)一個旅行商必須要經(jīng)過ABCD 這4個城市，目標函數(shù)是路程最短。將可行解代入目標函數(shù)得到目標函數(shù)值，并與Smin的目標函數(shù)值比較，取兩者目標函數(shù)值較小的可行解為Smin，然后依次循環(huán)上述步驟，分別代入S2~S6，便可找到最優(yōu)解。 改進的蟻群算法求解TSP問題為了證明和驗證改進的蟻群算法的有效性，將改進的蟻群算法在TSP問題實例上做了實驗。，本文算法的求解能力也優(yōu)于NCSOM、ASOM的結(jié)果。 改進的蟻群算法求解中國旅行商問題 中國旅行商問題描述中國旅行商問題 (CTSP)是典型的TSP問題，它是針對中國不同規(guī)模的城市旅行商問題進行研究的，自1991年以來，許多學(xué)者就開始進行了研究，主要有CTSP144個城市，CTSP100個城市，CTSP45個城市，CTSP34個城市和CTSP31個城市[54]。3238 1229。 1332 695。3429 1908。2370 2975] 模擬結(jié)果及比較使用MATLAB對經(jīng)典的中國旅行商問題進行模擬。雖然基本蟻群算法的運行時間比混合型蟻群算法的時間要短，但是混合型蟻群算法得到的結(jié)果要好的多。在文獻58中，得到的適應(yīng)度值很小，但是兩只螞蟻的路線卻相差很遠，所選擇的路線相差也很大，： 適應(yīng)度方法不準確的一個例子第2種對比每一個螞蟻的城市訪問順序能夠很好地說明蟻群算法的多樣性，但是當(dāng)城市的規(guī)模很大時，這個算法的復(fù)雜度會很高，會花很長時間的計算對比每一個螞蟻的訪問順序。 在每個迭代中，visitMatrix的元素最大值可以達到m（螞蟻的個數(shù)），當(dāng)值是m時，說明所有的螞蟻都選擇了這條路徑，那么這條路徑肯定是在最優(yōu)路徑中了。運行10次，結(jié)束后計算10次的平均邊數(shù)和。為了從理論上證明改進的混合型算法的有效性，通過統(tǒng)計每一次運行中螞蟻經(jīng)過的邊數(shù)和的方法來衡量蟻群算法的多樣性，與基本蟻群算法得到的邊數(shù)和進行對比，進一步證明了改進蟻群算法的有效性。因為如果交換的邊不屬于同一輛車所形成的路徑環(huán)，那么交換后的路線可能會不滿足車輛負載的限制。6. 從可選城市中去掉這個目標城市，使用偽隨機比例規(guī)則從剩余城市中再選擇一個城市然后再次判斷負載是否已經(jīng)超過了最大負載，如果沒有超過最大負載則可以轉(zhuǎn)步驟8（圖中c處）。13. 對步驟11（圖中e處）得到的最優(yōu)解和次優(yōu)解執(zhí)行全局信息素更新。N后面的數(shù)字表明了城市規(guī)模，K后面的數(shù)字表明了最大的車輛數(shù)目，車輛的最大負載都是100。通過本文實驗研究比較可以看出本文改進的算法在求解VRP問題時得到了很好的結(jié)果，對于很多VRP問題求解結(jié)果已經(jīng)非常接近最優(yōu)解或者達到最優(yōu)解，和最優(yōu)解相差的百分比基本都在6%以下。167。參考文獻[1] 楊淑瑩，—Matlab技術(shù)實現(xiàn)[M].北京：電子工業(yè)出版社，2012:13.[2] 段海濱．蟻群算法原理及其應(yīng)用[M]．北京：科學(xué)出版社．2005．[3] 吳春梅，現(xiàn)代智能優(yōu)化算法分的綜述[J].(8):3133.[4] Aickelin，. System Approaches to Intrusion DetectionA review[J].Lecture Notes in Computer Science,2004(3239): 316329．[5] CruzCortes，. Handling Constraints in Global Optimization Using an Artificial Immune System[J]. Lecture Notes in Computer Science,2005(3267):234247. [6] White Garrett. Improved Pattern Recognition with Artificial Clonal Science[J].Lecture Notes in Computer Science,2003(2787):181193.[7] Tang， ， Recognition System Using a Clonal Selectionbased Immune Network[J].Systems and Computers in Japan,2003,34(12):5663.[8] Sarafijanovic，Boudec .An Artificial Immune System Approach with Secondary Response for Misbehavior Detection in Mobile Adhoc Networks[J].IEEE Transactions on Neural Networks,2005,16(5):10761087.[9] Dantzig G B. Solution for Large Scale Travelling Salesman Problem [J]. Operations Research, 1954,2:393410.[10] 馬良，朱剛，[M].北京：科學(xué)出版社，2007，2029.[11] 勞眷. TSP問題中的蟻群優(yōu)化算法研究[D].長沙：湖南大學(xué)碩士論文，2007：34.[12] [D].西安：長安大學(xué)碩士論文，2009：23. [13] 駱劍平，李霞， 展望 本文只對蟻群優(yōu)化算法及其在TSP 和VRP 問題的應(yīng)用方面進行了部分研究，還有許多方面的研究需要進一步地展開：（1）應(yīng)用領(lǐng)域。蟻群算法是最新出現(xiàn)的一種啟發(fā)式優(yōu)化仿生類智能進化算法，它的原理主要是模擬昆蟲王國中螞蟻群體覓食的行為，由歐洲著名學(xué)者提出并逐步進行改進的新穎的算法。 經(jīng)過10次實驗兩種算法所求得的最優(yōu)、最差值比較 結(jié)果實例已知最優(yōu)解改進算法最小值A(chǔ)CS最小值改進算法最大值A(chǔ)CS最大值N32K5784N33K6742N36K5799N37K6949N38K5730N39K5822N39K6831N44K6937N63K91616N80K101763從表1的對比結(jié)果可以看出來，改進算法所求解的結(jié)果要遠遠優(yōu)于基本蟻群算法所求的結(jié)果，改進蟻群算法運行10次得到的最大值都要小于基本蟻群算法求得的最小值。轉(zhuǎn)步驟2（圖中a處）。8. 選擇目標城市為下個送貨的目標城市，并且把這個城市的狀態(tài)標記為已送貨。增加一次重新選擇的機會能夠增加找到可行解的次數(shù)，而只增加一次重新選擇機會而不是多次重新選擇的機會是因為增加多次重新選擇機會時得到的可行解的質(zhì)量太差，沒有實際意義。選取了VRP問題庫中的10個實例進行了實驗。綜合兩種算法在中國旅行商問題上的對比可以充分說明，改進的蟻群算法具有很好的種群多樣性。在基本蟻群算法和改進的算法中, 本文都加入了計算邊數(shù)的方法。文獻作者已經(jīng)證明了，在一個迭代中螞蟻所經(jīng)過的邊數(shù)越多，說明蟻群算法的多樣性越高。 結(jié)論通過中國旅行商問題，再次證明了改進蟻群算法的有效性，在求解TSP問題時能夠取得比當(dāng)前算法的最優(yōu)解更好的解。.我們得到的最優(yōu)遍歷結(jié)果的城市遍歷順序是：北京石家莊太原呼和浩特銀川蘭州西寧烏魯木齊拉薩成都昆明貴陽南寧海口廣州長沙南昌福州臺北杭州上海南京合肥武漢西安鄭州濟南天津沈陽長春哈爾濱。 3394 2643。 3918 2179。 4312 790。1. 拉薩 3.