1、 .0 成績: 機器學習姓名： 張瑞 班號： 05071402 學號： 2014301384 目 錄第1章 緒論1.1 蟻群算法概況第2章 基本蟻群算法簡介2.1 基本蟻群算法的原理2.1.1 蟻群行為描述2.1.2 基本蟻群算法的機制原理2.2 基本蟻群算法的系統學特征2.2.1 分布式2.2.2 自組織2.2.3 正反饋 第1章緒論螞蟻是地球上最常見、數量最多的昆蟲種類之一，常常成群結隊地出現在人類的日常生活環境中。這些昆蟲的群體生物智能特征，引起了一些學者的注意。意大利學者M.Dorigo，V.Maniezzo等人在觀察螞蟻的覓食習性時發現，螞蟻總能找到巢穴與食物源之間的最短路徑。經研究

2、發現，螞蟻的這種群體協作功能是通過一種遺留在其來往路徑上的叫做信息素（Pheromone）的揮發性化學物質來進行通信和協調的。化學通信是螞蟻采取的基本信息交流方式之一，在螞蟻的生活習性中起著重要的作用。通過對螞蟻覓食行為的研究，他們發現，整個蟻群就是通過這種信息素進行相互協作，形成正反饋，從而使多個路徑上的螞蟻都逐漸聚集到最短的那條路徑上。1.1 蟻群算法概況M.Dorigo等人于1991年首先提出了蟻群算法。其主要特點就是：通過正反饋、分布式協作來尋找最優路徑。這是一種基于種群尋優的啟發式搜索算法。它充分利用了生物蟻群能通過個體間簡單的信息傳遞，搜索從蟻巢至食物間最短路徑的集體尋優特征1，以

3、及該過程與旅行商問題求解之間的相似性。得到了具有NP難度的旅行商問題的最優解答。同時，該算法還被用于求解Job-Shop調度問題、二次指派問題以及多維背包問題等，顯示了其適用于組合優化類問題求解的優越特征。 蟻群算法之所以能引起相關領域研究者的注意，是因為這種求解模式能將問題求解的快速性、全局優化特征以及在有限時間內答案的合理性結合起來。其中，尋優的快速性是通過正反饋式的信息傳遞和積累來保證的。而算法的早熟性收斂又可以通過其分布式計算特征加以避免，同時，具有貪婪啟發式搜索特征的蟻群系統又能在搜索過程的早期找到可以接受的問題解答。這種優越的問題分布式求解模式經過相關領域研究者的關注和努力，已經在

4、最初的算法模型基礎上得到了很大的改進和拓展。 以蟻群算法為代表的群智能已成為當今分布式人工智能研究的一個熱點，許多源于蜂群和蟻群模型設計的算法己越來越多地被應用于企業的運轉模式的研究2。美國五角大樓正在資助關于群智能系統的研究工作-群體戰略（Swarm Strategy），它的一個實戰用途是通過運用成群的空中無人駕駛飛行器和地面車輛來轉移敵人的注意力，讓自己的軍隊在敵人后方不被察覺地安全進行。英國電信公司和美國世界通信公司以電子螞蟻為基礎，對新的電信網絡管理方法進行了試驗。國內，國家自然科學基金”十五”期間學科交叉類優先資助領域中的認知科學及其信息處理的研究內容中也明確列出了群智能領域的進化、

5、自適應與現場認知主題。 多年來世界各地研究工作者對蟻群算法進行了精心研究和應用開發，該算法現已被大量應用于數據分析、機器人協作問題求解、電力、通信、水利、采礦、化工、建筑、交通5等領域。蟻群算法最初用于解決TSP問題，經過多年的發展，已經陸續滲透到其他領域中，如圖著色問題、大規模集成電路設計、通訊網絡中的路由問題以及負載平衡問題、車輛調度問題等。蟻群算法在若干領域已經獲得成功的應用，其中最成功的是在組合優化問題中的應用。第2章 基本蟻群算法簡介2.1 基本蟻群算法的原理2.1.1 蟻群行為描述根據仿生學家的長期研究發現：螞蟻雖然沒有視覺，但運動時會通過在路徑上釋放出一種特殊的分泌物信息素來尋找

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

7、蟻覓食模擬圖 2.2 人工螞蟻覓食模擬圖 2.3 人工螞蟻覓食模擬圖2.1中，設A點是蟻巢，D點是食物源，EF之間區域是障礙物。由于障礙物的存在，螞蟻只能經由A經E或F到達D，或由D到達A，各點之間的距離如圖2.1所示。假設每個時間單位有30只螞蟻由A到達D點，有30只螞蟻由D到達A點，螞蟻過后留下的信息量為1。為了方便起見，設該物質停留時間為1。在初始時刻，由于路徑BF、FC、BE、EC上均無信息存在，位于A和D的螞蟻可以隨機選擇路徑，從統計學的角度可以認為螞蟻以相同的概率選擇BE、FC、BE、EC，如圖2.2所示。經過一個時間單位后，在路徑BFC上的信息量是路徑BEC上的信息量的2倍。又經

8、過一段時間，將有20只螞蟻由B、F和C點到達D，如圖2.3所示。隨著時間的推移，螞蟻將會以越來越大的概率選擇路徑BFC，最終將會完全選擇BFC，從而找到由蟻巢到食物源的最短路徑。2.1.2 基本蟻群算法的機制原理模擬螞蟻群體覓食行為的蟻群算法是作為一種新的計算智能模式引入，該算法基于以下基本假設： 1.螞蟻之間通過信息素和環境進行通信。每只螞蟻僅根據其周圍的局部環境作出反應，也只對其周圍的局部環境產生影響。 2.螞蟻對環境的反應由其內部模式決定。因為螞蟻是基因生物，螞蟻的行為實際上是其 基因的適應性表現，即螞蟻是反應型適應性主體。 3在個體水平上，每只螞蟻僅根據環境做出獨立選擇；在群體水平上，

9、單只螞蟻的行為是隨機的，但蟻群可通過自組織過程形成高度有序的群體行為。 由上述假設和分析可見，基本蟻群算法的尋優機制包含兩個基本階段：適應階段和協作階段。在適應階段，各候選解根據積累的信息不斷調整自身結構，路徑上經過的螞蟻越多，信息量越大，則該路徑越容易被選擇；時間越長，信息量會越小；在協作階段，候選解之間通過信息交流，以期望產生性能更好的解。 蟻群算法實際上是一類智能多主體系統，其自組織機制使得蟻群算法不需要對所求的問題的每一方面都有詳盡的認識。自組織本質上體現了從無序到有序的動態演化，其邏輯結構如下圖所示。圖 2.4 基本蟻群算法的邏輯結構由圖2.4可見，先將具體的組合優化問題表述成規范的

10、格式，然后利用蟻群算法在“探索”和“利用”之間根據信息素這一反饋載體確定決策點，同時按照相應的信息素更新規則對每只螞蟻個體的信息素進行增量構建，隨后從整體角度規劃出蟻群活動的行為方向，周而復始，即可求出組合優化的最優解。2.2 基本蟻群算法的系統學特征基本蟻群算法在系統學上表現以下三個特征：分布式，自組織，正反饋。三者表現出一個整體，相輔相成。2.2.1 分布式自然界中的真實蟻群行為也出現了分布式。當蟻群需要完成某項工作時，其中的許多螞蟻都為共同目的進行著同樣的工作，而最終任務的完成不會由于某些個體的的缺陷而受到影響。 蟻群算法作為對蟻群覓食行為的抽象，也體現了群體行為的分布式特征。每只人工螞

11、蟻在問題空間的多個點同時開始相互獨立地構造問題解，而整個問題的求解不會因為某只人工螞蟻無法成功獲得解而受到影響。 具體到不同的優化問題而言，蟻群算法體現出的分布式特征就具有了更加現實的意義。因為所有的仿生優化算法均可看做按照一定規則的問題解空間搜索最優解的過程，所以搜索點的初始選取就直接關系到算法求解結果的優劣和算法尋優效率。當求解許多復雜問題時，從一點出發的搜索受到局部特征的限制，可得不到所求問題的滿意解；而基本蟻群算法則可看做是一個分布式的多智能系統，它在問題空間的多點同時獨立地進行解搜索，不僅使得算法具有較強的全局搜索能力，也增加了算法的可靠性。2.2.2 自組織基本蟻群算法的另一個重要

12、特征是自組織。自組織的概念是隨著系統科學的發展而建立起來的。通常把系統論中的組織行為分為自組織和他組織兩大類4。其根本區別在于組織力或組織指令是來自于系統內部還是來自于系統外部，前者稱為自組織，而后者即為他組織。如果系統在獲得時間的、空間的或者功能的結果過程中，沒有外界的特定干預，則稱為系統是自組織的。 從抽象意義上講，自組織就是在沒有外界作用下使得系統從無序到有序的進化過程。基本蟻群算法體現了這一過程，以蟻群優化為例，當算法開始的初期，單只人工螞蟻無序地尋找解，經過一段時間的算法演化，人工螞蟻越來越趨向于尋找到接近最優解的一些解，這恰恰體現了從無序到有序的自組織進化。 自組織大大增強了算法的

13、魯棒性5（在這里可以理解為算法抗干擾性,就是指不是針對具體問題算法也同樣可以求解,極大的體現了蟻群算法的抗干擾能力），傳統的算法都是針對某一具體問題而設計的，這往往建立在對該問題有了全面清晰認識的基礎上，通常很難適應其他問題。而自組織的蟻群算法不需要對待求解問題的所有問題的所有方面都有所認識，因而較容易應用到一類問題中。2.2.3 正反饋反饋是控制論中的重要概念，它代表信息輸入對輸出的反作用。在系統學上認為，反饋就是把系統現在的行為作為影響系統未來行為的原因。反饋分正反饋和負反饋兩種，前者指的是以現在的行為去加強未來的行為，而后者則是以現在的行為去削弱未來的行為。 由自然界中真實螞蟻的覓食行為可見，螞蟻能夠最終找到最短路徑，直接依賴于最短路徑上信息素的堆積，而信息素的堆積卻是一個正反饋的過程，對于基本蟻群算法而言，初始時在環境中存在完全相同的信息量，給系統一個微小的擾動，使得各個邊上的信息量大小不同，螞蟻構造的解就存在了優劣。算法采用的反饋方式是在較優解經過的路徑留下更多的信息素，更多的信息素又吸引了更多的螞蟻，這個正反饋的過程使得初始值不斷地擴大，同時又引導整個系統向著最優解的方向進化。 單一的正反饋或者負反饋存在于線形系統之中，是無法實現系統的自我