機器學(xué)習(xí)課程論文

1、機器學(xué)習(xí)（論文）機 器 學(xué) 習(xí)（課程論文）李亞龍 E201102016基于蟻群算法的 TSP 問題研究摘 要本文研究了基于蟻群算法解決TSP問題的原理，算法流程以及用Microsoft Visual Studio 2008程序的仿真。論文首先簡單回顧了蟻群算法的歷史、發(fā)展以及應(yīng)用，然后詳細介紹了基本蟻群算法的原理，包括基本蟻群算法的行為描述和機制原理。其次從基本蟻群算法的系統(tǒng)學(xué)特征出發(fā)，討論它具有分布式，自組織，正反饋等特征。接著引出了基本蟻群算法解決的TSP問題，先討論了組合優(yōu)化問題，然后從TSP問題的定義，實用價值，理論意義的角度對TSP問題進行闡述。并且重點運用Microsoft Vis

2、ual Studio 2008的仿真方法，實現(xiàn)了基于蟻群算法的仿真，給出了求解TSP問題的數(shù)學(xué)模型，實現(xiàn)步驟，描述了蟻群算法的優(yōu)缺點。論文最后以Microsoft Visual Studio 2008仿真實驗為基礎(chǔ)，對蟻群算法的主要參數(shù)進行了詳細的討論，并且給出了優(yōu)化的參數(shù)選擇，解決了算法中存在的不足。論文實現(xiàn)了基于蟻群算法對TSP問題的求解和仿真。 關(guān)鍵字：關(guān)鍵字：蟻群算法，組合優(yōu)化，信息素，TSP 問題 機器學(xué)習(xí)（論文）目目 錄錄摘摘 要要.2第第 1 章章 緒論緒論.41.1 蟻群算法概況.41.2 論文的主要內(nèi)容.4第第 2 章章 基本蟻群算法簡介基本蟻群算法簡介.62.1 基本蟻群算

3、法的原理.62.1.1 蟻群行為描述.62.1.2 基本蟻群算法的機制原理.82.2 基本蟻群算法的系統(tǒng)學(xué)特征.92.2.1 分布式.92.2.2 自組織.102.2.3 正反饋.10第第 3 章章 組合優(yōu)化以及組合優(yōu)化以及 TSP 問題簡介問題簡介.113.1 組合優(yōu)化簡介.113.1.1 引言.113.1.2 組合優(yōu)化問題.113.1.3 NP 完全問題 .123.2 TSP 問題簡介.123.2.1 TSP 問題的定義.123.2.2 TSP 的實用價值.123.2.3 TSP 問題的理論意義.123.3 基本蟻群算法的數(shù)學(xué)模型.13第第 4 章章 基本蟻群算法求解基本蟻群算法求解 TS

4、P.154.1 基本蟻群算法求解 TSP 的實現(xiàn)流程.154.1.1 基本蟻群算法的實現(xiàn)步驟.154.1.2 基本蟻群算法的結(jié)構(gòu)流程.154.2 關(guān)鍵參數(shù)介紹.174.3 不同參數(shù)設(shè)置的試驗.174.3.1 信息素揮發(fā)度的設(shè)置.174.3.2 蟻群數(shù)量的設(shè)置.174.3.3 啟發(fā)式因子的設(shè)置.174.4 不同參數(shù)設(shè)置的試驗結(jié)果和結(jié)論.184.4.1 信息素揮發(fā)度的選擇設(shè)置.184.4.2 啟發(fā)式因子的選擇設(shè)置.21結(jié)論與展望結(jié)論與展望.26李亞龍 E201102016第第 1 章章 緒論緒論螞蟻是地球上最常見、數(shù)量最多的昆蟲種類之一，常常成群結(jié)隊地出現(xiàn)在人類的日常生活環(huán)境中。這些昆蟲的群體生物

5、智能特征，引起了一些學(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 年首先提出了蟻群算法。其主要

6、特點就是：通過正反饋、分布式協(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)的快速性是通過正反饋式的信息傳遞和積累來保證的。而算法的早熟性

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

8、美國世界通信公司以電子螞蟻為基礎(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)獲得成功的應(yīng)用，其中最成功的是在組合

9、優(yōu)化問題中的應(yīng)用。1.2 論文的主要內(nèi)容論文的主要內(nèi)容因為蟻群算法有很多種,并且TSP問題是蟻群算法眾多解決問題中的經(jīng)典問題,所以機器學(xué)習(xí)（論文）具有很大的隨意性。雖然蟻群算法的選擇性很多，但是所有的算法都是基于最基本的蟻群算法，并且基本蟻群算法也可以很好的解決TSP問題，以及說明參數(shù)選擇問題。所以本文以基本蟻群算法為基礎(chǔ)，重點討論了基本蟻群算法如何解決TSP問題。 第1章主要介紹了蟻群算法的歷史、發(fā)展、應(yīng)用，對蟻群算法原理的核心信息素作了簡單的描述。 第2章對基本蟻群算法的原理進行了介紹，包括基本蟻群算法的行為描述，機制原理。同時探討了基本蟻群算法的系統(tǒng)學(xué)特征。 第3章對組合優(yōu)化以及TSP問

10、題的定義，實用價值，理論意義進行了描述。并且介紹了基本蟻群算法求解TSP問題的數(shù)學(xué)模型。 第4章首先介紹了基本蟻群算法的實現(xiàn)步驟和結(jié)構(gòu)流程，然后討論了蟻群算法中主要參數(shù)對于蟻群算法的全局搜索能力以及收斂性的影響，并做了相應(yīng)仿真實驗加以驗證。李亞龍 E201102016第第 2 章章 基本蟻群算法簡介基本蟻群算法簡介2.1 基本蟻群算法的原理基本蟻群算法的原理2.1.1 蟻群行為描述蟻群行為描述根據(jù)仿生學(xué)家的長期研究發(fā)現(xiàn)：螞蟻雖然沒有視覺，但運動時會通過在路徑上釋放出一種特殊的分泌物信息素來尋找路徑。當它們碰到一個還沒有走過的路口的時，就隨機的挑選一條路徑前行，同時釋放出與路徑長度有關(guān)的信息素。

11、螞蟻走的路徑越長，則釋放的信息量越小。當后來的螞蟻再次碰到這個路口的時候，選擇信息量較大路徑的概率相對較大，這樣便形成了一個正反饋機制。最優(yōu)路徑上的信息量越來越大，而其他路徑上的信息量卻會隨著時間的流逝而逐漸消減，最終整個蟻群會找出最優(yōu)路徑。同時蟻群還能夠適應(yīng)環(huán)境的變化，當蟻群的運動路徑上突然出現(xiàn)障礙物時，螞蟻也能很快的重新找到最優(yōu)路徑?？梢?，在整個尋徑過程中，雖然單只螞蟻的選擇能力有限，但是通過信息素的作用使整個蟻群行為找出最優(yōu)路徑。這里用人工螞蟻覓食圖來描述蟻群搜索原理。圖 2.1 人工螞蟻覓食模擬機器學(xué)習(xí)（論文）圖 2.2 人工螞蟻覓食模擬圖 2.3 人工螞蟻覓食模擬李亞龍 E20110

12、2016圖 2.1 中，設(shè) A 點是蟻巢，D 點是食物源，EF 之間區(qū)域是障礙物。由于障礙物的存在，螞蟻只能經(jīng)由 A 經(jīng) E 或 F 到達 D，或由 D 到達 A，各點之間的距離如圖 2.1 所示。假設(shè)每個時間單位有 30 只螞蟻由 A 到達 D 點，有 30 只螞蟻由 D 到達 A 點，螞蟻過后留下的信息量為 1。為了方便起見，設(shè)該物質(zhì)停留時間為 1。在初始時刻，由于路徑 BF、FC、BE、EC 上均無信息存在，位于 A 和 D 的螞蟻可以隨機選擇路徑，從統(tǒng)計學(xué)的角度可以認為螞蟻以相同的概率選擇 BE、FC、BE、EC，如圖 2.2 所示。經(jīng)過一個時間單位后，在路徑 BFC 上的信息量是路徑

13、 BEC 上的信息量的 2 倍。又經(jīng)過一段時間，將有 20 只螞蟻由 B、F 和 C 點到達 D，如圖 2.3 所示。隨著時間的推移，螞蟻將會以越來越大的概率選擇路徑 BFC，最終將會完全選擇 BFC，從而找到由蟻巢到食物源的最短路徑。2.1.2 基本蟻群算法的機制原理基本蟻群算法的機制原理模擬螞蟻群體覓食行為的蟻群算法是作為一種新的計算智能模式引入，該算法基于以下基本假設(shè)： 1.螞蟻之間通過信息素和環(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)，即螞蟻是反

14、應(yīng)型適應(yīng)性主體。 3在個體水平上，每只螞蟻僅根據(jù)環(huán)境做出獨立選擇；在群體水平上，單只螞蟻的行為是隨機的，但蟻群可通過自組織過程形成高度有序的群體行為。 由上述假設(shè)和分析可見，基本蟻群算法的尋優(yōu)機制包含兩個基本階段：適應(yīng)階段和協(xié)作階段。在適應(yīng)階段，各候選解根據(jù)積累的信息不斷調(diào)整自身結(jié)構(gòu)，路徑上經(jīng)過的螞蟻越多，信息量越大，則該路徑越容易被選擇；時間越長，信息量會越小；在協(xié)作階段，候選解之間通過信息交流，以期望產(chǎn)生性能更好的解。 蟻群算法實際上是一類智能多主體系統(tǒng)，其自組織機制使得蟻群算法不需要對所求的問題的每一方面都有詳盡的認識。自組織本質(zhì)上體現(xiàn)了從無序到有序的動態(tài)演化，其邏輯結(jié)構(gòu)如下圖所示。機器

15、學(xué)習(xí)（論文）螞蟻個體A信息素的增量構(gòu)建螞蟻個體B信息素的增量構(gòu)建組合優(yōu)化問題蟻群活動規(guī)劃信息素更新管理信息素決策點問題表達圖 2.4 基本蟻群算法的邏輯結(jié)構(gòu)由圖2.4可見，先將具體的組合優(yōu)化問題表述成規(guī)范的格式，然后利用蟻群算法在“探索”和“利用”之間根據(jù)信息素這一反饋載體確定決策點，同時按照相應(yīng)的信息素更新規(guī)則對每只螞蟻個體的信息素進行增量構(gòu)建，隨后從整體角度規(guī)劃出蟻群活動的行為方向，周而復(fù)始，即可求出組合優(yōu)化的最優(yōu)解。2.2 基本蟻群算法的系統(tǒng)學(xué)特征基本蟻群算法的系統(tǒng)學(xué)特征基本蟻群算法在系統(tǒng)學(xué)上表現(xiàn)以下三個特征：分布式，自組織，正反饋。三者表現(xiàn)出一個整體，相輔相成。2.2.1 分布式分布式

16、自然界中的真實蟻群行為也出現(xiàn)了分布式。當蟻群需要完成某項工作時，其中的許多螞蟻都為共同目的進行著同樣的工作，而最終任務(wù)的完成不會由于某些個體的的缺陷而受到影響。 蟻群算法作為對蟻群覓食行為的抽象，也體現(xiàn)了群體行為的分布式特征。每只人工螞蟻在問題空間的多個點同時開始相互獨立地構(gòu)造問題解，而整個問題的求解不會因為某只人工螞蟻無法成功獲得解而受到影響。 具體到不同的優(yōu)化問題而言，蟻群算法體現(xiàn)出的分布式特征就具有了更加現(xiàn)實的意義。因為所有的仿生優(yōu)化算法均可看做按照一定規(guī)則的問題解空間搜索最優(yōu)解的過程，所以搜索點的初始選取就直接關(guān)系到算法求解結(jié)果的優(yōu)劣和算法尋優(yōu)效率。當求解許多復(fù)雜問題時，從一點出發(fā)的搜

17、索受到局部特征的限制，可得不到所求問題的滿李亞龍 E201102016意解；而基本蟻群算法則可看做是一個分布式的多智能系統(tǒng)，它在問題空間的多點同時獨立地進行解搜索，不僅使得算法具有較強的全局搜索能力，也增加了算法的可靠性。2.2.2 自組織自組織基本蟻群算法的另一個重要特征是自組織。自組織的概念是隨著系統(tǒng)科學(xué)的發(fā)展而建立起來的。通常把系統(tǒng)論中的組織行為分為自組織和他組織兩大類4。其根本區(qū)別在于組織力或組織指令是來自于系統(tǒng)內(nèi)部還是來自于系統(tǒng)外部，前者稱為自組織，而后者即為他組織。如果系統(tǒng)在獲得時間的、空間的或者功能的結(jié)果過程中，沒有外界的特定干預(yù)，則稱為系統(tǒng)是自組織的。 從抽象意義上講，自組織就

18、是在沒有外界作用下使得系統(tǒng)從無序到有序的進化過程?；鞠伻核惴w現(xiàn)了這一過程，以蟻群優(yōu)化為例，當算法開始的初期，單只人工螞蟻無序地尋找解，經(jīng)過一段時間的算法演化，人工螞蟻越來越趨向于尋找到接近最優(yōu)解的一些解，這恰恰體現(xiàn)了從無序到有序的自組織進化。 自組織大大增強了算法的魯棒性5（在這里可以理解為算法抗干擾性,就是指不是針對具體問題算法也同樣可以求解,極大的體現(xiàn)了蟻群算法的抗干擾能力） ，傳統(tǒng)的算法都是針對某一具體問題而設(shè)計的，這往往建立在對該問題有了全面清晰認識的基礎(chǔ)上，通常很難適應(yīng)其他問題。而自組織的蟻群算法不需要對待求解問題的所有問題的所有方面都有所認識，因而較容易應(yīng)用到一類問題中。2.2

19、.3 正反饋正反饋反饋是控制論中的重要概念，它代表信息輸入對輸出的反作用。在系統(tǒng)學(xué)上認為，反饋就是把系統(tǒng)現(xiàn)在的行為作為影響系統(tǒng)未來行為的原因。反饋分正反饋和負反饋兩種，前者指的是以現(xiàn)在的行為去加強未來的行為，而后者則是以現(xiàn)在的行為去削弱未來的行為。 由自然界中真實螞蟻的覓食行為可見，螞蟻能夠最終找到最短路徑，直接依賴于最短路徑上信息素的堆積，而信息素的堆積卻是一個正反饋的過程，對于基本蟻群算法而言，初始時在環(huán)境中存在完全相同的信息量，給系統(tǒng)一個微小的擾動，使得各個邊上的信息量大小不同，螞蟻構(gòu)造的解就存在了優(yōu)劣。算法采用的反饋方式是在較優(yōu)解經(jīng)過的路徑留下更多的信息素，更多的信息素又吸引了更多的螞

20、蟻，這個正反饋的過程使得初始值不斷地擴大，同時又引導(dǎo)整個系統(tǒng)向著最優(yōu)解的方向進化。 單一的正反饋或者負反饋存在于線形系統(tǒng)之中，是無法實現(xiàn)系統(tǒng)的自我組織的。自組織系統(tǒng)通過正反饋和負反饋機制，它體現(xiàn)于蟻群算法在構(gòu)造問題解的過程中用到了概率搜索技術(shù)，通過該技術(shù)增加了生成解的隨機性。隨機性的影響就在于接受了解在一定程度上的退化，另一方面又使得搜索范圍得以在一段時間內(nèi)保持足夠大。這樣正反饋縮小搜索范圍，保證算法朝著最優(yōu)解的方向進行；而負反饋保持搜索范圍，避免算法過早收斂于不好的結(jié)果。恰恰是在正反饋和負反饋共同作用影響下，基本蟻群算法得以自組織地進化，從而得到問題在一定程度上的滿意解。機器學(xué)習(xí)（論文）第第

21、 3 章章 組合優(yōu)化以及組合優(yōu)化以及 TSP 問題簡介問題簡介3.1 組合優(yōu)化簡介組合優(yōu)化簡介3.1.1 引言引言伴隨計算機技術(shù)的飛速發(fā)展，計算機正日益成為人們解決問題的不可或缺的重要工具。但在實踐中人們發(fā)現(xiàn)，存在這樣一類問題，運用精確的算法在多項式時間內(nèi)無法找到問題的最優(yōu)解，這類問題稱為組合優(yōu)化問題。這類問題通常隨著問題規(guī)模的擴大，問題空間呈現(xiàn)組合爆炸特征，求解問題的空間、時間復(fù)雜度將呈指數(shù)級增長，使用常規(guī)的方法求解，在現(xiàn)有條件下是無法實現(xiàn)的，屬于 NP 完全問題。TSP 問題就是其中最經(jīng)典問題之一。因此利用仿生進化算法，在較短的時間內(nèi)，求得問題的滿意解，就成為研究的重點。3.1.2 組合優(yōu)

22、化問題組合優(yōu)化問題組合優(yōu)化問題的目標是從組合問題的可行解中求出最優(yōu)解。在現(xiàn)實世界里存在大量組合優(yōu)化問題，其中許多問題如旅行商問題、圖著色問題、分配問題、調(diào)度問題、布線問題及路由選擇問題等，至今沒有找到有效地多項式算法，這些問題己被證明是NP 完全問題。 優(yōu)化問題有三個基本要素:變量、約束和目標函數(shù)。在求解過程中選定的基本參數(shù)稱為變量，對變量取值的限制稱為約束，表示可行方案衡量標準的函數(shù)稱為目標函數(shù)。組合優(yōu)化問題就是在給定的約束條件下，求目標函數(shù)最優(yōu)值的問題。組合優(yōu)化問題的一個實例可以表示為一個對偶（S，f） ，其中解空間 S 為可行解目標函數(shù) f 是一個映射，定義為:fSR求目標函數(shù)最小值問題

23、稱為最小化問題，記為：min( ),f i iS求目標函數(shù)最大值問題稱為最大值問題，記為：max( ),f i iS顯然，只要改變目標函數(shù)的符號，最小化問題與最大化問題就可以等價轉(zhuǎn)換。使目標函數(shù)最優(yōu)值的解稱為最優(yōu)解（整體最優(yōu)解） 。設(shè)（S，f）是組合優(yōu)化問題的一個實例，,若： （對所有的成立） ，稱為最小化問題aptiS()( )aptf if iiSapti的最優(yōu)解。min( ),f i iS優(yōu)化問題在工程中有著廣泛的應(yīng)用，其涉及的問題是在一組限制條件下求解問題的最好(或最優(yōu))解的問題。按照人類認知問題的特點，最優(yōu)化問題很自然的被劃分為兩類:一類是連續(xù)變量的問題，另一類是離散變量的問題。對于

24、離散變量問題來說，一般是尋找離散事件的最優(yōu)編排，分組，次序或篩選等。不難看出這些問題的解的個數(shù)是有限的。通常把這類問題稱為組合最優(yōu)化問題，而研究用數(shù)學(xué)方法來求解這些問題就被稱為組合最優(yōu)化。李亞龍 E2011020163.1.3 NP 完全問題完全問題按照計算復(fù)雜性理論研究問題求解的難易性，可把問題分為P類、NP類和NP完全類。 定義一:對于判定問題 D，存在一個多項式 P（t） ，使得對其每一輸入規(guī)模為 n 的實例，可以在 P(n)時間內(nèi)求得最優(yōu)解，此類問題稱為 P(Polynomial)問題。其它的則是NP(Non 一 Polynomial)問題。假如一個問題是 P 問題，我們通常認為它是“

25、簡單的”，而 NP 問題，通常認為它是“復(fù)雜的”。NP 問題是指可在多項式時間里檢驗的問題，至今尚未找到多項式時間算法。定義二：若問題,所有NP問題都可以經(jīng)過多項式計算時間轉(zhuǎn)化為L，則L稱LNP為NP完全問題。 如果 NP 完全類問題中有一個問題能用多項式確定性算法解決，則其他所有的 NP完全類問題都能用多項式確定性算法來解決，很多問題被證明為 NP 完全問題，如 TSP問題，NP 完全問題也是檢驗仿生算法有效性和可靠性的有效平臺。3.2 TSP 問題簡介問題簡介3.2.1 TSP 問題的定義問題的定義TSP問題的英文名（traveling salesman problem）,中文譯為旅行商問

26、題。問題的定義很簡單，即為一個旅行商要走訪N個城市，每個城市必須經(jīng)過一次且只能經(jīng)過一次，最后回到出發(fā)的城市就算是完成了一次旅行，問如何能找到一條最短的路徑。其相應(yīng)的數(shù)學(xué)描述如下：設(shè)有一個城市集合，其每對城市間的距1234 ,. nCc c c cc,ijc cC離為。求一條經(jīng)過C中每個城市正好一次的路徑，( ,)iid c cZ 1234,.,nccccc使得最小。 1111,niinid ccd cc3.2.2 TSP 的實用價值的實用價值TSP 問題廣泛的存在于許多領(lǐng)域，而且問題規(guī)模（城市的數(shù)目）都很大。比如說，電路板鉆孔問題，X 射線結(jié)晶學(xué)問題，VLSL（超大規(guī)模集成電路）制造問題等等。

27、總之，凡是可以抽象成為遍歷全部城市一次且僅一次，求代價最小的路徑的問題，都可以當作 TSP 問題來解決。3.2.3 TSP 問題的理論意義問題的理論意義同實用價值相比，TSP 問題的理論意義更加重大。事實上，該問題是作為所有組合優(yōu)化問題的范例而存在的11。它己經(jīng)成為并將繼續(xù)成為測試新算法的標準問題。這是因為，TSP 問題展示了組合優(yōu)化的所有方面。它從概念上來講非常簡單，但是其求解的難度是很大的。如果針對 TSP 問題提出的某種算法能夠取得比較好的實算效果，機器學(xué)習(xí)（論文）那么對其進行修改，就可以應(yīng)用于其它類型的組合優(yōu)化問題并取得良好的效果?；谏鲜鲈?，該問題吸引了許多不同領(lǐng)域的研究者。3.3

28、 基本蟻群算法的數(shù)學(xué)模型基本蟻群算法的數(shù)學(xué)模型設(shè)為 t 時刻路徑（i,j）上的信息量，n 表示 TSP 規(guī)模，m 為蟻群中螞蟻的總 ijt數(shù)目。在初始時刻各條路徑上的信息量相等，并設(shè)。 0ijconst螞蟻 k（k=1,2,m）在運動過程中，根據(jù)各條路徑上的信息量決定其轉(zhuǎn)移方向，這里用禁忌表來記錄螞蟻 k 當前所走過的城市，集合隨著進化1,2,.,ktabukmktabu過程作動態(tài)調(diào)整。在搜索過程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來計算狀態(tài)轉(zhuǎn)移概率。表示在 t 螞蟻 k 由城市 i 轉(zhuǎn)移到城市 j 的狀態(tài)轉(zhuǎn)移概率 kijpt 0ijikisiss allowedkttttkijpt

29、式中，表示螞蟻 k 下一步允許選擇的城市； 為信息啟發(fā)式因子，表示軌kallowed跡的相對重要性，反映了螞蟻在運動過程中所積累的信息在螞蟻運動時的所起的作用，其值越大，則該螞蟻越傾向于選擇其他螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強；為期望啟發(fā)式因子，表示能見度的相對重要性，反映了螞蟻在運動過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則；為啟發(fā)函數(shù)，其表達式如下： ijt 1ijijtd式中，表示相鄰兩個城市之間的距離。對螞蟻 k 而言，越小，則越大，ijd ijt也就越大。顯然，該啟發(fā)函數(shù)表示螞蟻從城市 i 轉(zhuǎn)移到城市 j 的期望程度。 kijpt為了避

30、免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻走完一步或者完成對所有 n 個城市遍歷（也即一個循環(huán)結(jié)束）后，要對殘留信息進行更新處理。這種更新策略模仿了人類大腦記憶的特點，在新信息不斷存入大腦的同時，存儲在大腦中的舊信息隨著時間的推移逐漸淡化，甚至忘記。由此，t+n 時刻在路徑（i,j）上的信息量可按如下規(guī)則進行調(diào)整 1ijijijtntt 1mkijijktt式中， 表示信息素揮發(fā)系數(shù)，則 1- 表示信息素殘留因子，為了防止信息的無限積累， 的取值范圍為：表示本次循環(huán)中路徑（i,j）上的信息素增 0,1 ;ijt量，初始時刻表示第 k 只螞蟻在本次循環(huán)中留在路徑（i,j）上的信 00,

31、kijijt李亞龍 E201102016息量。根據(jù)信息素更新策略的不同，Dorigo M 提出了三種不同的基本蟻群算法模型，分別稱之為 Ant-Cycle 模型、Ant-Quantity 模型及 Ant-Density 模型，其差別在于求法的不同。 kijt在 Ant-Cycle 模型中ktt+1ij0kQLkij如果第只螞蟻在時間到之間經(jīng)過邊（，）否則式中，Q 表示信息素強度，它在一定程度上影響算法的收斂程度；表示第 k 只kL螞蟻在本次循環(huán)中所走過路徑的總長度。 在 Ant-Quantity 模型中ktt+1ij0ijQdkij如果第只螞蟻在時間到之間經(jīng)過邊（，）否則在 Ant-Densi

32、ty 模型中ktt+1ij0Qkij如果第只螞蟻在時間到之間經(jīng)過邊（，）否則后兩個公式中利用的是局部信息，即螞蟻完成一步后更新路徑上的信息素；而第一個公式中利用的是整體信息，即螞蟻完成一次循環(huán)后更新所有路徑上的信息素，在求解 TSP 時性能較好，因此通常采用第一個公式作為蟻群算法的基本模型。機器學(xué)習(xí)（論文）第第 4 章章 基基本蟻群算法求解本蟻群算法求解 TSP4.1 基本蟻群算法求解基本蟻群算法求解 TSP 的實現(xiàn)流程的實現(xiàn)流程4.1.1 基本蟻群算法的實現(xiàn)步驟基本蟻群算法的實現(xiàn)步驟以 TSP 為例，基本蟻群算法的具體實現(xiàn)步驟如下： （1）參數(shù)初始化。令時間 t=0 和循環(huán)次數(shù)=0，設(shè)置最大

33、循環(huán)次數(shù)，將 mcNmaxcN只螞蟻置于 n 個城市上，令每條邊（i,j）的初始化信息量，其中 const 表 ijtconst示常數(shù)，且初始時刻。 00ij（2）循環(huán)次數(shù)。 1ccNN（3）螞蟻的禁忌表索引號 k=1 （4）螞蟻數(shù)目。 1kk（5）螞蟻個體根據(jù)狀態(tài)轉(zhuǎn)移概率公式計算的概率選擇城市 j。 （6）修改禁忌表指針，即選擇好之后將螞蟻移動到新的城市，并把該城市移動到該螞蟻個體的禁忌表中。 （7）若集合 C 中的城市未遍歷完，即 k=螞蟻總數(shù)m？信息量更新滿足結(jié)束條件？輸出程序計算結(jié)果結(jié)束YYNN圖 4.1 基本蟻群算法的程序結(jié)構(gòu)流程機器學(xué)習(xí)（論文）4.2 關(guān)鍵參數(shù)介紹關(guān)鍵參數(shù)介紹蟻群算

34、法中 、 等參數(shù)對算法性能有很大的影響。 值的大小表明留在每個結(jié)點上的信息量受重視的程度， 值越大，螞蟻選擇以前經(jīng)過的路線的可能性越大，但過大會使搜索過早陷于局部最小解； 的大小表明啟發(fā)式信息受重視的程度， 值越大，螞蟻選擇離它近的城市的可能性越大； 表示信息素的保留率，如果它的值取的不恰當，得到的結(jié)果會很差。4.3 不同參數(shù)設(shè)置的試驗不同參數(shù)設(shè)置的試驗蟻群算法中信息啟發(fā)式因子 、期望啟發(fā)式因子 、揮發(fā)系數(shù) 、螞蟻數(shù)目 m的設(shè)置值的不同會對蟻群算法的全局搜索能力和收斂速度產(chǎn)生很大的影響，接下來會對不同參數(shù)的設(shè)置對蟻群算法性能的影響進行描述，然后給出實驗結(jié)果和結(jié)論。4.3.1 信息素揮發(fā)度的設(shè)置

35、信息素揮發(fā)度的設(shè)置在蟻群算法中，人工螞蟻是具有人類記憶功能的，隨著時間的推移，以前留下的信息將要逐漸消逝。在算法模型中用參數(shù) 表示信息消逝程度（或稱信息素揮發(fā)度） ，而 1 就是信息素保留系數(shù)。蟻群算法存在著收斂速度慢、易于陷入局部最優(yōu)等缺陷。而信息素揮發(fā)度 的大小直接關(guān)系到蟻群算法的全局搜索能力及其收斂速度：由于信息素 的存在，當要處理的問題規(guī)模比較大時，會使那些從來未被搜索到的路徑（可行解）上的信息量減小到接近于 0，因而降低了算法的全局搜索能力，而且當 過大時以前搜索過的路徑被再次選擇的可能性過大，也會影響到算法的隨機性能和全局搜索能力；反之，通過減小信息素揮發(fā)度 雖然可以提高算法的隨機

36、性能和全局搜索能力，但又會使算法的收斂速度降低。關(guān)于蟻群算法中信息素揮發(fā)度 對算法性能的影響及其在實際應(yīng)用中的選擇，可以通過計算機仿真實驗來分析和確定。 4.3.2 蟻群數(shù)量的設(shè)置蟻群數(shù)量的設(shè)置蟻群算法是一種隨機搜索算法，通過多個候選解(可行解的一個子集)組成的群體的進化過程來尋求最優(yōu)解，在該過程中既需要每個個體的自適應(yīng)能力，更需要群體的相互協(xié)作。蟻群在搜索過程中之所以表現(xiàn)出復(fù)雜而有序的行為，個體之間的信息交流與相互協(xié)作起著至關(guān)重要的作用。對于 TSP 問題，單個螞蟻在一次循環(huán)中所經(jīng)過的路徑，表現(xiàn)為問題可行解集中的一個解，m 只螞蟻在一次循環(huán)中所經(jīng)過的路徑，則表現(xiàn)為問題解集中的一個子集。顯然;

37、子集越大(即蟻群數(shù)量多)可以提高蟻群算法的全局搜索能力以及算法的穩(wěn)定性;但螞蟻數(shù)目增大后，會使大量的曾被搜索過的解(路徑)上的信息量的變化比較平均，信息正反饋的作用不明顯，搜索的隨機性雖然得到了加強，但收斂速度減慢;反之，子集較小(即蟻群數(shù)量少)，特別是當要處理的問題規(guī)模比較大時，會使那些從來未被搜索到的解(路徑)上的信息量減小到接近于 0，搜索的隨機性減弱，雖然收斂速度加快，但會使算法的全局性能降低，算法的穩(wěn)定性差，容易出現(xiàn)過早停滯現(xiàn)象。4.3.3 啟發(fā)式因子的設(shè)置啟發(fā)式因子的設(shè)置信息啟發(fā)式因子 反映螞蟻在運動過程中所積累的信息量(即殘留信息量)在 ijt指導(dǎo)蟻群搜索中的相對重要程度，期望值

38、啟發(fā)式因子 反映螞蟻在運動過程中啟發(fā)信息(即期望值)在指導(dǎo)蟻群搜索中的相對重要程度。期望值啟發(fā)式因子 的大小反映ij了蟻群在路徑搜索中先驗性、確定性。 因素作用的強度，其值越大，螞蟻在某個局李亞龍 E201102016部點上選擇局部最短路徑的可能性越大，雖然搜索的收斂速度得以加快，但蟻群在最優(yōu)路徑的搜索過程中隨機性減弱，易于陷入局部最優(yōu);而信息啟發(fā)式因子 的大小則反映了蟻群在路徑搜索中隨機性因素作用的強度，其值越大，螞蟻選擇以前走過的路徑的可能性越大，搜索的隨機性減弱，當 值過大也會使蟻群的搜索過早陷于局部最優(yōu)。蟻群算法的全局尋優(yōu)性能，首先要求蟻群的搜索過程必須有很強的隨機性;而蟻群算法的快速

39、收斂性能，又要求蟻群的搜索過程必須要有較高的確定性。因此，兩者對蟻群算法性能的影響和作用是相互配合、密切相關(guān)的。4.4 不同參數(shù)設(shè)置的實驗結(jié)果和結(jié)論不同參數(shù)設(shè)置的實驗結(jié)果和結(jié)論本文采用缺省參數(shù)設(shè)置為 1=、5=、5.0=,螞蟻的數(shù)目總是設(shè)置為城市的總數(shù)目，即初始時刻每個城市放置一個螞蟻。實驗中所有 TSP 問題數(shù)據(jù)來源于 Eli51 城市問題（這是蟻群算法解決 TSP 問題的經(jīng)典城市數(shù)據(jù)） 。4.4.1 信息素揮發(fā)度的選擇設(shè)置信息素揮發(fā)度的選擇設(shè)置按照以上的實驗描述，在其他參數(shù)不變的情況下，使信息素揮發(fā)系數(shù)的變化為。信息素揮發(fā)系數(shù)對性能影響仿真結(jié)果如圖 4.24.6 和表 4.1 所示：0.1

40、,0.3,0.5,0.7,0.9（1）=2，=5，=0.1，NcMax=10圖 4.2 選擇不同信息素揮發(fā)度結(jié)果圖 1（2）=2，=5，=0.3，NcMax=10機器學(xué)習(xí)（論文）圖 4.3 選擇不同信息素揮發(fā)度結(jié)果圖 2（3）=2，=5，=0.5，NcMax=10圖 4.4 選擇不同信息素揮發(fā)度結(jié)果圖 3（4）=2，=5，=0.7，NcMax=10李亞龍 E201102016圖 4.5 選擇不同信息素揮發(fā)度結(jié)果圖 4（5）=2，=5，=0.9，NcMax=10圖 4.6 選擇不同信息素揮發(fā)度結(jié)果圖 5表 4.1 信息素揮發(fā)度對算法性能的影響揮發(fā)系數(shù) 最優(yōu)路徑長度 搜索循環(huán)次數(shù) 0.1581.6

41、51100.3599.786100.5610.637100.7600.225100.9599.74110機器學(xué)習(xí)（論文）由仿真實驗不難看出，在其他參數(shù)相同的情況下，信息素揮發(fā)度 的大小對蟻群算法的收斂性能影響極大，特別是當 很小時，由于路徑上的殘留信息占主導(dǎo)地位，信息正反饋的作用相對較強，搜索的隨機性減落，因而蟻群算法的收斂速度加快；而在 比較大時，由于信息正反饋的作用占主導(dǎo)地位，搜索的隨機性增強，全局搜索能力增強，但收斂速度太慢。因而關(guān)于蟻群算法的信息素揮發(fā)度 的選擇，必須綜合全局搜索能力和收斂速度兩項性能指標，由圖可知在，算法的性能比較穩(wěn)定和一0.1致，搜索的全局性和收斂速度比較好。4.4

42、.2 啟發(fā)式因子的選擇設(shè)置啟發(fā)式因子的選擇設(shè)置關(guān)于蟻群算法中啟發(fā)式因子 及 對算法性能的影響及其在實際應(yīng)用中的選擇，也可以通過計算機仿真實驗來分析和確定。在其它參數(shù)不變的情況下，取啟發(fā)式因子 和 不同數(shù)值的組合。啟發(fā)式因子 和 對算法性能影響的仿真結(jié)果如圖4.74.13 和表 4.2 所示。（1）=0.1，=0.5，=0.1，NcMax=10圖 4.7 選擇不同啟發(fā)式因子結(jié)果圖 1（2）=0.1，=1，=0.1，NcMax=10李亞龍 E201102016圖 4.8 選擇不同啟發(fā)式因子結(jié)果圖 2（3）=0.2，=2，=0.1，NcMax=10圖 4.9 選擇不同啟發(fā)式因子結(jié)果圖 3（4）=0.3，=3，=0.1，NcMax=10機器學(xué)習(xí)（論文）圖 4.10 選擇不同啟發(fā)式因子結(jié)果圖 4（5）=1.0，=4，=0.1，NcMax=10