一種基于獎勵機制的智能元搜索引擎

黃偉建，祝月紅，杜巍

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

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

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

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

1 基于多Agent的元搜索引擎系統模型

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

在該系統模型中，用戶交互Agent是用戶與系統交互的接口，負責將查詢請求發送給查詢擴展Agent;查詢擴展Agent將查詢請求轉換為各成員搜索引擎識別的指令格式，并將其發送給查詢管理Agent;查詢管理Agent將查詢任務分發給各成員搜索引擎Agent，由其對應的成員搜索引擎執行并發查詢，最后由結果整合Agent對各成員Agent返回的搜索結果進行合并、去重、排序等處理，并將最終查詢結果返回給用戶交互Agent，以統一的格式顯示給用戶。

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

2 基于獎勵機制的成員搜索引擎調度策略

2.1 基本思想

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

2.2 具體步驟

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

步驟1:創建成員搜索引擎列表并生成對應的成員Agent。查詢前首先將盡量多的獨立搜索引擎加入引擎知識庫的搜索引擎列表中，生成與之對應的成員搜索引擎Agent，并建立關聯。

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

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

步驟3:根據獎勵機制，計算各性能因子。查詢管理Agent將查詢任務同時發送給所有搜索引擎列表中的各Agent，返回查詢結果后根據其表現情況進行獎懲，并記錄在獎勵機制庫中。對成員搜索引擎Agent各性能因子的獎勵機制具體如下:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

性能因子的對于查詢的影響越大，相應的權值就越高。

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

成員搜索引擎調度策略是元搜索引擎的技術核心，通過選擇良好的成員搜索引擎調度策略可以提高元搜索引擎的系統性能。

3 基于獎勵機制的結果合成策略

結果合成策略是元搜索引擎的關鍵技術之一，結果合成策略的好壞在一定程度上決定著元搜索引擎性能的優劣?；讵剟顧C制的結果合成策略，克服了傳統合成策略在檢索結果合成排名時只考慮檢索結果與查詢主題相關度的缺陷，而是結合成員搜索引擎的重要度，將查詢結果被各成員搜索引擎命中的次數也考慮在內，即由成員Agent的爬行能力值、檢索結果與查詢主題的相關度、成員搜索引擎的查詢平均響應時間和查詢結果命中次數四個影響因素來綜合決定結果合成。

基于獎勵機制的結果合成策略的基本思想是，通過計算某一查詢結果在與其對應檢索的成員搜索引擎中的局部重要性和在所有查詢結果中命中數量的全局重要性，來綜合評價該查詢結果的整體重要性。基于獎勵機制的結果合成策略的基本步驟如下:

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

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

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

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

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

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

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

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

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

4 性能驗證

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

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

基于獎勵機制的智能元搜索引擎與傳統元搜索引擎相比，有以下獨特優勢:

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

⑵由于無效成員搜索引擎冗余信息的減少，元搜索引擎后期結果處理的負擔降低，系統查詢響應時間也隨之縮短。

⑶用定量法對成員搜索引擎的查詢性能進行量化管理，通過完善的獎勵機制發掘對查詢潛在有用的成員搜索引擎進行調度，改進了傳統成員搜索引擎調度策略的性能。

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

5 結語

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

[1]彭喜化.基于Agent的元搜索引擎結果優化研究[D].重慶:西南農業大學，2004.

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

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

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

[5]楊剛華.基于Agent的個性化信息檢索系統研究[D].大連:大連理工大學，2005.

[6]李曉瑜.Multi－Agent在網絡海量信息搜索中的應用[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]孟文杰.元搜索引擎的調度策略研究[D].青島:中國石油大學，2007.

[9]黃偉建，宋曉潔，王子軒.辦公自動化系統中動態工作流引擎的研究[J].河北工程大學學報:自然科學版，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.