摘 要： 針對(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è)體行為極其簡(jiǎn)單，而群體行為卻很復(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)行測(cè)試，統(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.