畢業(yè)設(shè)計(jì)-基于蟻群算法的TSP問題研究

1、編號(hào)200502122005021237 南京航空航天大學(xué)金城學(xué)院畢 業(yè) 設(shè) 計(jì) 題 目基于蟻群算法的 TSP 問題研究學(xué)生姓名學(xué) 號(hào)系 部專 業(yè)班 級(jí)指導(dǎo)教師信息工程系信息工程二九年六月南京航空航天大學(xué)金城學(xué)院本科畢業(yè)設(shè)計(jì)（論文）誠信承諾書本人鄭重聲明：所呈交的畢業(yè)設(shè)計(jì)（論文）（題目：基于蟻群算法的TSP問題研究）是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的成果。盡本人所知，除了畢業(yè)設(shè)計(jì)（論文）中特別加以標(biāo)注引用的內(nèi)容外，本畢業(yè)設(shè)計(jì)（論文）不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。作者簽名：（學(xué)號(hào)）：20050212372009 年6 月 6 日畢業(yè)設(shè)計(jì)（論文）報(bào)告紙基于蟻群算法的 TS

2、P 問題研究摘 要本文研究了基于蟻群算法解決 TSP 問題的原理，算法流程以及用 MATLAB 程序的仿真。論文首先簡單回顧了蟻群算法的歷史、發(fā)展以及應(yīng)用，然后詳細(xì)介紹了基本蟻群算法的原理，包括基本蟻群算法的行為描述和機(jī)制原理。其次從基本蟻群算法的系統(tǒng)學(xué)特征出發(fā)，討論它具有分布式，自組織，正反饋等特征。接著引出了基本蟻群算法解決的 TSP 問題，先討論了組合優(yōu)化問題，然后從 TSP 問題的定義，實(shí)用價(jià)值，理論意義的角度對(duì) TSP 問題進(jìn)行闡述。并且重點(diǎn)運(yùn)用 MATLAB 的仿真方法，實(shí)現(xiàn)了基于蟻群算法的仿真，給出了求解 TSP 問題的數(shù)學(xué)模型，實(shí)現(xiàn)步驟，描述了蟻群算法的優(yōu)缺點(diǎn)。論文最后以 MA

3、TLAB 仿真實(shí)驗(yàn)為基礎(chǔ)，對(duì)蟻群算法的主要參數(shù)進(jìn)行了詳細(xì)的討論，并且給出了優(yōu)化的參數(shù)選擇，解決了算法中存在的不足。論文實(shí)現(xiàn)了基于蟻群算法對(duì) TSP 問題的求解和仿真。關(guān)鍵字：蟻群算法，組合優(yōu)化，信息素，TSP 問題i畢業(yè)設(shè)計(jì)（論文）報(bào)告紙TSP research based on ant colony algorithm AbstractThis paper researched the principle based on ant colony algorithm to solve TSP problem,the algorithm processes and procedures usin

4、g MATLAB simulation.Paper first briefly reviewed thehistory of ant colony algorithm ,development and application,and then described in detail the basicprinciple of ant colony algorithm,including the conduct of the basic ant colony algorithm and themechanism descried in principle.Second,the basic ant

5、 colony algorithm from the characteristics ofthe system starting to discuss it with the distributed,self-organdization,characteristics of positivefeedback. Then leads to the basic ant colony algorithm to solve the TSP problem, first discuss thecombinatorial optimization problems, and then from the d

6、efinition of TSP problem, practical value,the theoretical significance of the point of view on the issue of the TSP. Focus on the use ofMATLAB and the simulation method, ant colony algorithm based on the realization of thesimulation, are given for solving the mathematical model of the TSP problem, t

7、he realization ofthese steps, describing the advantages and disadvantages of the ant colony algorithm. Finallysimulation results in MATLAB based on the main parameters of ant colony algorithm are discussedin detail, and optimized parameters are given options to solve the shortcomings of existingalgo

8、rithms. Paper achieved on optimization and simulation based on Ant colony algorithm to solvethe problem. Key Words:ant colony algorithm;combinatorial optimization;pheromone;TSP ii目 錄畢業(yè)設(shè)計(jì)（論文）報(bào)告紙摘 要 .iAbstract. ii第一章 緒 論 . - 1 - 1.1 蟻群算法概況. - 1 -1.2 論文的主要內(nèi)容. - 2 -第二章 基本蟻群算法簡介 . - 3 - 2.1 基本蟻群算法的原理. -

9、3 -2.1.1 蟻群行為描述 . - 3 -2.1.2 基本蟻群算法的機(jī)制原理 . - 5 -2.2 基本蟻群算法的系統(tǒng)學(xué)特征. - 6 -2.2.1 分布式 . - 6 -2.2.2 自組織 . - 7 -2.2.3 正反饋 . - 7 -第三章 組合優(yōu)化以及TSP問題簡介. - 9 - 3.1 組合優(yōu)化簡介. - 9 -3.1.1 引言 . - 9 -3.1.2 組合優(yōu)化問題 . - 9 -3.1.3NP完全問題 . - 10 -3.2TSP問題簡介 . - 10 -3.2.1TSP問題的定義. - 10 -3.2.2TSP的實(shí)用價(jià)值. - 11 -3.2.3TSP問題的理論意義. -

10、11 -3.3 基本蟻群算法的數(shù)學(xué)模型. - 11 -第四章 基本蟻群算法求解TSP . - 14 - 4.1 參數(shù)設(shè)置平臺(tái) . - 14 -iii畢業(yè)設(shè)計(jì)（論文）報(bào)告紙4.2 基本蟻群算法求解TSP的實(shí)現(xiàn)流程 . - 15 -4.2.1 基本蟻群算法的實(shí)現(xiàn)步驟 . - 15 -4.2.2 基本蟻群算法的結(jié)構(gòu)流程 . - 15 -4.3 基本蟻群算法的仿真結(jié)果 . - 17 -第五章 蟻群算法的主要參數(shù)設(shè)置 . - 19 - 5.1 關(guān)鍵參數(shù)介紹. - 19 -5.2 不同參數(shù)設(shè)置的試驗(yàn). - 21 -5.2.1 信息素?fù)]發(fā)度的設(shè)置 . - 21 -5.2.2 蟻群數(shù)量的設(shè)置 . - 21 -

11、5.2.3 啟發(fā)式因子的設(shè)置 . - 22 -5.3 不同參數(shù)設(shè)置的實(shí)驗(yàn)結(jié)果和結(jié)論. - 22 -5.3.1 信息素?fù)]發(fā)度的選擇設(shè)置 . - 22 -5.3.2 蟻群數(shù)量的選擇設(shè)置 . - 24 -5.3.3 啟發(fā)式因子的選擇設(shè)置 . - 25 -第六章 總結(jié)和展望 . - 27 - 6.1 工作總結(jié). - 27 -6.2 技術(shù)展望. - 27 -參考文獻(xiàn) . - 28 - 致 謝 . - 29 - 附 錄 . - 30 - 附錄 1: 基于基本蟻群算法的TSP問題源碼 . - 30 -iv第一章 緒 論畢業(yè)設(shè)計(jì)（論文）報(bào)告紙螞蟻是地球上最常見、數(shù)量最多的昆蟲種類之一，常常成群結(jié)隊(duì)地出現(xiàn)在人類

12、的日常生活環(huán)境中。這些昆蟲的群體生物智能特征，引起了一些學(xué)者的注意。意大利學(xué)者 M.Dorigo，V.Maniezzo 等人在觀察螞蟻的覓食習(xí)性時(shí)發(fā)現(xiàn)，螞蟻總能找到巢穴與食物源之間的最短路徑。經(jīng)研究發(fā)現(xiàn)，螞蟻的這種群體協(xié)作功能是通過一種遺留在其來往路徑上的叫做信息素（Pheromone）的揮發(fā)性化學(xué)物質(zhì)來進(jìn)行通信和協(xié)調(diào)的?；瘜W(xué)通信是螞蟻采取的基本信息交流方式之一，在螞蟻的生活習(xí)性中起著重要的作用。通過對(duì)螞蟻覓食行為的研究，他們發(fā)現(xiàn)，整個(gè)蟻群就是通過這種信息素進(jìn)行相互協(xié)作，形成正反饋，從而使多個(gè)路徑上的螞蟻都逐漸聚集到最短的那條路徑上。1.1 蟻群算法概況M.Dorigo等人于 1991 年首先

13、提出了蟻群算法。其主要特點(diǎn)就是：通過正反饋、分布式協(xié)作來尋找最優(yōu)路徑。這是一種基于種群尋優(yōu)的啟發(fā)式搜索算法。它充分利用了生物蟻群能通過個(gè)體間簡單的信息傳遞，搜索從蟻巢至食物間最短路徑的集體尋優(yōu)特征1，以及該過程與旅行商問題求解之間的相似性。得到了具有NP難度的旅行商問題的最優(yōu)解答。同時(shí)，該算法還被用于求解Job-Shop調(diào)度問題、二次指派問題以及多維背包問題等，顯示了其適用于組合優(yōu)化類問題求解的優(yōu)越特征。蟻群算法之所以能引起相關(guān)領(lǐng)域研究者的注意，是因?yàn)檫@種求解模式能將問題求解的快速性、全局優(yōu)化特征以及在有限時(shí)間內(nèi)答案的合理性結(jié)合起來。其中，尋優(yōu)的快速性是通過正反饋式的信息傳遞和積累來保證的。而

14、算法的早熟性收斂又可以通過其分布式計(jì)算特征加以避免，同時(shí)，具有貪婪啟發(fā)式搜索特征的蟻群系統(tǒng)又能在搜索過程的早期找到可以接受的問題解答。這種優(yōu)越的問題分布式求解模式經(jīng)過相關(guān)領(lǐng)域研究者的關(guān)注和努力，已經(jīng)在最初的算法模型基礎(chǔ)上得到了很大的改進(jìn)和拓展。以蟻群算法為代表的群智能已成為當(dāng)今分布式人工智能研究的一個(gè)熱點(diǎn)，許多源于蜂群和蟻群模型設(shè)計(jì)的算法己越來越多地被應(yīng)用于企業(yè)的運(yùn)轉(zhuǎn)模式的研究2。美國五角大樓正在資助關(guān)于群智能系統(tǒng)的研究工作-群體戰(zhàn)略（Swarm Strategy），它的一個(gè)實(shí)戰(zhàn)用途是通過運(yùn)用成群的空中無人駕駛飛行器和地面車輛來轉(zhuǎn)移敵人的注意力，讓自己的軍隊(duì)在敵人后方不被- 1 -畢業(yè)設(shè)計(jì)（論

15、文）報(bào)告紙察覺地安全進(jìn)行。英國電信公司和美國世界通信公司以電子螞蟻為基礎(chǔ)，對(duì)新的電信網(wǎng)絡(luò)管理方法進(jìn)行了試驗(yàn)。國內(nèi)，國家自然科學(xué)基金”十五”期間學(xué)科交叉類優(yōu)先資助領(lǐng)域中的認(rèn)知科學(xué)及其信息處理的研究內(nèi)容中也明確列出了群智能領(lǐng)域的進(jìn)化、自適應(yīng)與現(xiàn)場(chǎng)認(rèn)知主題。多年來世界各地研究工作者對(duì)蟻群算法進(jìn)行了精心研究和應(yīng)用開發(fā)，該算法現(xiàn)已被大量應(yīng)用于數(shù)據(jù)分析、機(jī)器人協(xié)作問題求解、電力、通信、水利、采礦、化工、建筑、交通5等領(lǐng)域。蟻群算法最初用于解決TSP問題，經(jīng)過多年的發(fā)展，已經(jīng)陸續(xù)滲透到其他領(lǐng)域中，如圖著色問題、大規(guī)模集成電路設(shè)計(jì)、通訊網(wǎng)絡(luò)中的路由問題以及負(fù)載平衡問題、車輛調(diào)度問題等。蟻群算法在若干領(lǐng)域已經(jīng)獲

16、得成功的應(yīng)用，其中最成功的是在組合優(yōu)化問題中的應(yīng)用。1.2 論文的主要內(nèi)容因?yàn)橄伻核惴ㄓ泻芏喾N,并且 TSP 問題是蟻群算法眾多解決問題中的經(jīng)典問題,所以具有很大的隨意性。雖然蟻群算法的選擇性很多，但是所有的算法都是基于最基本的蟻群算法，并且基本蟻群算法也可以很好的解決 TSP 問題，以及說明參數(shù)選擇問題。所以本文以基本蟻群算法為基礎(chǔ)，通過 MATLAB 仿真這個(gè)平臺(tái)，重點(diǎn)討論了基本蟻群算法如何解決 TSP 問題。 第一章主要介紹了蟻群算法的歷史、發(fā)展、應(yīng)用，對(duì)蟻群算法原理的核心信息素作了簡單的描述。第二章對(duì)基本蟻群算法的原理進(jìn)行了介紹，包括基本蟻群算法的行為描述，機(jī)制原理。同時(shí)探討了基本蟻群

17、算法的系統(tǒng)學(xué)特征。第三章對(duì)組合優(yōu)化以及 TSP 問題的定義，實(shí)用價(jià)值，理論意義進(jìn)行了描述。并且介紹了基本蟻群算法求解 TSP 問題的數(shù)學(xué)模型。第四章首先介紹了利用基本蟻群算法的參數(shù)仿真平臺(tái)，及實(shí)現(xiàn)步驟和結(jié)構(gòu)流程。并給出了用 MATLAB 實(shí)現(xiàn)的仿真結(jié)果。第五章主要討論了蟻群算法中主要參數(shù)對(duì)于蟻群算法的全局搜索能力以及收斂性的影響，并做了相應(yīng)仿真實(shí)驗(yàn)加以驗(yàn)證。第六章對(duì)蟻群算法的發(fā)展進(jìn)行了展望，同時(shí)對(duì)本文進(jìn)行了總結(jié)。- 2 -畢業(yè)設(shè)計(jì)（論文）報(bào)告紙第二章 基本蟻群算法簡介2.1 基本蟻群算法的原理2.1.1 蟻群行為描述根據(jù)仿生學(xué)家的長期研究發(fā)現(xiàn)：螞蟻雖然沒有視覺，但運(yùn)動(dòng)時(shí)會(huì)通過在路徑上釋放出一種

18、特殊的分泌物信息素來尋找路徑。當(dāng)它們碰到一個(gè)還沒有走過的路口的時(shí)，就隨機(jī)的挑選一條路徑前行，同時(shí)釋放出與路徑長度有關(guān)的信息素。螞蟻?zhàn)叩穆窂皆介L，則釋放的信息量越小。當(dāng)后來的螞蟻再次碰到這個(gè)路口的時(shí)候，選擇信息量較大路徑的概率相對(duì)較大，這樣便形成了一個(gè)正反饋機(jī)制。最優(yōu)路徑上的信息量越來越大，而其他路徑上的信息量卻會(huì)隨著時(shí)間的流逝而逐漸消減，最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。同時(shí)蟻群還能夠適應(yīng)環(huán)境的變化，當(dāng)蟻群的運(yùn)動(dòng)路徑上突然出現(xiàn)障礙物時(shí)，螞蟻也能很快的重新找到最優(yōu)路徑。可見，在整個(gè)尋徑過程中，雖然單只螞蟻的選擇能力有限，但是通過信息素的作用使整個(gè)蟻群行為找出最優(yōu)路徑。這里用人工螞蟻覓食圖來描述蟻群搜索

19、原理。EAd=1Bd=1CDd=0.5Fd=0.5圖 2.1 人工螞蟻覓食模擬- 3 -AB1515EF1515畢業(yè)設(shè)計(jì)（論文）報(bào)告紙CD圖 2.2 人工螞蟻覓食模擬EAB1020F1020CD圖 2.3 人工螞蟻覓食模擬圖 2.1 中，設(shè) A 點(diǎn)是蟻巢，D 點(diǎn)是食物源，EF 之間區(qū)域是障礙物。由于障礙物的存在，- 4 -畢業(yè)設(shè)計(jì)（論文）報(bào)告紙螞蟻只能經(jīng)由 A 經(jīng) E 或 F 到達(dá) D，或由 D 到達(dá) A，各點(diǎn)之間的距離如圖 2.1 所示。假設(shè)每個(gè)時(shí)間單位有 30 只螞蟻由 A 到達(dá) D 點(diǎn)，有 30 只螞蟻由 D 到達(dá) A 點(diǎn)，螞蟻過后留下的信息量為 1。為了方便起見，設(shè)該物質(zhì)停留時(shí)間為 1

20、。在初始時(shí)刻，由于路徑 BF、FC、BE、EC 上均無信息存在，位于 A 和 D 的螞蟻可以隨機(jī)選擇路徑，從統(tǒng)計(jì)學(xué)的角度可以認(rèn)為螞蟻以相同的概率選擇 BE、FC、BE、EC，如圖 2.2 所示。經(jīng)過一個(gè)時(shí)間單位后，在路徑BFC 上的信息量是路徑 BEC 上的信息量的 2 倍。又經(jīng)過一段時(shí)間，將有 20 只螞蟻由 B、F 和 C 點(diǎn)到達(dá)D，如圖 2.3 所示。隨著時(shí)間的推移，螞蟻將會(huì)以越來越大的概率選擇路徑 BFC，最終將會(huì)完全選擇 BFC，從而找到由蟻巢到食物源的最短路徑。2.1.2 基本蟻群算法的機(jī)制原理模擬螞蟻群體覓食行為的蟻群算法是作為一種新的計(jì)算智能模式引入，該算法基于以下基本假設(shè)：1

21、.螞蟻之間通過信息素和環(huán)境進(jìn)行通信。每只螞蟻僅根據(jù)其周圍的局部環(huán)境作出反應(yīng)，也只對(duì)其周圍的局部環(huán)境產(chǎn)生影響。2.螞蟻對(duì)環(huán)境的反應(yīng)由其內(nèi)部模式?jīng)Q定。因?yàn)槲浵伿腔蛏?，螞蟻的行為?shí)際上是其基因的適應(yīng)性表現(xiàn)，即螞蟻是反應(yīng)型適應(yīng)性主體。3在個(gè)體水平上，每只螞蟻僅根據(jù)環(huán)境做出獨(dú)立選擇；在群體水平上，單只螞蟻的行為是隨機(jī)的，但蟻群可通過自組織過程形成高度有序的群體行為。由上述假設(shè)和分析可見，基本蟻群算法的尋優(yōu)機(jī)制包含兩個(gè)基本階段：適應(yīng)階段和協(xié)作階段。在適應(yīng)階段，各候選解根據(jù)積累的信息不斷調(diào)整自身結(jié)構(gòu)，路徑上經(jīng)過的螞蟻越多，信息量越大，則該路徑越容易被選擇；時(shí)間越長，信息量會(huì)越小；在協(xié)作階段，候選解之間通

22、過信息交流，以期望產(chǎn)生性能更好的解。蟻群算法實(shí)際上是一類智能多主體系統(tǒng)，其自組織機(jī)制使得蟻群算法不需要對(duì)所求的問題的每一方面都有詳盡的認(rèn)識(shí)。自組織本質(zhì)上體現(xiàn)了從無序到有序的動(dòng)態(tài)演化，其邏輯結(jié)構(gòu)如下圖所示。- 5 -螞 蟻 個(gè)體A信息 素 的增 量 構(gòu)建蟻群活動(dòng)規(guī)劃信息素更新管理信息素決策點(diǎn)問題表達(dá)組 合 優(yōu) 化 問題畢業(yè)設(shè)計(jì)（論文）報(bào)告紙螞 蟻 個(gè) 體B信息素的 增 量 構(gòu)建圖 2.4 基本蟻群算法的邏輯結(jié)構(gòu)由圖 2.4 可見，先將具體的組合優(yōu)化問題表述成規(guī)范的格式，然后利用蟻群算法在“探索”和“利用”之間根據(jù)信息素這一反饋載體確定決策點(diǎn)，同時(shí)按照相應(yīng)的信息素更新規(guī)則對(duì)每只螞蟻個(gè)體的信息素進(jìn)行

23、增量構(gòu)建，隨后從整體角度規(guī)劃出蟻群活動(dòng)的行為方向，周而復(fù)始，即可求出組合優(yōu)化的最優(yōu)解。2.2 基本蟻群算法的系統(tǒng)學(xué)特征基本蟻群算法在系統(tǒng)學(xué)上表現(xiàn)以下三個(gè)特征：分布式，自組織，正反饋。三者表現(xiàn)出一個(gè)整體，相輔相成。2.2.1 分布式自然界中的真實(shí)蟻群行為也出現(xiàn)了分布式。當(dāng)蟻群需要完成某項(xiàng)工作時(shí)，其中的許多螞蟻都為共同目的進(jìn)行著同樣的工作，而最終任務(wù)的完成不會(huì)由于某些個(gè)體的的缺陷而受到影響。蟻群算法作為對(duì)蟻群覓食行為的抽象，也體現(xiàn)了群體行為的分布式特征。每只人工螞蟻- 6 -畢業(yè)設(shè)計(jì)（論文）報(bào)告紙?jiān)趩栴}空間的多個(gè)點(diǎn)同時(shí)開始相互獨(dú)立地構(gòu)造問題解，而整個(gè)問題的求解不會(huì)因?yàn)槟持蝗斯の浵仧o法成功獲得解而受

24、到影響。具體到不同的優(yōu)化問題而言，蟻群算法體現(xiàn)出的分布式特征就具有了更加現(xiàn)實(shí)的意義。因?yàn)樗械姆律鷥?yōu)化算法均可看做按照一定規(guī)則的問題解空間搜索最優(yōu)解的過程，所以搜索點(diǎn)的初始選取就直接關(guān)系到算法求解結(jié)果的優(yōu)劣和算法尋優(yōu)效率。當(dāng)求解許多復(fù)雜問題時(shí)，從一點(diǎn)出發(fā)的搜索受到局部特征的限制，可得不到所求問題的滿意解；而基本蟻群算法則可看做是一個(gè)分布式的多智能系統(tǒng)，它在問題空間的多點(diǎn)同時(shí)獨(dú)立地進(jìn)行解搜索，不僅使得算法具有較強(qiáng)的全局搜索能力，也增加了算法的可靠性。2.2.2 自組織基本蟻群算法的另一個(gè)重要特征是自組織。自組織的概念是隨著系統(tǒng)科學(xué)的發(fā)展而建立起來的。通常把系統(tǒng)論中的組織行為分為自組織和他組織兩大

25、類4。其根本區(qū)別在于組織力或組織指令是來自于系統(tǒng)內(nèi)部還是來自于系統(tǒng)外部，前者稱為自組織，而后者即為他組織。如果系統(tǒng)在獲得時(shí)間的、空間的或者功能的結(jié)果過程中，沒有外界的特定干預(yù)，則稱為系統(tǒng)是自組織的。從抽象意義上講，自組織就是在沒有外界作用下使得系統(tǒng)從無序到有序的進(jìn)化過程?；鞠伻核惴w現(xiàn)了這一過程，以蟻群優(yōu)化為例，當(dāng)算法開始的初期，單只人工螞蟻無序地尋找解，經(jīng)過一段時(shí)間的算法演化，人工螞蟻越來越趨向于尋找到接近最優(yōu)解的一些解，這恰恰體現(xiàn)了從無序到有序的自組織進(jìn)化。自組織大大增強(qiáng)了算法的魯棒性5（在這里可以理解為算法抗干擾性,就是指不是針對(duì)具體問題算法也同樣可以求解,極大的體現(xiàn)了蟻群算法的抗干擾

26、能力），傳統(tǒng)的算法都是針對(duì)某一具體問題而設(shè)計(jì)的，這往往建立在對(duì)該問題有了全面清晰認(rèn)識(shí)的基礎(chǔ)上，通常很難適應(yīng)其他問題。而自組織的蟻群算法不需要對(duì)待求解問題的所有問題的所有方面都有所認(rèn)識(shí)，因而較容易應(yīng)用到一類問題中。2.2.3 正反饋反饋是控制論中的重要概念，它代表信息輸入對(duì)輸出的反作用。在系統(tǒng)學(xué)上認(rèn)為，反饋就是把系統(tǒng)現(xiàn)在的行為作為影響系統(tǒng)未來行為的原因。反饋分正反饋和負(fù)反饋兩種，前者指的是以現(xiàn)在的行為去加強(qiáng)未來的行為，而后者則是以現(xiàn)在的行為去削弱未來的行為。由自然界中真實(shí)螞蟻的覓食行為可見，螞蟻能夠最終找到最短路徑，直接依賴于最短路- 7 -畢業(yè)設(shè)計(jì)（論文）報(bào)告紙徑上信息素的堆積，而信息素的堆積

27、卻是一個(gè)正反饋的過程，對(duì)于基本蟻群算法而言，初始時(shí)在環(huán)境中存在完全相同的信息量，給系統(tǒng)一個(gè)微小的擾動(dòng)，使得各個(gè)邊上的信息量大小不同，螞蟻構(gòu)造的解就存在了優(yōu)劣。算法采用的反饋方式是在較優(yōu)解經(jīng)過的路徑留下更多的信息素，更多的信息素又吸引了更多的螞蟻，這個(gè)正反饋的過程使得初始值不斷地?cái)U(kuò)大，同時(shí)又引導(dǎo)整個(gè)系統(tǒng)向著最優(yōu)解的方向進(jìn)化。單一的正反饋或者負(fù)反饋存在于線形系統(tǒng)之中，是無法實(shí)現(xiàn)系統(tǒng)的自我組織的。自組織系統(tǒng)通過正反饋和負(fù)反饋機(jī)制，它體現(xiàn)于蟻群算法在構(gòu)造問題解的過程中用到了概率搜索技術(shù)，通過該技術(shù)增加了生成解的隨機(jī)性。隨機(jī)性的影響就在于接受了解在一定程度上的退化，另一方面又使得搜索范圍得以在一段時(shí)間內(nèi)

28、保持足夠大。這樣正反饋縮小搜索范圍，保證算法朝著最優(yōu)解的方向進(jìn)行；而負(fù)反饋保持搜索范圍，避免算法過早收斂于不好的結(jié)果。恰恰是在正反饋和負(fù)反饋共同作用影響下，基本蟻群算法得以自組織地進(jìn)化，從而得到問題在一定程度上的滿意解。- 8 -3.1 組合優(yōu)化簡介3.1.1 引言畢業(yè)設(shè)計(jì)（論文）報(bào)告紙第三章 組合優(yōu)化以及 TSP 問題簡介伴隨計(jì)算機(jī)技術(shù)的飛速發(fā)展，計(jì)算機(jī)正日益成為人們解決問題的不可或缺的重要工具。但在實(shí)踐中人們發(fā)現(xiàn)，存在這樣一類問題，運(yùn)用精確的算法在多項(xiàng)式時(shí)間內(nèi)無法找到問題的最優(yōu)解，這類問題稱為組合優(yōu)化問題。這類問題通常隨著問題規(guī)模的擴(kuò)大，問題空間呈現(xiàn)組合爆炸特征，求解問題的空間、時(shí)間復(fù)雜度

29、將呈指數(shù)級(jí)增長，使用常規(guī)的方法求解，在現(xiàn)有條件下是無法實(shí)現(xiàn)的，屬于NP完全問題6。TSP問題就是其中最經(jīng)典問題之一。因此利用仿生進(jìn)化算法，在較短的時(shí)間內(nèi)，求得問題的滿意解，就成為研究的重點(diǎn)。3.1.2 組合優(yōu)化問題組合優(yōu)化問題的目標(biāo)是從組合問題的可行解中求出最優(yōu)解。在現(xiàn)實(shí)世界里存在大量組合優(yōu)化問題，其中許多問題如旅行商問題、圖著色問題、分配問題、調(diào)度問題、布線問題及路由選擇問題等7，至今沒有找到有效地多項(xiàng)式算法，這些問題己被證明是NP完全問題。優(yōu)化問題有三個(gè)基本要素:變量、約束和目標(biāo)函數(shù)。在求解過程中選定的基本參數(shù)稱為變量，對(duì)變量取值的限制稱為約束，表示可行方案衡量標(biāo)準(zhǔn)的函數(shù)稱為目標(biāo)函數(shù)。組合

30、優(yōu)化問題就是在給定的約束條件下，求目標(biāo)函數(shù)最優(yōu)值的問題。組合優(yōu)化問題的一個(gè)實(shí)例可以表示為一個(gè)對(duì)偶（S，f），其中解空間 S 為可行解目標(biāo)函數(shù) f 是一個(gè)映射，定義為:f : S R求目標(biāo)函數(shù)最小值問題稱為最小化問題，記為：min f (i),i S求目標(biāo)函數(shù)最大值問題稱為最大值問題，記為：max f (i),i S顯然，只要改變目標(biāo)函數(shù)的符號(hào)，最小化問題與最大化問題就可以等價(jià)轉(zhuǎn)換。使目標(biāo)函數(shù)最優(yōu)值的解稱為最優(yōu)解（整體最優(yōu)解）。設(shè)（S，f）是組合優(yōu)化問題的一個(gè)實(shí)例， iapt S ，- 9 -畢業(yè)設(shè)計(jì)（論文）報(bào)告紙若： f (iapt) f (i)（對(duì)所有的 i S 成立）,稱 i為最小化問題

31、min f (i),i S 的最優(yōu)解。apt優(yōu)化問題在工程中有著廣泛的應(yīng)用，其涉及的問題是在一組限制條件下求解問題的最好(或最優(yōu))解的問題。按照人類認(rèn)知問題的特點(diǎn)，最優(yōu)化問題很自然的被劃分為兩類:一類是連續(xù)變量的問題，另一類是離散變量的問題。對(duì)于離散變量問題來說，一般是尋找離散事件的最優(yōu)編排，分組，次序或篩選等。不難看出這些問題的解的個(gè)數(shù)是有限的。通常把這類問題稱為組合最優(yōu)化問題，而研究用數(shù)學(xué)方法來求解這些問題就被稱為組合最優(yōu)化。3.1.3NP 完全問題按照計(jì)算復(fù)雜性理論研究問題求解的難易性，可把問題分為P類、NP類和NP完全類8。定義一:對(duì)于判定問題 D，存在一個(gè)多項(xiàng)式 P（t），使得對(duì)其每

32、一輸入規(guī)模為 n 的實(shí)例，可以在P(n)時(shí)間內(nèi)求得最優(yōu)解，此類問題稱為P(Polynomial)問題。其它的則是NP(Non一Polynomial)問題。假如一個(gè)問題是 P 問題，我們通常認(rèn)為它是“簡單的”，而 NP 問題，通常認(rèn)為它是“復(fù)雜的”。NP 問題是指可在多項(xiàng)式時(shí)間里檢驗(yàn)的問題，至今尚未找到多項(xiàng)式時(shí)間算法。定義二：若問題 L NP ，所有 NP 問題都可以經(jīng)過多項(xiàng)式計(jì)算時(shí)間轉(zhuǎn)化為 L，則 L 稱為NP 完全問題。如果 NP 完全類問題中有一個(gè)問題能用多項(xiàng)式確定性算法解決，則其他所有的 NP 完全類問題都能用多項(xiàng)式確定性算法來解決，很多問題被證明為 NP 完全問題，如 TSP 問題，N

33、P 完全問題也是檢驗(yàn)仿生算法有效性和可靠性的有效平臺(tái)。3.2TSP 問題簡介3.2.1TSP 問題的定義TSP問題的英文名（traveling salesman problem）,中文譯為旅行商問題9。問題的定義很簡單，即為一個(gè)旅行商要走訪N個(gè)城市，每個(gè)城市必須經(jīng)過一次且只能經(jīng)過一次，最后回到出發(fā)的城市就算是完成了一次旅行，問如何能找到一條最短的路徑。其相應(yīng)的數(shù)學(xué)描述如下：設(shè)有一個(gè)城市集合C= c1， c2， c3, ,. cn,其每對(duì)城市 ci， cj C 間的距離為d( , )ici Z+。求一條經(jīng)過C中每個(gè)城市正好一次的路徑（ c (1) ，n1d(c (i),c (i+1)+ d (c

34、 ( n),c (1)最小。i=1c (2)，c (3)， c (4) ，., c (n) ）,使得- 10 -3.2.2 TSP 的實(shí)用價(jià)值畢業(yè)設(shè)計(jì)（論文）報(bào)告紙TSP問題廣泛的存在于許多領(lǐng)域，而且問題規(guī)模（城市的數(shù)目）都很大。比如說，電路板鉆孔問題，X射線結(jié)晶學(xué)問題，VLSL（超大規(guī)模集成電路）制造問題等等10?？傊彩强梢猿橄蟪蔀楸闅v全部城市一次且僅一次，求代價(jià)最小的路徑的問題，都可以當(dāng)作TSP問題來解決。3.2.3TSP 問題的理論意義同實(shí)用價(jià)值相比，TSP問題的理論意義更加重大。事實(shí)上，該問題是作為所有組合優(yōu)化問題的范例而存在的11。它己經(jīng)成為并將繼續(xù)成為測(cè)試新算法的標(biāo)準(zhǔn)問題。這是

35、因?yàn)?，TSP問題展示了組合優(yōu)化的所有方面。它從概念上來講非常簡單，但是其求解的難度是很大的。如果針對(duì)TSP問題提出的某種算法能夠取得比較好的實(shí)算效果，那么對(duì)其進(jìn)行修改，就可以應(yīng)用于其它類型的組合優(yōu)化問題并取得良好的效果?；谏鲜鲈?，該問題吸引了許多不同領(lǐng)域的研究者。3.3 基本蟻群算法的數(shù)學(xué)模型設(shè)ij(t) 為 t 時(shí)刻路徑（i,j）上的信息量，n 表示 TSP 規(guī)模，m 為蟻群中螞蟻的總數(shù)目。在初始時(shí)刻各條路徑上的信息量相等，并設(shè)ij(0) = const 。螞蟻k（k=1,2,m）在運(yùn)動(dòng)過程中，根據(jù)各條路徑上的信息量決定其轉(zhuǎn)移方向，這里用禁忌表12 tabuk(k=1,2,m)來記錄螞蟻

36、k當(dāng)前所走過的城市，集合隨著 tabuk進(jìn)化過程作動(dòng)態(tài)調(diào)整。在搜索過程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來計(jì)算狀態(tài)轉(zhuǎn)移概率。 pijk(t) 表示在t螞蟻k由城市i轉(zhuǎn)移到城市j的狀態(tài)轉(zhuǎn)移概率t ( )t ( )ijiktkp t= ( )t ( )ij( ) s allowedk0（3-1）式中，allowedk表示螞蟻k下一步允許選擇的城市； 為信息啟發(fā)式因子，表示軌跡的相對(duì)重要性，反映了螞蟻在運(yùn)動(dòng)過程中所積累的信息在螞蟻運(yùn)動(dòng)時(shí)的所起的作用，其值越大，則該螞蟻越傾向于選擇其他螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強(qiáng)； 為期望啟發(fā)式因子，表- 11 -畢業(yè)設(shè)計(jì)（論文）報(bào)告紙示能見度的相

37、對(duì)重要性，反映了螞蟻在運(yùn)動(dòng)過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則13；ij(t ) 為啟發(fā)函數(shù)，其表達(dá)式如下( ) = 1/ijtdij（3-2）式中， dij表示相鄰兩個(gè)城市之間的距離。對(duì)螞蟻 k 而言， dij越小，則ij(t) 越大， pijk(t) 也就越大。顯然，該啟發(fā)函數(shù)表示螞蟻從城市 i 轉(zhuǎn)移到城市 j 的期望程度。為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪?duì)所有 n 個(gè)城市遍歷（也即一個(gè)循環(huán)結(jié)束）后，要對(duì)殘留信息進(jìn)行更新處理。這種更新策略模仿了人類大腦記憶的特點(diǎn)，在新信息不斷存入大腦的同時(shí)，存儲(chǔ)在大

38、腦中的舊信息隨著時(shí)間的推移逐漸淡化，甚至忘記。由此，t+n 時(shí)刻在路徑（i,j）上的信息量可按如下規(guī)則進(jìn)行調(diào)整ij(t+n) = (1)mijt( )+ ijt( )（3-3）ij(t) =k=1kij(t)（3-4）式中， 表示信息素?fù)]發(fā)系數(shù)，則 1- 表示信息素殘留因子，為了防止信息的無限積累， 的取值范圍為： 0,1) ；ij(t ) 表示本次循環(huán)中路徑（ i,j）上的信息素增量，初始時(shí)刻ij(0) = 0 ，ijk(t) 表示第 k 只螞蟻在本次循環(huán)中留在路徑（i,j）上的信息量。根據(jù)信息素更新策略的不同，Dorigo M 提出了三種不同的基本蟻群算法模型，分別稱之為 Ant-Cycl

39、e 模型、Ant-Quantity 模型及 Ant-Density 模型，其差別在于在 Ant-Cycle 模型中 Qijk(t) 求法的不同。,k(i, ) k( )= L若第 只螞蟻在本次循環(huán)中經(jīng)過（3-5） ijk0,否則式中，Q 表示信息素強(qiáng)度，它在一定程度上影響算法的收斂程度； Lk表示第 k 只螞蟻在本次循環(huán)中所走過路徑的總長度。在 Ant-Quantity 模型中- 12 - Q+畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 k( )= d,若第 只螞蟻在 和kt t1之間經(jīng)過（i j, )（3-6） ij在 Ant-Density 模型中ij0，否則Q,t + 1jijkt( )=若第k只螞蟻在t和

40、之間經(jīng)過（i,)（3-7） 0,否則公式（3-6）和（3-7）中利用的是局部信息，即螞蟻完成一步后更新路徑上的信息素；而公式（3-5）中利用的是整體信息，即螞蟻完成一次循環(huán)后更新所有路徑上的信息素，在求解 TSP 時(shí)性能較好，因此通常采用公式(3-5)作為蟻群算法的基本模型。- 13 -畢業(yè)設(shè)計(jì)（論文）報(bào)告紙第四章 基本蟻群算法求解 TSP本章首先利用了 MATLAB 平臺(tái)做出一個(gè)參數(shù)設(shè)置平臺(tái)，是為后一章做參數(shù)討論做鋪墊，主要是運(yùn)用 MATLAB 中 GUIDE 設(shè)計(jì)工具。接著給出了基本蟻群算法求解 TSP 的實(shí)現(xiàn)流程，并且做了相應(yīng)的仿真，得出了仿真結(jié)果。并在第五章中進(jìn)行了蟻群算法主要參數(shù)設(shè)置的分析。4.1 參數(shù)設(shè)置平臺(tái)為了后一章利用仿真數(shù)據(jù)討論參數(shù)選擇更加方便，首先在這里設(shè)計(jì)了一個(gè)簡易的參數(shù)設(shè)置平臺(tái)。