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

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

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

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

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

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

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

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

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

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

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

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

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