黃偉建，祝月紅，杜巍

(河北工程大學(xué)信息與電氣工程學(xué)院，河北邯鄲056038)

在網(wǎng)絡(luò)信息量呈指數(shù)增長的信息時代，任何一個獨立搜索引擎的數(shù)據(jù)庫容量都不足整個網(wǎng)絡(luò)信息量的三分之一。由于信息覆蓋面的限制，傳統(tǒng)搜索引擎無法很好滿足用戶對查全率的要求。元搜索引擎的出現(xiàn)在一定程度上解決了這個問題。元搜索引擎將用戶的查詢請求發(fā)送到多個獨立搜索引擎上同時進行檢索，最后將查詢結(jié)果統(tǒng)一整理后顯示給用戶[1]。其工作原理如圖 1所示。

由于元搜索引擎的獨特優(yōu)勢，人們對元搜索引擎的研究十分活躍。目前，國外主要的元搜索引擎有 Dogpile、Mamma、Profusion、Inquick 等，國內(nèi)主要有萬緯、MetaFisher等比較典型的中文元搜索引擎。近幾年，隨著元搜索引擎技術(shù)的深入研究，相繼出現(xiàn)了一些新的元搜索引擎模型，比如鐘智等[2]設(shè)計了一種智能化提供個性化服務(wù)的元搜索引擎方案，將系統(tǒng)分為用戶接口模塊、信息檢索模塊和結(jié)果處理模塊。崔志明等[3]提出了一種基于Ontology的個性化元搜索引擎系統(tǒng)模型，全面描述用戶個性化處理過程。

現(xiàn)有的元搜索引擎系統(tǒng)通常將查詢請求發(fā)送到全部成員搜索引擎進行檢索，并對全部檢索結(jié)果整合處理。缺陷在于不僅系統(tǒng)的查詢響應(yīng)時間變長，而且在后期結(jié)果去重、排序時面臨巨大負載。此外，雖然對成員搜索引擎調(diào)度策略的研究有很多，但都缺乏對成員搜索引擎性能的具體評價，或評價機制很粗略，不易理解。鑒于此，本文引入Agent技術(shù)，提出一種基于獎勵機制的智能元搜索引擎系統(tǒng)模型，并為該模型建立完善的獎勵機制，通過獎勵機制對成員引擎Agent的查詢情況進行獎懲，選擇表現(xiàn)性能最佳的、對新查詢潛在有用的若干搜索引擎進行查詢調(diào)度和結(jié)果合成。

1 基于多Agent的元搜索引擎系統(tǒng)模型

智能搜索引擎是指結(jié)合了人工智能技術(shù)的新一代搜索引擎。Agent融合了人工智能(AI)技術(shù)，是目前個性化主動服務(wù)研究中的熱點和前沿，被美國麻省理工學(xué)院(MIT)媒體實驗室視為“未來的搜索引擎”[4]。本文設(shè)計了一個多 Agent協(xié)作的元搜索引擎系統(tǒng)模型，以Agent為基本單位，讓多個并行工作的搜索引擎代理按照用戶的檢索要求啟動合適的成員引擎進行檢索。構(gòu)建的系統(tǒng)模型如圖2所示。

在該系統(tǒng)模型中，用戶交互Agent是用戶與系統(tǒng)交互的接口，負責(zé)將查詢請求發(fā)送給查詢擴展Agent;查詢擴展Agent將查詢請求轉(zhuǎn)換為各成員搜索引擎識別的指令格式，并將其發(fā)送給查詢管理Agent;查詢管理Agent將查詢?nèi)蝿?wù)分發(fā)給各成員搜索引擎Agent，由其對應(yīng)的成員搜索引擎執(zhí)行并發(fā)查詢，最后由結(jié)果整合Agent對各成員Agent返回的搜索結(jié)果進行合并、去重、排序等處理，并將最終查詢結(jié)果返回給用戶交互Agent，以統(tǒng)一的格式顯示給用戶。

其中，查詢管理Agent是系統(tǒng)各Agent通信的核心，負責(zé)各Agent生命周期的管理和消息傳遞[5]。成員引擎知識庫存放了供調(diào)度的獨立搜索引擎信息，用戶可根據(jù)需要在引擎知識列表中添加、刪除、修改被調(diào)度的成員搜索引擎信息。獎勵機制庫對成員搜索引擎的檢索性能進行量化評價，計算其對于指定查詢的重要度，并將檢索性能最優(yōu)的若干成員搜索引擎推薦給查詢管理Agent，供查詢調(diào)度。

2 基于獎勵機制的成員搜索引擎調(diào)度策略

2.1 基本思想

成員搜索引擎調(diào)度技術(shù)通常是將查詢請求發(fā)往所有成員搜索引擎進行并發(fā)查詢，盡管信息覆蓋面廣，但查全率高所帶來的代價也是巨大的。研究表明，元搜索引擎的查詢響應(yīng)時間跟成員搜索引擎的個數(shù)是呈正相關(guān)的[6]。成員搜索引擎的個數(shù)越多，查詢結(jié)果就越多，必然導(dǎo)致結(jié)果顯示代理在結(jié)果整合時需要較長處理時間。為此，本文提出一種新的基于獎勵機制的成員搜索引擎調(diào)度策略。該策略的基本思想是，通過輸入查詢，發(fā)現(xiàn)對新查詢潛在有用的成員搜索引擎，通過計算各成員搜索引擎對于查詢的重要度，將重要度排名靠前的幾個成員搜索引擎優(yōu)先調(diào)度使用，并可通過多次查詢，實時、動態(tài)調(diào)整調(diào)度的成員搜索引擎，使得每次查詢都選擇檢索性能最佳的成員搜索引擎、以最優(yōu)的方式完成檢索。

2.2 具體步驟

基于獎勵機制的成員搜索引擎調(diào)度策略的具體步驟如下:

步驟1:創(chuàng)建成員搜索引擎列表并生成對應(yīng)的成員Agent。查詢前首先將盡量多的獨立搜索引擎加入引擎知識庫的搜索引擎列表中，生成與之對應(yīng)的成員搜索引擎Agent，并建立關(guān)聯(lián)。

步驟2:初始化各Agent及其成員搜索引擎A-gent的重要度。成員搜索引擎的重要度主要受三個性能因子影響:成員Agent的能力值、檢索文檔與查詢主題的相關(guān)度以及成員搜索引擎查詢的平均響應(yīng)時間。各成員搜索引擎Agent的信息在成員引擎知識庫中進行注冊，初始化各成員搜索引擎Agent的重要度，并為其分配相同的初始值。

這里，定義 C={C1，C2，C3，…，Cn，為成員搜索引擎Agent的集合(n為成員搜索引擎Agent的個數(shù))，用一個三元組表示第i個成員搜索引擎的重要度 Weight(Ci)，即 Weight(Ci)={Capability(Ci)，Relevance(Ci)，Response－Time(Ci)}，其中Capability(Ci)表示成員Agent Ci的能力值，Relevance(Ci)表示成員Agent Ci的檢索文檔與查詢主題的相關(guān)度，Response－time(Ci)表示成員Agent Ci查詢的平均響應(yīng)時間。在初次查詢開始之前，所有成員Agent的重要度參數(shù)相同。

步驟3:根據(jù)獎勵機制，計算各性能因子。查詢管理Agent將查詢?nèi)蝿?wù)同時發(fā)送給所有搜索引擎列表中的各Agent，返回查詢結(jié)果后根據(jù)其表現(xiàn)情況進行獎懲，并記錄在獎勵機制庫中。對成員搜索引擎Agent各性能因子的獎勵機制具體如下:

1)成員Agent的能力值Capability。每個成員Agent爬行前，查詢管理Agent會為其分配一定的爬行時間，設(shè)tc為成員Agent已用的爬行時間，tm為系統(tǒng)分配的總時間，t為成員Agent剩余時間與系統(tǒng)分配總時間的比值，即t=(tm－tc)/tm。查詢管理Agent還會為成員Agent分配用于存儲待爬鏈接的最大閾值(一般用可存儲鏈接的個數(shù)表示)，設(shè)sl為待爬隊列中的鏈接個數(shù)，sm為閾值，s為剩余空間與最大閾值的比值，即s=(sm－s1)/sm。那么，根據(jù)t和s，則某成員Agent Ci的能力值定義[8]如式 1:

能力值由t和s共同確定，系數(shù)決定了t和s對能力值的重要度，其中 λ∈[0，1]。CAPABILITY(Ci)的值越大，說明該成員Agent Ci的能力越高。如果某成員Agent沒有剩余空間(即t=0)或無剩余存儲空間(即s≤0)，也就是當(dāng)t×≤0時，說明該成員Agent已沒有繼續(xù)執(zhí)行爬行任務(wù)的能力。

2)檢索文檔與查詢主題的相關(guān)度Relevance。假設(shè)用DOC=(D1，D2，Dk，…，Dm)表示某成員 A-gent檢索到的文檔集合，該集合按網(wǎng)頁文檔下載的時刻順次排列，Dm為最后一篇下載的文檔。利用向量空間模型，文檔Dk可表達成Dk=(dk1)，dk2，…，dki，dkn)的形式，dki表示向量 Dk的第 i維。元搜索引擎的查詢主題可表示為KW=(kw1，kw2，…，kwi，kwn)的形式，kwi表示向量 KW 的第 i維。那么在第j次查詢中，成員Agent的檢索文檔與查詢主題之間的相關(guān)度為

根據(jù)該成員Agent Ci近n次的執(zhí)行情況設(shè)置一個閾值Rel(Ci)，作為衡量標準。閾值的計算方法為

然后比較relevance(KW，Dk)i和Rel(Ci)的大小并觀察relevance(KW，Dk)的變化情況。設(shè) P(relevancei)為某成員Agent第j次查詢時檢索文檔與查詢主題相關(guān)度的獎懲值，獎懲函數(shù)如下:

①若 relevance(KW，Dk)j≥Rel(Ci)，說明成員Agent Ci的任務(wù)執(zhí)行情況較好，給予獎勵。獎勵值為:

②若 relevance(KW，Dk)j＜Rel(Ci)，說明成員Agent Ci的執(zhí)行情況差，給與懲罰。懲罰值為:

③若relevance(KW，Dk)整體走勢由低變高，超過了Rel(Ci)，說明該成員Agent Ci有較好的前景，可以予以獎勵。獎勵值為:P(relevancei)=1;

④若relevance(KW，Dk)整體走勢由高變低，低于了Rel(Ci)，說明該成員Agent Ci前景較差，給予懲罰。懲罰值為:P(relevancei)=－1。

設(shè)用P(relevance)0表示開始查詢之前，檢索文檔與查詢主題的相關(guān)度重要性的初始化值。那么，第i個成員Agent的檢索文檔與查詢主題的相關(guān)度的重要性為:

3)查詢響應(yīng)時間Response－Time。假設(shè)用tr表示某成員Agent的近五次查詢的平均響應(yīng)時間，th表示響應(yīng)時間的閾值(默認值為15 s[9])，to表示可以被接受的最大響應(yīng)時間(默認值為45 s)，PRT(Ci)表示成員Agent Ci平均響應(yīng)時間的重要性。

①若某成員Agent Ci的平均響應(yīng)時間大于閾值，則對該成員Agent Ci進行懲罰，將其重要性減少:

②若某成員Agent Ci的平均響應(yīng)時間小于閾值，則對該成員Agent Ci進行獎勵，將其重要性增加:

③若成員Agent Ci的平均響應(yīng)時間恰好等于閾值，則不予懲罰和獎勵，即ΔPRT(Ci)=0。

設(shè)用PRT(Ci)0代表平均響應(yīng)時間的初始化值，初始時各個成員Agent平均響應(yīng)時間的重要性相同。因此，成員Agent Ci的平均響應(yīng)時間的重要性可表示為:

步驟4:計算各成員搜索引擎Agent的重要度。得到成員搜索引擎Agent各性能因子的評價值后，再加權(quán)綜合評價即可得到成員Agent Ci的重要度，計算公式為:

式中:α－性能因子PRel(Ci)的權(quán)值;β－性能因子Capability(Ci)的權(quán)值;γ－性能因子PRT(Ci)的權(quán)值。

性能因子的對于查詢的影響越大，相應(yīng)的權(quán)值就越高。

步驟5:根據(jù)重要度排名，選擇檢索性能最佳的若干(具體數(shù)目可根據(jù)個人需求設(shè)定)成員搜索引擎Agent進行查詢調(diào)度。

成員搜索引擎調(diào)度策略是元搜索引擎的技術(shù)核心，通過選擇良好的成員搜索引擎調(diào)度策略可以提高元搜索引擎的系統(tǒng)性能。

3 基于獎勵機制的結(jié)果合成策略

結(jié)果合成策略是元搜索引擎的關(guān)鍵技術(shù)之一，結(jié)果合成策略的好壞在一定程度上決定著元搜索引擎性能的優(yōu)劣。基于獎勵機制的結(jié)果合成策略，克服了傳統(tǒng)合成策略在檢索結(jié)果合成排名時只考慮檢索結(jié)果與查詢主題相關(guān)度的缺陷，而是結(jié)合成員搜索引擎的重要度，將查詢結(jié)果被各成員搜索引擎命中的次數(shù)也考慮在內(nèi)，即由成員Agent的爬行能力值、檢索結(jié)果與查詢主題的相關(guān)度、成員搜索引擎的查詢平均響應(yīng)時間和查詢結(jié)果命中次數(shù)四個影響因素來綜合決定結(jié)果合成。

基于獎勵機制的結(jié)果合成策略的基本思想是，通過計算某一查詢結(jié)果在與其對應(yīng)檢索的成員搜索引擎中的局部重要性和在所有查詢結(jié)果中命中數(shù)量的全局重要性，來綜合評價該查詢結(jié)果的整體重要性?；讵剟顧C制的結(jié)果合成策略的基本步驟如下:

步驟1:計算查詢結(jié)果在成員搜索引擎中的局部重要性等級值WeightRank(Itemi)

首先按照6式計算成員搜索引擎對于查詢的重要度Weight(Ci)，并計算成員搜索引擎的重要度等級值WeightRank(Ci)為:

由于成員搜索引擎按其重要度降序排列，優(yōu)先選擇排名靠前的、檢索性能最佳的若干成員搜索引擎進行調(diào)度，那么該搜索引擎的檢索結(jié)果與查詢主題的相關(guān)度越大。可認為查詢結(jié)果在成員搜索引擎中的重要性等級值與該成員搜索引擎的重要性等級值呈正相關(guān)，即存在函數(shù)映射:

且WeightRank(Itemi)∞WeightRank(Ci)(7)

步驟2:計算查詢結(jié)果命中數(shù)量的全局重要性等級值VoteRank(Itemi)

在元搜索引擎中，由于不同搜索引擎可能使用相同的索引數(shù)據(jù)庫，有時多個搜索引擎可能會出現(xiàn)相同的搜索結(jié)果。如果某個搜索結(jié)果Itemj被成員搜索引擎命中的次數(shù)越多，其符合查詢主題的概率就越大。因此命中次數(shù)多的搜索結(jié)果去重后可優(yōu)先顯示給用戶。設(shè)搜索結(jié)果用集合Result={(Agent(Ci)，Itemj)|1≤i≤n，1≤j≤m，且n∈N+，m∈N+}表示，搜索結(jié)果總數(shù)為ResultNum=，成員搜索引擎 Agent(Ci)對某條搜索結(jié)果Itemj命中的次數(shù)為Vote-Num(Agent(Ci)，Itemj)，計算其命中次數(shù)等級值VoteRank(Itemj)，計算公式為:

步驟3:計算查詢結(jié)果最終等級值Rank(Itemi)

用λ和φ為影響因子系數(shù)。則由式7和式8，可推導(dǎo)出查詢結(jié)果 Itemj的最終等級值 Rank(Itemj)為:

式9 中:λ∈(0，1)，φ∈(0，1)，且 λ +φ =1 。

4 性能驗證

為驗證基于獎勵機制的智能元搜索引擎系統(tǒng)的性能和可行性，將本系統(tǒng)模型在JADE平臺上實現(xiàn)仿真和模擬，并與元搜索引擎萬緯的查全率、查準率和查詢響應(yīng)時間進行對比。由于萬緯可以調(diào)用百度、搜狐、中文Google、中文雅虎、新浪GB、天網(wǎng)等6個中文搜索引擎，以及 Google、Yahoo、Hot-Bot等3個英文搜索引擎，因此在本系統(tǒng)的成員引擎知識庫中，通過搜索引擎的API接口函數(shù)添加相同的9個中英文搜索引擎(沒有提供API接口函數(shù)的搜索引擎可直接使用其檢索結(jié)果)，并生成相應(yīng)的成員搜索引擎Agent。然后隨機采取20個中英文關(guān)鍵詞在本系統(tǒng)模型中搜索，按照獎勵機制對各成員搜索引擎Agent的重要度計算，經(jīng)統(tǒng)計分析，得出重要度排名前4位的成員搜索引擎為:Google、百度、搜狐、Yahoo，用以供本系統(tǒng)模型查詢調(diào)度。在20次隨機查詢中，本系統(tǒng)與萬緯的查全率、查準率和查詢響應(yīng)時間情況的對比見圖3。

通過圖2可以看出，本系統(tǒng)采取獎勵機制選擇的查詢性能最優(yōu)的四個獨立搜索引擎，與萬緯同時調(diào)用9個獨立搜索引擎檢索對比，查全率幾乎無太大影響，查準率比萬緯平均提高了11.6%，查詢響應(yīng)時間平均縮短了2.3 s。

基于獎勵機制的智能元搜索引擎與傳統(tǒng)元搜索引擎相比，有以下獨特優(yōu)勢:

⑴每次查詢都選擇檢索性能最佳的成員搜索引擎進行調(diào)度，在保證查全率的基礎(chǔ)上，避免了無效成員搜索引擎檢索返回的大量重復(fù)信息，在一定程度上提高了查準率。

⑵由于無效成員搜索引擎冗余信息的減少，元搜索引擎后期結(jié)果處理的負擔(dān)降低，系統(tǒng)查詢響應(yīng)時間也隨之縮短。

⑶用定量法對成員搜索引擎的查詢性能進行量化管理，通過完善的獎勵機制發(fā)掘?qū)Σ樵儩撛谟杏玫某蓡T搜索引擎進行調(diào)度，改進了傳統(tǒng)成員搜索引擎調(diào)度策略的性能。

⑷將Agent技術(shù)與元搜索引擎結(jié)合，使系統(tǒng)更具靈活性和可擴展性。成員搜索引擎Agent建立后，可在成員搜索引擎知識庫列表中按個人需求增刪、修改對應(yīng)的成員搜索引擎，滿足不同用戶的個性化需求。

5 結(jié)語

隨著信息量的日益擴增，搜索引擎技術(shù)的發(fā)展稱為人們備受關(guān)注的熱點問題之一。本文結(jié)合前沿的Agent技術(shù)，基于獎勵機制的智能元搜索引擎通過完善的獎勵機制對成員搜索引擎進行調(diào)度，并根據(jù)獎勵機制對查詢結(jié)果進行歸并，在提高查準率、縮短查詢時間、減輕元搜索引擎后期的結(jié)果處理負擔(dān)方面，都在一定程度上有所提高。系統(tǒng)模型中各影響因子系數(shù)的判定以及一些具體的實現(xiàn)技術(shù)，還需要進一步研究。

[1]彭喜化.基于Agent的元搜索引擎結(jié)果優(yōu)化研究[D].重慶:西南農(nóng)業(yè)大學(xué)，2004.

[2]鐘 智，黃發(fā)良.基于個性化服務(wù)的元搜索引擎模型[J].河北理工學(xué)院學(xué)報，2005(01):73 －75.

[3]黃國景，崔志明.基于Ontology的個性化元搜索引擎研究[J].微電子學(xué)與計算機，2004，21(12):100－103.

[4]王小朋.基于代理的元搜索引擎的研究[D].遼寧:遼寧工程技術(shù)大學(xué)，2005.

[5]楊剛?cè)A.基于Agent的個性化信息檢索系統(tǒng)研究[D].大連:大連理工大學(xué)，2005.

[6]李曉瑜.Multi－Agent在網(wǎng)絡(luò)海量信息搜索中的應(yīng)用[J].科技信息，2009(14):92.

[7]ASHRI R，RAMCHURN S D，SABATER J，et al.Trust evaluation through relationship analysis[C]//Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems.Utrecht，The Netherlands:AAMAS＇05，2005:1005 －1011.

[8]孟文杰.元搜索引擎的調(diào)度策略研究[D].青島:中國石油大學(xué)，2007.

[9]黃偉建，宋曉潔，王子軒.辦公自動化系統(tǒng)中動態(tài)工作流引擎的研究[J].河北工程大學(xué)學(xué)報:自然科學(xué)版，2011，28(4):45－48.

[10]DREILLINGER D，HOWE A E.Experiences with selecting search engines using meta search[J].ACM TOIS，2007，15(3):195 －222.