賽忠良

【摘要】：齊心協(xié)力搬運(yùn)食物，這是我們心里最深刻的螞蟻行為，人類對螞蟻行為的研究發(fā)現(xiàn)，螞蟻可以在沒有任何幫助的情況下找到窩巢到食物的最短路徑，并且當(dāng)環(huán)境變化時，依舊可以順應(yīng)環(huán)境變化找到新的路徑，有人就以螞蟻的這種“群集智能”提出了蟻群算法。

眾所周知，搜索引擎的主要工作過程包括：抓取、存儲、頁面分析、索引、檢索等幾個主要過程。隨著互聯(lián)網(wǎng)的迅猛發(fā)展，對搜索引擎的性能要求越來越高，搜索引擎系統(tǒng)的體系結(jié)構(gòu)和搜索算法從根本上決定了整個系統(tǒng)的效率和搜索性能，由此可知，搜索算法在搜索引擎重要性舉足輕重，本文章首先介紹了蟻群算法的工作原理，以及蟻群算法在搜索引擎方面的應(yīng)用現(xiàn)狀和以及提出的的改進(jìn)問題。

【關(guān)鍵詞】：算法;搜索引擎;蟻群算法

引言

蟻群算法最早由意大利學(xué)者M(jìn)arco Dorigo（及其導(dǎo)師Colorni）于1911年在其博士論文

中提出，后期工作則是Marco Dorigo與其合作同事們在比利時布魯塞爾自由大學(xué)研究期間陸續(xù)展開，早期的研究成果大多是該研究團(tuán)隊(duì)在歐洲的一些小型專業(yè)研討會及其會議錄上所發(fā)表的，世界對此了解并不多，1998年十月，首屆螞蟻優(yōu)化國際研討會于比利時布魯塞爾自由大學(xué)召開，此后，幾乎每年都召開一次這樣的會議并出版回憶錄，吸引了來自世界各個國家的同行，還為蟻群算法開設(shè)了專題小組討論和研習(xí)班，蟻群算法自提出以來，以TSP為測試基準(zhǔn)，與其他一些常用啟發(fā)式方法作了一系列的比較，對若干典型的對稱性于非對稱性TSP問題（如TSPLIB中的許多實(shí)例），先后采用了模擬退火法，遺傳算法，神經(jīng)網(wǎng)絡(luò)（如彈性網(wǎng)法，自組織映射法等）。進(jìn)化規(guī)劃，遺傳退火法，插入法，禁忌搜索法，邊交換法等多種優(yōu)化算法進(jìn)行求解，除了Lin-Kernighan局部改進(jìn)法之外，蟻群算法優(yōu)于其他的所有方法蟻群算法的基本原理，毫無疑問，蟻群算法表現(xiàn)出了強(qiáng)大的優(yōu)勢性。

本文就蟻群算法的原理以及搜索引擎方面研究作出綜述，并就做出的的改進(jìn)進(jìn)行研究。

1蟻群算法的原理

螞蟻是如何找到窩巢與食物源的最短路徑的？螞蟻通過在移動中所釋放的特有分泌物-信息素來找尋窩巢與食物源的最短路徑。

1.1螞蟻的覓食原理

自然界中的螞蟻沒有視覺，既不知道向何處去尋找和獲取食物，也不知道發(fā)現(xiàn)食物后如何返回自己的巢穴，它們僅僅依賴于同類散發(fā)在周圍環(huán)境中的特殊物質(zhì)-信息素的軌跡，從而決定自己何去何從，有趣的是，盡管沒有任何經(jīng)驗(yàn)的只是，但螞蟻們還是有能力找到從其巢穴到十五元的最佳路徑，是指在該路線上放置障礙物之后，它們?nèi)阅芎芸熘匦抡业嚼m(xù)保的最佳路線。

在這里，我借助更形象化的圖示來理解這種機(jī)制，假定障礙物的周圍有兩條道路可以從螞蟻的巢穴到食物源（見圖1.1）：Nest-ABD-Food和Nest-ACD-Food，分別具有長度4和6，螞蟻在單位時間內(nèi)看可以移動一個單位長度的距離，開始時所有道路上都未曾留有任何信息素。在t=0時刻，20只螞蟻從巢穴出發(fā)移動到A，它們以相同概率選擇左側(cè)或右側(cè)道路，因此平均有10只螞蟻?zhàn)咦髠?cè)，10只螞蟻?zhàn)哂覀?cè)，在t=4時刻，第一組到達(dá)食物源的螞蟻將折回，在t=5時刻，兩組螞蟻將在D點(diǎn)相遇，此時BD上的信息素數(shù)量與CD上的相同，因?yàn)楦饔?0只螞蟻選擇了相應(yīng)的道路，從而有5只返回的螞蟻將選擇BD，而另5只將選擇CD。在t=8時刻，前5個螞蟻將返回巢穴，而AC，CD和BD上各有5個螞蟻。在t=9時刻，前5個螞蟻又回到A并且再次面對往左還是往右的選擇，這時，AB上的軌跡數(shù)為20而AC上的為15，因此將有較多的螞蟻選擇往左，從而增強(qiáng)了該路線上的信息素，隨著該過程的繼續(xù)，兩條道路上的信息素量的差距越來越大，直至絕大多數(shù)螞蟻都選擇了最短的路線。

正是由于一條道路要比另外一條短，因此在相同時間區(qū)間內(nèi)，短的路線會有更多的機(jī)會被選擇，例如，在96個時間單元中，短的路線將會被一個螞蟻?zhàn)哌^12次，而長的路線僅僅被走過8次。

圖1.1 ?螞蟻從巢穴至食物源

1.2蟻群算法的基本原理

這里，以TSP問題為例，闡述蟻群算法的基本思想和原理：

在基本的實(shí)施步驟中，用到的變量和常數(shù)有：

m=螞蟻的個數(shù)，

=邊?。╥，j）的能見度（visibility），即1/，

=邊弧（i，j）的軌跡強(qiáng)度（intensity），

按的不同取法，可形成不同類型的蟻群算法，最基本的為

=螞蟻K的轉(zhuǎn)移速率，與成正比，j是尚未訪問的節(jié)點(diǎn)，軌跡強(qiáng)度的更新方程為=+〖.這里，個參數(shù)的含義如下：

軌跡的相對重要性（）;

= 能見度的相對重要性（）;

軌跡的持久性（01）;可將1—理解為跡衰減度

Q= 體現(xiàn)螞蟻所留軌跡數(shù)量的一個常數(shù).

步驟1. nc0（nc為迭代步數(shù)或搜索次數(shù)）;各和初始化;將m個螞蟻置于n各頂點(diǎn)上;

步驟2. 將各螞蟻的初始出發(fā)點(diǎn)置于當(dāng)前解集中;對每個螞蟻k，按概率移動至下一個頂點(diǎn)j，將頂點(diǎn)j置于當(dāng)前解集;

步驟3. 計算各螞蟻的目標(biāo)函數(shù)值;記錄當(dāng)前的最好解;

步驟4. 按更新方程修改軌跡長度

步驟5. 對各邊弧（i，j），置;ncnc+1;

步驟6. 若nc<預(yù)定迭代次數(shù)且無退化行為，則轉(zhuǎn)步驟2.

步驟7. 輸出最好解.

整個算法的時間復(fù)雜度為O（nc），如果選取m≈n，則蟻群算法的時間復(fù)雜度為O（nc）.算法理論認(rèn)為，這個復(fù)雜度在計算時間上是可以接受的.

2蟻群算法與搜索引擎的研究

2.1搜索引擎的結(jié)構(gòu)

搜索引擎結(jié)構(gòu)由兩部分組成：離線（Ofltine）部分和在線部分（Online）離線部分通過網(wǎng)頁爬取器（Crawler）、網(wǎng)頁剖析器（Parser）和索引編輯器（Index Builder）組成，主要完成對網(wǎng)頁的收集、剖析、索引和重要排序功能在線部分通過用戶界N（UserInterface）、緩存（Caching）和相關(guān)性排序?yàn)橛脩舴祷厮阉鹘Y(jié)果。

2.2蟻群算法在搜索引擎中的應(yīng)用研究

螞蟻是根據(jù)自己活動時釋放的信息素以及對信息素濃度的判斷來找到最短路徑的，搜索引擎系統(tǒng)是將訪問網(wǎng)站的用戶看成是螞蟻來指引用戶進(jìn)行導(dǎo)航，建立蟻群的導(dǎo)航模型是基于用戶在網(wǎng)頁之間隨機(jī)的進(jìn)行轉(zhuǎn)移，隨后，實(shí)時的抽取用戶的導(dǎo)航行為為特征，從而抽取用戶的訪問網(wǎng)頁的具體信息。

用戶導(dǎo)航路徑：

當(dāng)用戶訪問具體的網(wǎng)站時，相關(guān)的網(wǎng)絡(luò)請求稱為用戶的導(dǎo)航路徑，換句話說就是用戶的瀏覽行為。

支持度：根據(jù)用戶的導(dǎo)航路徑，可以建議一個有向圖，支持度表示用戶沿著節(jié)點(diǎn)i到j(luò)路徑的訪問頻率，定義如下：

=/

表示沿著節(jié)點(diǎn)i到j(luò)路徑訪問的次數(shù)，從節(jié)點(diǎn)i到所有的下一節(jié)點(diǎn)有n種不同的選擇。

信息素函數(shù)：

信息素函數(shù)（t）表示用戶沿著節(jié)點(diǎn)i到j(luò)路徑的訪問傾向，定義如下：

）+，表示信息素的衰減率.

公式中表示沿節(jié)點(diǎn)i到j(luò)路徑訪問下一個網(wǎng)頁的平均時間，從節(jié)點(diǎn)i到所有的相鄰節(jié)點(diǎn)有n種不同的選擇。

公式中表示沿著節(jié)點(diǎn)i到j(luò)路徑訪問下一個網(wǎng)頁的時間，表示沿著節(jié)點(diǎn)i到j(luò)路徑的訪問次數(shù)。

用戶導(dǎo)航路徑的核心特征就是用戶在不同網(wǎng)頁間的訪問時間，在網(wǎng)頁上的訪問時間可以很好地度量用戶對該網(wǎng)頁的興趣，如果對網(wǎng)頁內(nèi)容感興趣，他可能在瀏覽該網(wǎng)頁上花費(fèi)更多的時間，如果用戶僅僅是通過網(wǎng)頁的一個鏈接到達(dá)另一個網(wǎng)頁，他可能在該網(wǎng)頁上逗留很短的時間。

偏好函數(shù)：偏好函數(shù)（t）表示用戶沿著節(jié)點(diǎn)i到j(luò)路徑訪問的偏好，偏好函數(shù)定義如下：

公式中分別表示信息素和支持度的相對重要性。

3蟻群算法的應(yīng)用改進(jìn)

3.1擴(kuò)展旅行商問題的蟻群算法

3.1.2 問題闡述

瓶頸問題問題是最早從TSP延伸出來的樣子紅擴(kuò)展性TSP，其含義與經(jīng)典的TSP類似，僅僅是目標(biāo)不同，要求巡回路線中經(jīng)過的最長距離最短，即最小化瓶頸距離，該情況體現(xiàn)了那些不追求總巡回路線最短，而只希望在巡回路線中每次從一個地點(diǎn)至另外一個地點(diǎn)的單行程盡可能短的實(shí)際應(yīng)用問題的特征。

從嚴(yán)格的數(shù)學(xué)意義上來講，瓶頸TSP可以通過一定的方法轉(zhuǎn)化為等價的經(jīng)典TSP問題，由于增加了問題的規(guī)模，因此并沒有降低問題的難度，也未能提供任何特殊的解題方法。

和經(jīng)典TSP類似，瓶頸TSP的數(shù)學(xué)模型可寫成

min Z=max

由于目標(biāo)函數(shù)值為瓶頸值，故求得的巡回路線與經(jīng)典TSP的巡回路線往往截然不同。

3.1.3 算法思想

求解瓶頸問題的蟻群算法思想和經(jīng)典TSP類似，只需要將目標(biāo)函數(shù)值轉(zhuǎn)換為瓶頸值即可，對瓶頸TSP求解采用：（1）最遠(yuǎn)插入法;（2）最近插入法;（3）最小插入法;（4）最近鄰法;（5）模擬退火法;（6）蟻群算法;（7）元胞蟻群算法。

4結(jié)束語

本文討論了蟻群算法的基本原理，以及蟻群算法在搜索引擎系統(tǒng)中的相關(guān)應(yīng)用，并對蟻群算法的一些改進(jìn)應(yīng)用進(jìn)行了研究探討。

參考文獻(xiàn)：

[1] 王艷玲，李龍澍，胡哲. ?群體智能優(yōu)化算法[J]. 計算機(jī)技術(shù)與發(fā)展. 2008（08）

[2] 王劍，李平，楊春節(jié). ?蟻群算法的理論與應(yīng)用[J]. 機(jī)電工程. 2003（05）

[3] 劉道海，方毅，黃樟燦. ?一種求解組合優(yōu)化問題的演化算法[J]. 武漢大學(xué)學(xué)報（理學(xué)版）.2002（03）

[4] 李冰巖，黃地龍，郝園. ?基于Web的搜索引擎算法的研究[J]. 電腦與電信. 2010（05）

[5] 王海鷹，魏穎. ?基于蟻群算法的多目標(biāo)網(wǎng)頁綜合評價策略[J]. 計算機(jī)工程與應(yīng)用. 2011（04）

[6] 邢立寧，陳英武，姚鋒，賀仁杰，姜江.求解雙層CARP優(yōu)化問題的知識型蟻群算法[J]. 系統(tǒng)工程理論與實(shí)踐. 2012（11）

[7] 馬良，朱剛，寧愛兵，蟻群優(yōu)化算法[J]. 科學(xué)出版社.2008（05）