【正文】 單位代碼：10110 學(xué) 號(hào)：s20110075中 北 大 學(xué)碩 士 學(xué) 位 論 文 改進(jìn)的混合型蟻群算法及其應(yīng)用 xxx華北改進(jìn)的混合型蟻群算法及其應(yīng)用 碩士研究生 孫晶 指導(dǎo)教師 xxx 教授 學(xué)科專業(yè) 應(yīng)用數(shù)學(xué) 年 月 日?qǐng)D書分類號(hào) O157 密級(jí) 非密 UDC 510 碩 士 學(xué) 位 論 文改進(jìn)的混合型蟻群算法及其應(yīng)用 孫 晶 指導(dǎo)教師（姓名、職稱） xxx 教授 申請(qǐng)學(xué)位級(jí)別 理學(xué)碩士 專業(yè)名稱 應(yīng)用數(shù)學(xué) 論文提交日期 年 月 日 論文答辯日期 年 月 日 學(xué)位授予日期 年 月 日 論文評(píng)閱人 答辯委員會(huì)主席 年 月 日xxx學(xué)位論文摘 要 旅行商問(wèn)題（TSP）與車輛路徑問(wèn)題（VRP）自提出以來(lái)，許多學(xué)者進(jìn)行了大量的理論研究和實(shí)驗(yàn)分析，取得了非常顯著的進(jìn)展，已經(jīng)成為了運(yùn)籌學(xué)和組合優(yōu)化問(wèn)題領(lǐng)域的熱點(diǎn)研究問(wèn)題。求解他們的算法主要有精確型算法、近似算法和啟發(fā)式算法。自創(chuàng)立以來(lái)，無(wú)論理論研究還是在應(yīng)用方面都取得了突破性的進(jìn)展，不但在求解以上兩種問(wèn)題上得到了最優(yōu)解，而且在工件的排序問(wèn)題、圖著色問(wèn)題、多目標(biāo)函數(shù)等許多領(lǐng)域也取得了相當(dāng)不錯(cuò)的效果，具有相當(dāng)廣闊的發(fā)展前景。通過(guò)仿真實(shí)驗(yàn)可以看出本文改進(jìn)的算法在求解TSP問(wèn)題時(shí)具有很好的效果，在求解很多問(wèn)題時(shí)已經(jīng)非常接近最優(yōu)解或者優(yōu)于最優(yōu)解，和最優(yōu)解相差的百分比基本都在1%以下，并和兩種最新改進(jìn)的蟻群算法以及兩種自組織算法進(jìn)行比較，比較結(jié)果充分證明了該改進(jìn)算法的有效性。 最后又把改進(jìn)的混合型蟻群算法應(yīng)用到VRP問(wèn)題，使用MATLAB仿真工具對(duì)N44K6等10個(gè)經(jīng)典VRP問(wèn)題進(jìn)行了求解，得到的結(jié)果和已知最優(yōu)解的誤差很小，都在6%以下，并且N33K6問(wèn)題得到了和已知最優(yōu)解相同的解。關(guān)鍵詞：混合型蟻群算法，TSP問(wèn)題，種群多樣性，VRP問(wèn)題 AbstractMany scholars have been a lot of theoretical research and experimental analysis since Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) are proposed and notable progress is made. TSP and VRP have bee the central issue in operational research and binatorial optimization. Precise algorithm, approximate algorithm and heuristic algorithm are used to solve the problems. Among all the algorithms, ant colony algorithm has better performance. This bionic intelligence algorithm is quite different from the traditional ones, it’s more robust, positive feedback, concurrency and easy to bine with other algorithms. Since ant colony algorithm is proposed, breakthrough progress has been made both in theoretical research and realistic application. Not only optimal results are achieved but also proven to be effective in scheduling jobs, graph coloring, multiobjective function and other scopes. It has a very broad prospect.In this paper, a mixed ant colony algorithm is introduced firstly. The algorithm is based on the traditional ant colony system algorithm, construct an initial result using the nearest neighbor method and then improve the results using 2opt partial search strategy, and update the global pheromone for the best two colonies with a maximum and minimum constraint. The simulation using MATLAB for the classic kroa200 and other twelve TSP problems showed us very good results. All the results have deviations less than 1 percent pared to the bestknown results and some problems even achieved better results. In this paper, I also pared the results to two updated ant colony algorithms and two selforganization algorithms, the better results indicated us our mixed ant colony algorithm is a better one. Afterwards we used a method of counting the sum of the route edges to measure the population diversity of our algorithm. Then we pared the population diversity of our improved mixed algorithm and the base ACO algorithm. The result shows our algorithm has higher population diversity which gives us a theory support why our algorithm can achieve best result than ever known.Then we applied the algorithm to VRP. We simulated the classic N34K6 and other nine VRP problems using the MATLAB tool, the results of which have small deviations pared to the bestknown results. All the deviations are all smaller than 6 percent. And we got the result same as the bestknown result for N33K6. In this paper, I also pared the results to the results of the base ant colony optimization algorithm。 引言 1167。 VRP問(wèn)題 3 VRP問(wèn)題的提出 3 VRP問(wèn)題的研究現(xiàn)狀 5167。 本文的結(jié)構(gòu)安排 7第二章 蟻群算法 8167。 蟻群算法的基本思想 9 蟻群系統(tǒng)解決TSP的基本步驟 10 蟻群算法參數(shù)的控制選擇 11167。 MAX—MIN螞蟻系統(tǒng) 13167。 改進(jìn)策略 15 局部搜索法 15 2opt算法 15 改進(jìn)的混合型蟻群算法 16167。 改進(jìn)的蟻群算法求解中國(guó)旅行商問(wèn)題 23 中國(guó)旅行商問(wèn)題描述 23 模擬結(jié)果及比較 24 結(jié)論 27167。 小結(jié) 29第四章 改進(jìn)的混合型蟻群算法在VRP中的應(yīng)用 30167。 33167。 37167。 引言隨著現(xiàn)在信息技術(shù)和網(wǎng)絡(luò)技術(shù)突飛猛進(jìn)的發(fā)展人們不斷探索新知的欲望越來(lái)越強(qiáng)烈，而大自然是進(jìn)行人類探索發(fā)現(xiàn)的鑰匙。其中，人工蟻群算法[2]就是受到大自然真實(shí)螞蟻的啟發(fā)，通過(guò)觀察螞蟻在從巢穴到食物源覓食行為過(guò)程而發(fā)展起來(lái)的。蟻群算法正是模擬了這樣的優(yōu)化機(jī)制，即通過(guò)個(gè)體之間的信息交流與相互協(xié)作最終找到最優(yōu)解[3]。在求解著名復(fù)雜的優(yōu)化問(wèn)題——旅行商問(wèn)題（Traveling Salesman Problem）上取得成效以后，其應(yīng)用已經(jīng)逐漸滲透到各個(gè)領(lǐng)域，比如車輛路徑問(wèn)題(Vehicle Routing Problem)[4,5]、工件的排序問(wèn)題[6]、圖著色問(wèn)題[7,8]等。無(wú)論從理論研究還是應(yīng)用價(jià)值方面來(lái)看，它都是一種很有途的優(yōu)化算法。167。歐拉是在研究的騎士周游問(wèn)題時(shí)進(jìn)行描述的，國(guó)際象棋棋盤有64個(gè)方格，每一個(gè)方格只允許走一次，且所有方格都走一次后返回到起始的方格。下面我們用數(shù)學(xué)的語(yǔ)言進(jìn)行描述[10]：記G=(V,E)為賦權(quán)圖，V=(1,2…..,n)為頂點(diǎn)集，E為邊集，各頂點(diǎn)間的距離dij已知(dij 0，dii=∞，i，j∈V)。第一個(gè)約束條件和第二個(gè)約束條件表示對(duì)每個(gè)點(diǎn)來(lái)說(shuō)，僅有一條邊進(jìn)和一條邊出；第三個(gè)約束條件是為了確保沒(méi)有任何子回路解的產(chǎn)生。當(dāng)dij=dji（i,j∈V）時(shí)，被稱作是對(duì)稱TSP問(wèn)題。 TSP問(wèn)題研究現(xiàn)狀由于TSP問(wèn)題是NP完全難問(wèn)題，要想找到一個(gè)非常有效的的求解方法還是眾多學(xué)者需要探索的問(wèn)題。后來(lái)研究者提出使用近似算法或啟發(fā)式算法進(jìn)行研究，并且融合多種方法成為研究主流。(2)使用最近鄰、插入式、最小樹、ropt等啟發(fā)式算法和迭代算法。鑒于蟻群算法等智能優(yōu)化算法經(jīng)常停止于局部最優(yōu)解而得不到最優(yōu)解，因此研究者將蟻群算法和局部搜索算法結(jié)合起來(lái)得到混合型算法，混合型算法是一種有效求解TSP問(wèn)題的方法和方向。又由于很多領(lǐng)域的NP難題問(wèn)題都可以歸結(jié)為TSP問(wèn)題，所以它也具有一定的實(shí)際應(yīng)用價(jià)值，比如在車輛路徑規(guī)劃問(wèn)題、郵路問(wèn)題、裝配線路的螺母問(wèn)題等等都得到了研究者的廣泛關(guān)注。167。自該問(wèn)題的提出以來(lái)，不僅引起了應(yīng)用數(shù)學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)等各領(lǐng)域的學(xué)者關(guān)注，也得到了許多管理者和運(yùn)輸策劃制定者的極大重視。 VRP問(wèn)題的概述VRP問(wèn)題可以描述為：在滿足一定限制條件（如長(zhǎng)度、時(shí)間和容量等）下，根據(jù)客戶的不同需求，由配送中心設(shè)計(jì)從一個(gè)或多個(gè)起始點(diǎn)出發(fā)，計(jì)劃適當(dāng)?shù)男熊嚶肪€，使運(yùn)送車輛有序的通過(guò)，到達(dá)多個(gè)不同的城市或客戶的最優(yōu)路徑分配，以達(dá)到諸如路徑最短、成本最低、耗時(shí)最小等目的。雖然每一個(gè)城市都有一定的需求量，但是任何車輛所承載的總重量都不能超過(guò)該車輛的能力負(fù)荷。2) 總長(zhǎng)限制。我們把這種帶有路長(zhǎng)或時(shí)間限制的VRP稱為DVRP。4) 兩城市間的優(yōu)先關(guān)系：城市i必須在城市j之前被訪問(wèn)。本文研究的對(duì)象就是CVRP問(wèn)題，對(duì)于這種經(jīng)典的VRP問(wèn)題，在本文中將簡(jiǎn)稱為VRP[14]。假設(shè)每一個(gè)客戶只能被訪問(wèn)一次，每輛車所訪問(wèn)的城市的需求總和不能超過(guò)車輛的負(fù)載能力，并且所使用的車輛數(shù)量是固定的。設(shè)： 則VRP問(wèn)題的數(shù)學(xué)模型可以描述為[15,16]: 其中約束（a）為車輛負(fù)載限制，約束（b）保證每輛車對(duì)每個(gè)客戶只訪問(wèn)一次，約束c e保證形成回路。 VRP問(wèn)題的研究現(xiàn)狀國(guó)外是從上世紀(jì)60年代就開始研究VRP問(wèn)題的，我國(guó)國(guó)內(nèi)對(duì)VRP問(wèn)題的研究起步比較晚，1994年才有第一篇關(guān)于VRP問(wèn)題的研究論文在正式期刊上發(fā)表[17]。從論文的研究?jī)?nèi)容來(lái)看，大部分論文都是討論如何能夠有效的求解VRP問(wèn)題。它包括分枝定界法、割平面法、網(wǎng)絡(luò)流算法、動(dòng)態(tài)規(guī)劃算法等。近似算法主要是通過(guò)搜索解空間中部分有限的子空間，以達(dá)到在有限的時(shí)間內(nèi)找到質(zhì)量較好的解，因此，在實(shí)際應(yīng)用要更加