摘  要： 針對(duì)目前主題爬蟲采用“啟發(fā)式”搜索策略出現(xiàn)的“近視”缺點(diǎn),，提出了一種基于蟻群算法的主題爬蟲搜索策略,。該方法將蟻群算法引入到主題爬蟲的搜索策略中，并對(duì)蟻群算法中信息素的更新計(jì)算進(jìn)行了改進(jìn),，使其具有一定的自適應(yīng)性,。通過與其他搜索策略的比較實(shí)驗(yàn)，結(jié)果表明該算法能夠更好地提高爬蟲的全局搜索能力,。
關(guān)鍵詞： 主題爬蟲,；蟻群算法；搜索策略,；信息素

    主題網(wǎng)絡(luò)爬蟲是根據(jù)一定的網(wǎng)頁分析算法,，過濾與主題無關(guān)的鏈接,，保留主題相關(guān)的鏈接并將其放入待抓取的超鏈接隊(duì)列中，然后根據(jù)一定的搜索策略從隊(duì)列中選擇下一步要抓取的網(wǎng)頁鏈接,，并重復(fù)上述過程,，直到達(dá)到系統(tǒng)的某一條件時(shí)停止。所有網(wǎng)絡(luò)爬蟲抓取的網(wǎng)頁將會(huì)被系統(tǒng)存儲(chǔ),，進(jìn)行一定的分析,、過濾，并建立索引[1],。相對(duì)于通用爬蟲,，主題爬蟲搜索的內(nèi)容只限于特定主題或?qū)ｉT領(lǐng)域，因而被通用網(wǎng)絡(luò)爬蟲廣泛采用的基于廣度或深度優(yōu)先算法已不再適用,。目前,，主題網(wǎng)絡(luò)爬蟲通常采用啟發(fā)式搜索策略，每次選擇“最有價(jià)值”鏈接進(jìn)行優(yōu)先訪問,，但是這類策略容易過早陷入Web搜索空間中局部最優(yōu)子空間的陷阱,，缺乏全局性，從而導(dǎo)致整體回報(bào)率不高[2],。
    蟻群算法不僅能夠智能搜索和全局優(yōu)化,，而且還具有魯棒性、正反饋,、分布式計(jì)算,、易于與其他算法結(jié)合等特點(diǎn)。利用正反饋原理,，可以加快進(jìn)化過程,。分布式計(jì)算使該算法易于并行實(shí)現(xiàn)，個(gè)體之間不斷進(jìn)行信息交流和傳遞,，有利于找到較好的解,，不容易陷入局部最優(yōu)。易與多種啟發(fā)式算法結(jié)合,，可改善算法的性能,。穩(wěn)健性強(qiáng)，故在基本蟻群算法模型的基礎(chǔ)上進(jìn)行修改,，便可用于其他問題,。
    結(jié)合蟻群算法，本文針對(duì)主題爬蟲搜索策略上的不足,，提出了一種基于蟻群算法的主題爬蟲搜索策略,。由于對(duì)蟻群算法進(jìn)行了改進(jìn)，所以提出的算法還具有一定的自適應(yīng)性,。
1 蟻群算法模型
    蟻群算法是群集智能體現(xiàn)的一個(gè)典型例子,，該算法是意大利學(xué)者M(jìn)arco Dorigo[3]等人在1991年受螞蟻覓食行為的啟發(fā)而提出的,。
    蟻群算法借鑒和吸收了現(xiàn)實(shí)世界中蟻群的行為特征：螞蟻屬于群居昆蟲，個(gè)體行為極其簡單,，而群體行為卻很復(fù)雜,。相互協(xié)作的一群螞蟻很容易找到從蟻巢到食物源的最短路徑。此外,，螞蟻還能夠適應(yīng)環(huán)境的變化,，例如在蟻群的運(yùn)動(dòng)路線突然出現(xiàn)障礙物時(shí)，它們能夠很快地重新找到最優(yōu)路徑,。螞蟻個(gè)體之間在覓食過程中通過信息素來進(jìn)行信息傳遞,，信息素隨著時(shí)間的推移會(huì)逐漸揮發(fā)。螞蟻在覓食過程中能夠感知信息素的存在及其強(qiáng)度,，并以此來指導(dǎo)自己的運(yùn)動(dòng)方向,，傾向于朝著信息素強(qiáng)度高的方向移動(dòng)，即選擇該路徑的概率與當(dāng)時(shí)這條路徑上信息素強(qiáng)度成正比,。信息素強(qiáng)度越高的路徑，選擇它的螞蟻就越多,，則在該路徑上留下的信息素的強(qiáng)度就更大,，而強(qiáng)度大的信息素又吸引更多的螞蟻，從而形成一種正反饋,。通過這種反饋,，使得大部分螞蟻都會(huì)走這個(gè)最佳路徑。
    正反饋的副作用就是當(dāng)許多螞蟻都選中同一條路徑時(shí),，該路徑中的信息素量會(huì)迅速增大,，從而使得多只螞蟻集中到某一條路徑上，造成一種堵塞和停滯現(xiàn)象,，表現(xiàn)在使用蟻群算法解決問題時(shí)就容易導(dǎo)致早熟和局部收斂,。
2 基于蟻群算法的搜索策略
2.1 算法思想
    本文提出了一種基于蟻群算法的主題爬蟲搜索策略，其基本思想是：在Web頁面中存在超文本頁面wi和wj,，如果wi中有一個(gè)鏈接指向wj,，那么處于wi的螞蟻?zhàn)陨韺⒏鶕?jù)一定的條件決定是否從wi移動(dòng)到wj。每個(gè)鏈接序列代表了一個(gè)可能的螞蟻移動(dòng)路線,。螞蟻個(gè)體之間在移動(dòng)過程中通過信息素來進(jìn)行信息傳遞,。信息素在螞蟻爬行過程中會(huì)隨著時(shí)間的推移逐漸揮發(fā)。螞蟻在頁面之間的爬行被分為多個(gè)循環(huán)周期,，在每個(gè)周期中,，一個(gè)螞蟻在Web頁面間進(jìn)行一系列的移動(dòng)，直到探尋到目標(biāo)資源并返回到源點(diǎn)為止,。每完成一次爬行周期,，蟻群對(duì)各路線上的信息素量進(jìn)行更新,。為解決蟻群算法的“早熟”和“局部收斂”問題，本文借鑒了參考文獻(xiàn)[4]中動(dòng)態(tài)自適應(yīng)的調(diào)整信息素的思想,。
    假設(shè)V代表全體頁面集合,，E代表由鏈接構(gòu)成的路徑集合，則Web頁面（鏈接）構(gòu)成有向圖G={V,，E},。因?yàn)槲浵佋谶x擇下一個(gè)Web頁面時(shí)必須考慮其主題相關(guān)度，所以有向圖G中頁面Pk的主題相關(guān)度值可以參考PageRank算法公式,。
    為方便表述,，作如下定義[5]：


   其中c為常數(shù)。這樣,，根據(jù)解的分布情況自適應(yīng)地進(jìn)行信息素量的更新,，從而動(dòng)態(tài)地調(diào)整各路徑上的信息素量強(qiáng)度，使螞蟻既不過分集中也不過分分散,，從而避免了早熟和局部收斂,，提高全局搜索能力[5]。
2.3 算法流程
    提出的基于蟻群算法的爬蟲搜索策略執(zhí)行過程如下：

2.4 算法參數(shù)分析
    在蟻群算法的實(shí)現(xiàn)過程中,，多個(gè)參數(shù)需要初始化設(shè)定,。由蟻群算法的原理可知，不同參數(shù)的選擇能夠?qū)ο伻核惴ǖ男阅墚a(chǎn)生至關(guān)重要的影響[5],。目前對(duì)蟻群算法中參數(shù)的確定還沒有嚴(yán)格的理論基礎(chǔ),，所以以上諸式中出現(xiàn)的參數(shù)ηij、α,、β和ρ通常用試驗(yàn)方法來確定其最優(yōu)組合,。ηij表示由城市i轉(zhuǎn)移到城市j的期望程度，可根據(jù)某種啟發(fā)算法而定,，例如可以取ηij=1/dij,。α表示螞蟻在行進(jìn)過程中所積累的信息素對(duì)它選擇路徑所起的作用程度。β是一個(gè)表示信息素重要程度的參數(shù),。信息激素的保留系數(shù)為ρ(0<ρ<1),，它體現(xiàn)了信息素強(qiáng)度的持久性，而1-ρ則表示信息素的消逝程度,。
    參考文獻(xiàn)[6]通過大量的實(shí)驗(yàn)數(shù)值分析表明,，當(dāng)滿足0.01≤α≤0.3、3≤β≤6,、0.1≤ρ≤0.3時(shí),，算法總體上有較好性能，達(dá)到的最優(yōu)解與全局最優(yōu)較接近,，同時(shí),，所需的迭代次數(shù)也較少,，不易陷入局部最優(yōu)而導(dǎo)致算法停滯。
3 實(shí)驗(yàn)
3.1 實(shí)驗(yàn)說明
    為了驗(yàn)證基于蟻群算法的主題爬蟲搜索策略比傳統(tǒng)的廣度優(yōu)先算法和基于最佳優(yōu)先搜索策略具有更好的全局搜索能力和自適應(yīng)性,，本文在Nutch爬蟲的基礎(chǔ)上構(gòu)建了一個(gè)主題爬蟲,。Nutch爬蟲具有可擴(kuò)展和定制性。通過定義一個(gè)ACOCrawler插件來抓取特定主題的網(wǎng)頁[8],。實(shí)現(xiàn)以“物理教學(xué)資源”為主題,，選取了國內(nèi)三個(gè)教育網(wǎng)站為種子集(如表1所示)，算法參變量設(shè)定如表2所示,。

3.2 結(jié)果分析
    系統(tǒng)運(yùn)行12個(gè)小時(shí),，共抓取3 360 000個(gè)網(wǎng)頁及資源。為了便于比較,，分別對(duì)基于廣度優(yōu)先算法和最佳優(yōu)先搜索算法的搜索結(jié)果進(jìn)行測試,，統(tǒng)計(jì)三種搜索算法實(shí)現(xiàn)的爬蟲所搜索的關(guān)于物理教學(xué)資源的網(wǎng)頁及資源數(shù)，采用“相對(duì)回報(bào)率”來評(píng)價(jià)爬蟲的性能,。相對(duì)回報(bào)率R的計(jì)算公式為：

    通過計(jì)算,，可以得到三種算法性能比較圖，如圖1所示,。

    由圖1可以看出,，在三種搜索策略中，廣度優(yōu)先算法的性能低于其他兩種“啟發(fā)式”算法,。這兩種搜索策略在訪問了50%的頁面后，已經(jīng)找到了70%以上的相關(guān)物理資源,，這表明基于“啟發(fā)式”搜索策略具有優(yōu)越性,。
    基于蟻群算法的搜索策略性能比較顯著，除了在搜索初期其發(fā)現(xiàn)能力略低于基于最佳優(yōu)先策略的搜索算法外,，在其后的搜索中,，新算法的性能明顯高于基于最佳優(yōu)先策略的搜索算法。其原因在于,，基于蟻群算法的搜索策略采用了一種最優(yōu)選擇機(jī)制,，一旦蟻群發(fā)現(xiàn)有好的全局最優(yōu)個(gè)體，動(dòng)態(tài)地更新路徑上的信息素,，作為最優(yōu)選擇路徑,，從而避免了局部最優(yōu)，因而整體回報(bào)率較高,。
    本文針對(duì)現(xiàn)有主題爬蟲所采用搜索策略出現(xiàn)的一些問題,，將蟻群搜索模型引入主題爬蟲搜索策略。實(shí)驗(yàn)結(jié)果表明,，基于蟻群算法的搜索策略與基于廣度優(yōu)先搜索策略和基于最佳優(yōu)先搜索策略相比,，其在主題相關(guān)性上有比較明顯的優(yōu)勢(shì),。通過對(duì)蟻群算法進(jìn)行改進(jìn)，能夠動(dòng)態(tài)地調(diào)整信息素,，從而也能夠較好地解決局部最優(yōu)問題,，提高了全局搜索的能力。但由于蟻群算法本身的一些缺陷,，使得主題爬蟲在搜索效率上還有待提高,，這是下一步要做的工作。
參考文獻(xiàn)
[1] 劉金紅,，陸余良.主題網(wǎng)絡(luò)爬蟲研究綜述[J].計(jì)算機(jī)應(yīng)用研究,，2007(10)：26-29.
[2] 李學(xué)勇，田立軍,，譚義紅,，等.一種基于非貪婪策略的網(wǎng)絡(luò)蜘蛛搜索算法[J].計(jì)算機(jī)與自動(dòng)化，2004,，23(2).
[3] DORIGO M,， MANIEZZO V， COLORNI A. The ant system： optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems,， Man and Cybernetics—Part B,， 1996， 26(1)： 29-41.
[4] 李開榮,，陳宏建,，陳崚.一種動(dòng)態(tài)自適應(yīng)蟻群算法[J].計(jì)算機(jī)與自動(dòng)化，2004,，40(29)：149-152.
[5] 陶劍文.基于蟻群計(jì)算的自適應(yīng)Web檢索算法設(shè)計(jì)[J]. 計(jì)算機(jī)工程與應(yīng)用,，2007(15)：163-165.
[6] 蔣玲艷，張軍,，鐘樹鴻.蟻群算法的參數(shù)分析[J].計(jì)算機(jī)工程與應(yīng)用,，2006(13)：31-35.
[7] MENCZER F， PANT G,， SRINIVASAN N P. Topical Web crawler： evaluating adaptive algorithms[J]. ACM Transactions on Internet Technology,， 2004(4)： 378-419.
[8] 榮光，張化祥.一種DeepWeb爬蟲的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)與現(xiàn)代化,，2009(3)：32-34.