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

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

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

3、TLAB 仿真實驗為基礎(chǔ)，對蟻群算法的主要參數(shù)進行了詳細的討論，并且給出了優(yōu)化的參數(shù)選擇，解決了算法中存在的不足。論文實現(xiàn)了基于蟻群算法對 TSP 問題的求解和仿真。關(guān)鍵字：蟻群算法，組合優(yōu)化，信息素，TSP 問題i畢業(yè)設(shè)計（論文）報告紙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è)計（論文）報告紙摘 要 .iAbstract. ii第一章 緒 論 . - 1 - 1.1 蟻群算法概況. - 1 -1.2 論文的主要內(nèi)容. - 2 -第二章 基本蟻群算法簡介 . - 3 - 2.1 基本蟻群算法的原理. -

9、3 -2.1.1 蟻群行為描述 . - 3 -2.1.2 基本蟻群算法的機制原理 . - 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的實用價值. - 11 -3.2.3TSP問題的理論意義. -

10、11 -3.3 基本蟻群算法的數(shù)學(xué)模型. - 11 -第四章 基本蟻群算法求解TSP . - 14 - 4.1 參數(shù)設(shè)置平臺 . - 14 -iii畢業(yè)設(shè)計（論文）報告紙4.2 基本蟻群算法求解TSP的實現(xiàn)流程 . - 15 -4.2.1 基本蟻群算法的實現(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è)置的試驗. - 21 -5.2.1 信息素揮發(fā)度的設(shè)置 . - 21 -5.2.2 蟻群數(shù)量的設(shè)置 . - 21 -

11、5.2.3 啟發(fā)式因子的設(shè)置 . - 22 -5.3 不同參數(shù)設(shè)置的實驗結(jié)果和結(jié)論. - 22 -5.3.1 信息素揮發(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 -參考文獻 . - 28 - 致 謝 . - 29 - 附 錄 . - 30 - 附錄 1: 基于基本蟻群算法的TSP問題源碼 . - 30 -iv第一章 緒 論畢業(yè)設(shè)計（論文）報告紙螞蟻是地球上最常見、數(shù)量最多的昆蟲種類之一，常常成群結(jié)隊地出現(xiàn)在人類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33、P 完全問題也是檢驗仿生算法有效性和可靠性的有效平臺。3.2TSP 問題簡介3.2.1TSP 問題的定義TSP問題的英文名（traveling salesman problem）,中文譯為旅行商問題9。問題的定義很簡單，即為一個旅行商要走訪N個城市，每個城市必須經(jīng)過一次且只能經(jīng)過一次，最后回到出發(fā)的城市就算是完成了一次旅行，問如何能找到一條最短的路徑。其相應(yīng)的數(shù)學(xué)描述如下：設(shè)有一個城市集合C= c1， c2， c3, ,. cn,其每對城市 ci， cj C 間的距離為d( , )ici Z+。求一條經(jīng)過C中每個城市正好一次的路徑（ 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 的實用價值畢業(yè)設(shè)計（論文）報告紙TSP問題廣泛的存在于許多領(lǐng)域，而且問題規(guī)模（城市的數(shù)目）都很大。比如說，電路板鉆孔問題，X射線結(jié)晶學(xué)問題，VLSL（超大規(guī)模集成電路）制造問題等等10。總之，凡是可以抽象成為遍歷全部城市一次且僅一次，求代價最小的路徑的問題，都可以當(dāng)作TSP問題來解決。3.2.3TSP 問題的理論意義同實用價值相比，TSP問題的理論意義更加重大。事實上，該問題是作為所有組合優(yōu)化問題的范例而存在的11。它己經(jīng)成為并將繼續(xù)成為測試新算法的標(biāo)準問題。這是

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

36、k當(dāng)前所走過的城市，集合隨著 tabuk進化過程作動態(tài)調(diào)整。在搜索過程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來計算狀態(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ā)式因子，表示軌跡的相對重要性，反映了螞蟻在運動過程中所積累的信息在螞蟻運動時的所起的作用，其值越大，則該螞蟻越傾向于選擇其他螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強； 為期望啟發(fā)式因子，表- 11 -畢業(yè)設(shè)計（論文）報告紙示能見度的相

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

38、腦中的舊信息隨著時間的推移逐漸淡化，甚至忘記。由此，t+n 時刻在路徑（i,j）上的信息量可按如下規(guī)則進行調(diào)整ij(t+n) = (1)mijt( )+ ijt( )（3-3）ij(t) =k=1kij(t)（3-4）式中， 表示信息素揮發(fā)系數(shù)，則 1- 表示信息素殘留因子，為了防止信息的無限積累， 的取值范圍為： 0,1) ；ij(t ) 表示本次循環(huán)中路徑（ i,j）上的信息素增量，初始時刻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 表示信息素強度，它在一定程度上影響算法的收斂程度； Lk表示第 k 只螞蟻在本次循環(huán)中所走過路徑的總長度。在 Ant-Quantity 模型中- 12 - Q+畢業(yè)設(shè)計（論文）報告紙 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 時性能較好，因此通常采用公式(3-5)作為蟻群算法的基本模型。- 13 -畢業(yè)設(shè)計（論文）報告紙第四章 基本蟻群算法求解 TSP本章首先利用了 MATLAB 平臺做出一個參數(shù)設(shè)置平臺，是為后一章做參數(shù)討論做鋪墊，主要是運用 MATLAB 中 GUIDE 設(shè)計工具。接著給出了基本蟻群算法求解 TSP 的實現(xiàn)流程，并且做了相應(yīng)的仿真，得出了仿真結(jié)果。并在第五章中進行了蟻群算法主要參數(shù)設(shè)置的分析。4.1 參數(shù)設(shè)置平臺為了后一章利用仿真數(shù)據(jù)討論參數(shù)選擇更加方便，首先在這里設(shè)計了一個簡易的參數(shù)設(shè)置平臺。