機(jī)器學(xué)習(xí)論文張瑞

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

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

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

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

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

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

7、蟻覓食模擬圖 2.2 人工螞蟻覓食模擬圖 2.3 人工螞蟻覓食模擬圖2.1中，設(shè)A點(diǎn)是蟻巢，D點(diǎn)是食物源，EF之間區(qū)域是障礙物。由于障礙物的存在，螞蟻只能經(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)，螞蟻過(guò)后留下的信息量為1。為了方便起見(jiàn)，設(shè)該物質(zhì)停留時(shí)間為1。在初始時(shí)刻，由于路徑BF、FC、BE、EC上均無(wú)信息存在，位于A和D的螞蟻可以隨機(jī)選擇路徑，從統(tǒng)計(jì)學(xué)的角度可以認(rèn)為螞蟻以相同的概率選擇BE、FC、BE、EC，如圖2.2所示。經(jīng)過(guò)一個(gè)時(shí)間單位后，在路徑BFC上的信息量是路徑BEC上的信息量的2倍。又經(jīng)

8、過(guò)一段時(shí)間，將有20只螞蟻由B、F和C點(diǎn)到達(dá)D，如圖2.3所示。隨著時(shí)間的推移，螞蟻將會(huì)以越來(lái)越大的概率選擇路徑BFC，最終將會(huì)完全選擇BFC，從而找到由蟻巢到食物源的最短路徑。2.1.2 基本蟻群算法的機(jī)制原理模擬螞蟻群體覓食行為的蟻群算法是作為一種新的計(jì)算智能模式引入，該算法基于以下基本假設(shè)： 1.螞蟻之間通過(guò)信息素和環(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ú)立選擇；在群體水平上，

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

10、格式，然后利用蟻群算法在“探索”和“利用”之間根據(jù)信息素這一反饋載體確定決策點(diǎn)，同時(shí)按照相應(yīng)的信息素更新規(guī)則對(duì)每只螞蟻個(gè)體的信息素進(jìn)行增量構(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)了群體行為的分布式特征。每只人工螞

11、蟻在問(wèn)題空間的多個(gè)點(diǎn)同時(shí)開(kāi)始相互獨(dú)立地構(gòu)造問(wèn)題解，而整個(gè)問(wèn)題的求解不會(huì)因?yàn)槟持蝗斯の浵仧o(wú)法成功獲得解而受到影響。 具體到不同的優(yōu)化問(wèn)題而言，蟻群算法體現(xiàn)出的分布式特征就具有了更加現(xiàn)實(shí)的意義。因?yàn)樗械姆律鷥?yōu)化算法均可看做按照一定規(guī)則的問(wèn)題解空間搜索最優(yōu)解的過(guò)程，所以搜索點(diǎn)的初始選取就直接關(guān)系到算法求解結(jié)果的優(yōu)劣和算法尋優(yōu)效率。當(dāng)求解許多復(fù)雜問(wèn)題時(shí)，從一點(diǎn)出發(fā)的搜索受到局部特征的限制，可得不到所求問(wèn)題的滿意解；而基本蟻群算法則可看做是一個(gè)分布式的多智能系統(tǒng)，它在問(wèn)題空間的多點(diǎn)同時(shí)獨(dú)立地進(jìn)行解搜索，不僅使得算法具有較強(qiáng)的全局搜索能力，也增加了算法的可靠性。2.2.2 自組織基本蟻群算法的另一個(gè)重要

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

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