解讀搜索引擎算法“蟻群算法”

解讀搜索引擎算法“蟻群算法”

蟻群算法的由來：螞蟻是地球上最常見、數(shù)量最多的昆蟲種類之一，常常成群結(jié)隊地出現(xiàn)在人類的日常生活環(huán)境中。這些昆蟲的群體生物智能特征，引起了一些學(xué)者的注意。意大利學(xué)者M(jìn).Dorigo，V.Maniezzo等人在觀察螞蟻的覓食習(xí)性時發(fā)現(xiàn)，螞蟻總能找到巢穴與食物源之間的最短路徑。經(jīng)研究發(fā)現(xiàn)，螞蟻的這種群體協(xié)作功能是通過一種遺留在其來往路徑上的叫做信息素(Pheromone)的揮發(fā)性化學(xué)物質(zhì)來進(jìn)行通信和協(xié)調(diào)的?；瘜W(xué)通信是螞蟻采取的基本信息交流方式之一，在螞蟻的生活習(xí)性中起著重要的作用。通過對螞蟻覓食行為的研究，他們發(fā)現(xiàn)，整個蟻群就是通過這種信息素進(jìn)行相互協(xié)作，形成正反饋，從而使多個路徑上的螞蟻都逐漸聚集到最短的那條路徑上。這樣，M.Dorigo等人于1991年首先提出了蟻群算法。其主要特點就是：通過正反饋、分布式協(xié)作來尋找最優(yōu)路徑。這是一種基于種群尋優(yōu)的啟發(fā)式搜索算法。它充分利用了生物蟻群能通過個體間簡單的信息傳遞，搜索從蟻巢至食物間最短路徑的集體尋優(yōu)特征，以及該過程與旅行商問題求解之間的相似性。得到了具有NP難度的旅行商問題的最優(yōu)解答。同時，該算法還被用于求解Job-Shop調(diào)度問題、二次指派問題以及多維背包問題等，顯示了其適用于組合優(yōu)化類問題求解的優(yōu)越特征。多年來世界各地研究工作者對蟻群算法進(jìn)行了精心研究和應(yīng)用開發(fā)，該算法現(xiàn)己被大量應(yīng)用于數(shù)據(jù)分析、機(jī)器人協(xié)作問題求解、電力、通信、水利、采礦、化工、建筑、交通等領(lǐng)域。蟻群算法之所以能引起相關(guān)領(lǐng)域研究者的注意，是因為這種求解模式能將問題求解的快速性、全局優(yōu)化特征以及有限時間內(nèi)答案的合理性結(jié)合起來。其中，尋優(yōu)的快速性是通過正反饋式的信息傳遞和積累來保證的。而算法的早熟性收斂又可以通過其分布式計算特征加以避免，同時，具有貪婪啟發(fā)式搜索特征的蟻群系統(tǒng)又能在搜索過程的早期找到可以接受的問題解答。這種優(yōu)越的問題分布式求解模式經(jīng)過相關(guān)領(lǐng)域研究者的關(guān)注和努力，已經(jīng)在最初的算法模型基礎(chǔ)上得到了很大的改進(jìn)和拓展。經(jīng)過一定時間，從食物源返回的螞蟻到達(dá)D點同樣也碰到障礙物，也需要進(jìn)行選擇。此時A，B兩側(cè)的信息素濃度相同，它們?nèi)匀灰话胂蜃螅话胂蛴?。但是?dāng)A側(cè)的螞蟻已經(jīng)完全繞過障礙物到達(dá)C點時，B側(cè)的螞蟻由于需走的路徑更長，還不能到達(dá)C點。如圖3所示。圖3蟻群在障礙物前經(jīng)過一段時間后的情形此時對于從蟻巢出發(fā)來到C點的螞蟻來說，由于A側(cè)的信息素濃度高，B側(cè)的信息素較低，就傾向于選擇A側(cè)的路徑。這樣的結(jié)果是A側(cè)的螞蟻越來越多，最終所有螞蟻都選擇這條較短的路徑。如圖4所示。圖4蟻群最終選擇的路徑上述過程，很顯然是由螞蟻所留下的信息素的“正反饋”過程而導(dǎo)致的。螞蟻個體就是通過這種信息的交流來達(dá)到搜索食物的目的。蟻群算法的基本思想也是從這個過程轉(zhuǎn)化而來的。蟻群算法的特點1)蟻群算法是一種自組織的算法。在系統(tǒng)論中，自組織和它組織是組織的兩個基本分類，其區(qū)別在于組織力或組織指令是來自于系統(tǒng)的內(nèi)部還是來自于系統(tǒng)的外部，來自于系統(tǒng)內(nèi)部的是自組織，來自于系統(tǒng)外部的是他組織。如果系統(tǒng)在獲得空間的、時間的或者功能結(jié)構(gòu)的過程中，沒有外界的特定干預(yù)，我們便說系統(tǒng)是自組織的。在抽象意義上講，自組織就是在沒有外界作用下使得系統(tǒng)墑增加的過程(即是系統(tǒng)從無序到有序的變化過程)。蟻群算法充分休現(xiàn)了這個過程，以螞蟻群體優(yōu)化為例子說明。當(dāng)算法開始的初期，單個的人工螞蟻無序的尋找解，算法經(jīng)過一段時間的演化，人工螞蟻間通過信息激素的作用，自發(fā)的越來越趨向于尋找到接近最優(yōu)解的一些解，這就是一個無序到有序的過程。2)蟻群算法是一種本質(zhì)上并行的算法。每只螞蟻搜索的過程彼此獨(dú)立，僅通過信息激素進(jìn)行通信。所以蟻群算法則可以看作是一個分布式的多agent系統(tǒng)，它在問題空間的多點同時開始進(jìn)行獨(dú)立的解搜索，不僅增加了算法的可靠性，也使得算法具有較強(qiáng)的全局搜索能力。3)蟻群算法是一種正反饋的算法。從真實螞蟻的覓食過程中我們不難看出，螞蟻能夠最終找到最短路徑，直接依賴于最短路徑上信息激素的堆積，而信息激素的堆積卻是一個正反饋的過程。對蟻群算法來說，初始時刻在環(huán)境中存在完全相同的信息激素，給予系統(tǒng)一個微小擾動，使得各個邊上的軌跡濃度不相同，螞蟻構(gòu)造的解就存在了優(yōu)劣，算法采用的反饋方式是在較優(yōu)的解經(jīng)過的路徑留下更多的信息激素，而更多的信息激素又吸引了更多的螞蟻，這個正反饋的過程使得初始的不同得到不斷的擴(kuò)大，同時又引導(dǎo)整個系統(tǒng)向最優(yōu)解的方向進(jìn)化。因此，正反饋是螞蟻算法的重要特征，它使得算法演化過程得以進(jìn)行。4)蟻群算法具有較強(qiáng)的魯棒性。相對于其它算法，蟻群算法對初始路線要求不高，即蟻群算法的求解結(jié)果不依賴子初始路線的選擇，而且在搜索過程中不需要進(jìn)行人工的調(diào)整。其次，蟻群算法的參數(shù)數(shù)目少，設(shè)置簡單，易于蟻群算法應(yīng)用到其它組合優(yōu)化問題的求解。蟻群算法的應(yīng)用進(jìn)展以蟻群算法為代表的群智能已成為當(dāng)今分布式人工智能研究的一個熱點，許多源于蜂群和蟻群模型設(shè)計的算法己越來越多地被應(yīng)用于企業(yè)的運(yùn)轉(zhuǎn)模式的研究。美國五角大樓正在資助關(guān)于群智能系統(tǒng)的研究工作-群體戰(zhàn)略(SwarmStrategy)，它的一個實戰(zhàn)用途是通過運(yùn)用成群的空中無人駕駛飛行器和地面車輛來轉(zhuǎn)移敵人的注意力，讓自己的軍隊在敵人后方不被察覺地安全進(jìn)行。英國電信公司和美國世界通信公司以電子螞蟻為基礎(chǔ)，對新的電信網(wǎng)絡(luò)管理方法進(jìn)行了試驗。群智能還被應(yīng)用于工廠生產(chǎn)計劃的制定和運(yùn)輸部門的后勤管理。美國太平洋西南航空公司采用了一種直接源于螞蟻行為研究成果的運(yùn)輸管理軟件，結(jié)果每年至少節(jié)約了1000萬美元的費(fèi)用開支。英國聯(lián)合利華公司己率先利用群智能技術(shù)改善其一家牙膏廠的運(yùn)轉(zhuǎn)情況。美國通用汽車公司、法國液氣公司、荷蘭公路交通部和美國一些移民事務(wù)機(jī)構(gòu)也都采用這種技術(shù)來改善其運(yùn)轉(zhuǎn)的機(jī)能。鑒于群智能廣闊的應(yīng)用前景，美國和歐盟均于近幾年開始出資資助基于群智能模擬的相關(guān)研究項目，并在一些院校開設(shè)群體智能的相關(guān)課程。國內(nèi)，國家自然科學(xué)基金”十五”期間學(xué)科交叉類優(yōu)先資助領(lǐng)域中的認(rèn)知科學(xué)及其信息處理的研究內(nèi)容中也明確列出了群智能領(lǐng)域的進(jìn)化、自適應(yīng)與現(xiàn)場認(rèn)知主題。蟻群優(yōu)化算法最初用于解決TSP問題，經(jīng)過多年的發(fā)展，已經(jīng)陸續(xù)滲透到其他領(lǐng)域中，如，圖著色問題、大規(guī)模集成電路設(shè)計、通訊網(wǎng)絡(luò)中的路由問題以及負(fù)載平衡問題、車輛調(diào)度問題等。蟻群算法在若干領(lǐng)域己獲得成功的應(yīng)用，其中最成功的是在組合優(yōu)化問題中的應(yīng)用。在網(wǎng)絡(luò)路由處理中，網(wǎng)絡(luò)的流量分布不斷變