朱 婧

(福建船政交通職業(yè)學院 信息工程系，福州 350001)

?

搜索引擎系統(tǒng)中的蟻群算法分析

朱 婧

(福建船政交通職業(yè)學院 信息工程系，福州 350001)

分析當前搜索引擎系統(tǒng)設計中應用蟻群算法的相關問題，以確保運用蟻群算法優(yōu)化設計搜索引擎系統(tǒng).結果證實，在搜索引擎系統(tǒng)中應用蟻群算法，仿真證明該算法在設計系統(tǒng)應用中具有有效性與優(yōu)越性.結論表明，在搜索引擎系統(tǒng)中，應用蟻群算法，不僅能夠優(yōu)化搜索引擎系統(tǒng)中的搜索代價,還可以發(fā)揮蟻群算法的開放性與自我動態(tài)調(diào)整性，發(fā)揮積極應用價值.

算法；搜索引擎；蟻群算法

在當前信息網(wǎng)絡化時代，人們在瀏覽網(wǎng)絡信息過程中，迫切需求一種優(yōu)化的搜索引擎系統(tǒng)，以滿足人們高效獲取網(wǎng)絡信息、大量獲取網(wǎng)絡信息的需求[1].優(yōu)化設計搜索引擎系統(tǒng)，基于蟻群算法優(yōu)化設計搜索引擎算法，將會有助于提升搜索引擎系統(tǒng)性能，產(chǎn)生積極影響.

1 蟻群算法概述

蟻群算法是由國外Marco Dorigo學者提出的，他在觀察分析螞蟻的覓食行為后受到啟發(fā)，從而設計制定的一種基于群智能的優(yōu)化算法[2].蟻群算法是繼模擬退火算法、遺傳算法以及禁忌搜索等算法后的又一種優(yōu)化算法，可以解決組合優(yōu)化問題中的隨機搜索問題，是具備啟發(fā)式的算法[3-6].不僅能應用蟻群算法實現(xiàn)智能搜索，應用蟻群算法也可對引擎系統(tǒng)進行全局優(yōu)化，提升算法在計算過程中的魯棒性，發(fā)揮分布式計算優(yōu)點[7].用蟻群算法能夠求解TSP問題，處理搜索引擎分配的問題，也可以用來解決job-shop調(diào)度的問題.雖然我國在當前關于蟻群算法方面的研究時間不長，但是基于現(xiàn)在我國相關學者的研究結果中，顯示出在求解復雜問題時應用蟻群算法發(fā)揮一定優(yōu)勢，蟻群算法在搜索引擎系統(tǒng)設計中是一種有應用價值的算法[8].

2 優(yōu)化設計搜索引擎系統(tǒng)的需求分析

在當前信息化時代，網(wǎng)上的資源信息往往具有數(shù)據(jù)量龐大、信息組織結構多樣、信息分布不均勻以及網(wǎng)絡信息動態(tài)更新速度快的特點[9]，導致搜索引擎獲得的信息呈現(xiàn)出的準確性偏低、信息錯誤等弊端，降低Internet上資源利用率，降低搜索引擎系統(tǒng)的信息檢索性能[10-11].在優(yōu)化設計搜索引擎系統(tǒng)之中，必須要確保該系統(tǒng)具備搜集信息的功能，也可以實時處理引擎搜索到的信息，并可同時為系統(tǒng)用戶提供查詢服務.基于蟻群算法，優(yōu)化設計搜索引擎系統(tǒng),提出蟻群搜索引擎算法，可以優(yōu)化引擎系統(tǒng)在實際應用中的搜索代價,可以分散局部搜索引擎的負載,提升搜索引擎系統(tǒng)應用性能.

3 設計實現(xiàn)基于蟻群算法的搜索引擎系統(tǒng)

3.1 搜索引擎系統(tǒng)結構

圖1 搜索引擎系統(tǒng)

在本次設計的搜索引擎系統(tǒng)中，系統(tǒng)工作結構主要包括搜集信息、整理信息以及接受檢索三大部分.如圖1所示.

信息搜集：主要是網(wǎng)絡爬蟲爬取網(wǎng)頁和網(wǎng)站，其過程是自動完成.理論上網(wǎng)頁的大部分超鏈接，爬蟲都能將其遍歷.

信息整理：可以將爬取搜索引擎網(wǎng)絡中的信息，根據(jù)一定規(guī)則進行篩選，并制定出索引.

檢索：該結構部分能夠根據(jù)用戶輸入到系統(tǒng)中的檢索信息，查找搜索引擎系統(tǒng)中的索引數(shù)據(jù)庫，并能夠按一定的排序算法，將檢索結果返回給用戶.

3.2 蟻群算法

廣義蟻群算法如下：

其中：ηij(t)表示啟發(fā)函數(shù)，ηij(t)=1/dij，就是代表一種期望，是螞蟻能夠從節(jié)點i轉(zhuǎn)移成j節(jié)點期望的程度；allowk(k=1,2,3,…,m)是螞蟻k對于待訪問節(jié)點的集合，在開始之時，allowk中一共有(n-1)個元素，往往包括除螞蟻出發(fā)k節(jié)點以外的所有節(jié)點，并且隨著時間的不斷推進，allowk中的元素也會不斷減少到空，所有節(jié)點也均可訪問完畢；α就是信息素中的重要程度因子，若是α的值越大，則在轉(zhuǎn)移中表示信息素發(fā)揮了越大的作用；β則是表示啟發(fā)函數(shù)的重要程度因子.

信息素更新，包括螞蟻釋放信息素，有3種模型：

模型一：“ant cycle system”

在其中Q是常數(shù)，可以表示在螞蟻循環(huán)一次后釋放信息素的總量；Lk是第k只螞蟻經(jīng)過的路徑長度.

模型二：“ant quanlity system”

模型三：“ant density system”

應用模型一來計算釋放出的信息濃度，也就是螞蟻經(jīng)過的最短路徑.

信息素揮發(fā)(evaporation)過程是信息素痕跡的濃度自動逐漸減弱的過程.揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴展.

設ρ(0<ρ<1)可以表示信息素揮發(fā)的程度，那么，可以在當所有的螞蟻完成一次循環(huán)之后，需要實時更新各個節(jié)點搜索引擎間連接路徑中信息的濃度：

3.3 基于蟻群算法設計實現(xiàn)搜索引擎算法

搜索引擎系統(tǒng)中，其不同網(wǎng)絡服務器之間彼此相互連接,構成一個全連接圖網(wǎng)絡；并且對特定用戶可以提供單個服務器的引擎檢索服務,構成服務器與用戶間的C/S架構.在搜索引擎中，對于網(wǎng)絡搜索引擎系統(tǒng)設計中，搜索網(wǎng)絡能夠應用無向圖G(V，E)來表示，V就表示網(wǎng)絡內(nèi)所有的節(jié)點集合，E則是代表網(wǎng)絡鏈路的集合.故此，可以將尋找搜索引擎系統(tǒng)中最佳資源路徑的問題，轉(zhuǎn)換成在無向圖G內(nèi)尋找滿足約束條件最佳路徑的算法.整個搜索引擎系統(tǒng)中，由數(shù)目可變的多個搜索服務器組成,系統(tǒng)中的多個服務器之間又相互是彼此的客戶端,構成P2P (Peer-to-Peer)的對等網(wǎng)絡.

圖2 搜索引擎系統(tǒng)應用算法的步驟

搜索引擎系統(tǒng)應用算法的步驟如圖2所示.首先，初始化參數(shù)，需要對與搜索引擎算法相關的參數(shù)初始化.其次，可以將各個螞蟻隨機放置在不同的出發(fā)點，對每個螞蟻k(k=1,2,…，m)，計算出轉(zhuǎn)換概率，確定其下一個搜索引擎待訪問的節(jié)點.然后，可以新信息素，計算出在各螞蟻經(jīng)過后的路徑長度Lk，并記錄在當前蟻群算法迭代中的最短路徑.并且可以在最后，如果iter

4 仿真應用分析

對于本次設計的搜索引擎系統(tǒng)，仿真分析其應用蟻群算法后的系統(tǒng)應用效果.分析其搜索引擎性能.

查準率：就是相關信息在所有查出信息中所占的比例，其計算公式如下：

其中的Relevant 表示相關信息集， Retrieved 表示返回的結果集.

在本次搜索引擎系統(tǒng)的應用仿真中，分別應用 Google搜索引擎、百度搜索引擎以及本次設計的搜索引擎系統(tǒng)，隨機查詢關于計算機領域方面的 20 個關鍵詞.并且選取每次返回的前 50 個搜索結果進行統(tǒng)計分析，對得出的 1 000 個結果統(tǒng)計其查準率.得出的查準率結果如表1所示.

表1 比較查準率結果

在本次設計的搜索引擎系統(tǒng)中，當查詢“搜索”這個關鍵字時，搜索引擎就會出現(xiàn)與計算機領域信息對應的相關網(wǎng)頁；并且該搜索引擎系統(tǒng)相對于百度以及Google引擎，不僅會提升查準率，提升搜索引擎系統(tǒng)的應用性能.在搜索引擎系統(tǒng)中應用蟻群算法，仿真證明該算法在設計系統(tǒng)應用中具有有效性與優(yōu)越性，發(fā)揮應用優(yōu)勢.

5 結論

綜上所述，在搜索引擎系統(tǒng)中應用蟻群算法，優(yōu)化設計搜索引擎系統(tǒng)，實現(xiàn)基于蟻群算法的搜索引擎算法.該算法發(fā)揮積極應用優(yōu)勢，提升搜索引擎系統(tǒng)應用性能，值得在實踐中推廣應用.

[1] 王海鷹,魏穎.基于蟻群算法的多目標網(wǎng)頁綜合評價策略[J].計算機工程與應用,2011,47(4):223-225.

[2] 劉晉佩.融合蟻群算法的用戶瀏覽路徑推薦系統(tǒng)研究[D].廈門：廈門大學,2014.

[3] 崔曉艷,霍中剛,辛中華，等.應用理性優(yōu)化蟻群算法提高激光三維復制的重現(xiàn)度[J].光譜學與光譜分析,2013,33(7):1873-1876.

[4] 何小鋒,馬良.帶時間窗車輛路徑問題的量子蟻群算法[J].系統(tǒng)工程理論與實踐,2013,33(5):1255-1261.

[5] 李積英,黨建武.基于量子空間的蟻群算法及應用[J].系統(tǒng)工程與電子技術,2013,35(10):2229-2232.

[6] 曹慶奎,趙斐.基于遺傳蟻群算法的港口集卡路徑優(yōu)化[J].系統(tǒng)工程理論與實踐,2013,33(7):1820-1828.

[7] 陳英武,姚鋒,李菊芳，等.求解多星任務規(guī)劃問題的演化學習型蟻群算法[J].系統(tǒng)工程理論與實踐,2013,33(3):791-801.

[8] 邢立寧,陳英武,姚鋒，等.求解雙層CARP優(yōu)化問題的知識型蟻群算法[J].系統(tǒng)工程理論與實踐,2012,32(11):2540-2549.

[9] 魯強,周新.基于在線檢測動態(tài)一維下料問題的GPU并行蟻群算法[J].儀器儀表學報,2015,36(8):1774-1782.

[10]郭浩,邱滌珊,伍國華，等.基于改進蟻群算法的敏捷成像衛(wèi)星任務調(diào)度方法[J].系統(tǒng)工程理論與實踐,2012,32(11):2533-2539.

[11]李冰巖,黃地龍,郝園，等.基于Web的搜索引擎算法的研究[J].電腦與電信,2010(5):29-31.

[責任編輯 王新奇]

Analysis of Ant Colony Algorithm in Search Engine System

ZHU Jing

(Department of Information Engineering, Fujian Chuanzheng Communications College, Fuzhou 350001, China)

In this paper, the related problems of application of ant colony algorithm in the current search engine system is analyzed to ensure that the use of ant colony algorithm to optimize the design of search engine system. The results show that the ant colony algorithm is used in the search engine system, and the simulation results show that the algorithm is effective and superior to the design system. The results show that ant colony algorithm can be applied in the search engine system, it can not only optimize the search cost in the search engine system, but also play the openness and self dynamic adjustment of the ant colony algorithm, and play a positive application value.

algorithm; search engine; ant colony algorithm

1008-5564(2016)04-0044-04

2016-02-18

朱 婧(1981—)，女，江西南昌人，福建船政交通職業(yè)學院信息工程系講師，主要從事計算機網(wǎng)絡技術研究.

TP391.3

A