黃偉建,祝月紅,杜巍
(河北工程大學(xué)信息與電氣工程學(xué)院,河北邯鄲056038)
在網(wǎng)絡(luò)信息量呈指數(shù)增長(zhǎng)的信息時(shí)代,任何一個(gè)獨(dú)立搜索引擎的數(shù)據(jù)庫(kù)容量都不足整個(gè)網(wǎng)絡(luò)信息量的三分之一。由于信息覆蓋面的限制,傳統(tǒng)搜索引擎無(wú)法很好滿足用戶對(duì)查全率的要求。元搜索引擎的出現(xiàn)在一定程度上解決了這個(gè)問題。元搜索引擎將用戶的查詢請(qǐng)求發(fā)送到多個(gè)獨(dú)立搜索引擎上同時(shí)進(jìn)行檢索,最后將查詢結(jié)果統(tǒng)一整理后顯示給用戶[1]。其工作原理如圖 1所示。
由于元搜索引擎的獨(dú)特優(yōu)勢(shì),人們對(duì)元搜索引擎的研究十分活躍。目前,國(guó)外主要的元搜索引擎有 Dogpile、Mamma、Profusion、Inquick 等,國(guó)內(nèi)主要有萬(wàn)緯、MetaFisher等比較典型的中文元搜索引擎。近幾年,隨著元搜索引擎技術(shù)的深入研究,相繼出現(xiàn)了一些新的元搜索引擎模型,比如鐘智等[2]設(shè)計(jì)了一種智能化提供個(gè)性化服務(wù)的元搜索引擎方案,將系統(tǒng)分為用戶接口模塊、信息檢索模塊和結(jié)果處理模塊。崔志明等[3]提出了一種基于Ontology的個(gè)性化元搜索引擎系統(tǒng)模型,全面描述用戶個(gè)性化處理過程。
現(xiàn)有的元搜索引擎系統(tǒng)通常將查詢請(qǐng)求發(fā)送到全部成員搜索引擎進(jìn)行檢索,并對(duì)全部檢索結(jié)果整合處理。缺陷在于不僅系統(tǒng)的查詢響應(yīng)時(shí)間變長(zhǎng),而且在后期結(jié)果去重、排序時(shí)面臨巨大負(fù)載。此外,雖然對(duì)成員搜索引擎調(diào)度策略的研究有很多,但都缺乏對(duì)成員搜索引擎性能的具體評(píng)價(jià),或評(píng)價(jià)機(jī)制很粗略,不易理解。鑒于此,本文引入Agent技術(shù),提出一種基于獎(jiǎng)勵(lì)機(jī)制的智能元搜索引擎系統(tǒng)模型,并為該模型建立完善的獎(jiǎng)勵(lì)機(jī)制,通過獎(jiǎng)勵(lì)機(jī)制對(duì)成員引擎Agent的查詢情況進(jìn)行獎(jiǎng)懲,選擇表現(xiàn)性能最佳的、對(duì)新查詢潛在有用的若干搜索引擎進(jìn)行查詢調(diào)度和結(jié)果合成。
智能搜索引擎是指結(jié)合了人工智能技術(shù)的新一代搜索引擎。Agent融合了人工智能(AI)技術(shù),是目前個(gè)性化主動(dòng)服務(wù)研究中的熱點(diǎn)和前沿,被美國(guó)麻省理工學(xué)院(MIT)媒體實(shí)驗(yàn)室視為“未來(lái)的搜索引擎”[4]。本文設(shè)計(jì)了一個(gè)多 Agent協(xié)作的元搜索引擎系統(tǒng)模型,以Agent為基本單位,讓多個(gè)并行工作的搜索引擎代理按照用戶的檢索要求啟動(dòng)合適的成員引擎進(jìn)行檢索。構(gòu)建的系統(tǒng)模型如圖2所示。
在該系統(tǒng)模型中,用戶交互Agent是用戶與系統(tǒng)交互的接口,負(fù)責(zé)將查詢請(qǐng)求發(fā)送給查詢擴(kuò)展Agent;查詢擴(kuò)展Agent將查詢請(qǐng)求轉(zhuǎn)換為各成員搜索引擎識(shí)別的指令格式,并將其發(fā)送給查詢管理Agent;查詢管理Agent將查詢?nèi)蝿?wù)分發(fā)給各成員搜索引擎Agent,由其對(duì)應(yīng)的成員搜索引擎執(zhí)行并發(fā)查詢,最后由結(jié)果整合Agent對(duì)各成員Agent返回的搜索結(jié)果進(jìn)行合并、去重、排序等處理,并將最終查詢結(jié)果返回給用戶交互Agent,以統(tǒng)一的格式顯示給用戶。
其中,查詢管理Agent是系統(tǒng)各Agent通信的核心,負(fù)責(zé)各Agent生命周期的管理和消息傳遞[5]。成員引擎知識(shí)庫(kù)存放了供調(diào)度的獨(dú)立搜索引擎信息,用戶可根據(jù)需要在引擎知識(shí)列表中添加、刪除、修改被調(diào)度的成員搜索引擎信息。獎(jiǎng)勵(lì)機(jī)制庫(kù)對(duì)成員搜索引擎的檢索性能進(jìn)行量化評(píng)價(jià),計(jì)算其對(duì)于指定查詢的重要度,并將檢索性能最優(yōu)的若干成員搜索引擎推薦給查詢管理Agent,供查詢調(diào)度。
成員搜索引擎調(diào)度技術(shù)通常是將查詢請(qǐng)求發(fā)往所有成員搜索引擎進(jìn)行并發(fā)查詢,盡管信息覆蓋面廣,但查全率高所帶來(lái)的代價(jià)也是巨大的。研究表明,元搜索引擎的查詢響應(yīng)時(shí)間跟成員搜索引擎的個(gè)數(shù)是呈正相關(guān)的[6]。成員搜索引擎的個(gè)數(shù)越多,查詢結(jié)果就越多,必然導(dǎo)致結(jié)果顯示代理在結(jié)果整合時(shí)需要較長(zhǎng)處理時(shí)間。為此,本文提出一種新的基于獎(jiǎng)勵(lì)機(jī)制的成員搜索引擎調(diào)度策略。該策略的基本思想是,通過輸入查詢,發(fā)現(xiàn)對(duì)新查詢潛在有用的成員搜索引擎,通過計(jì)算各成員搜索引擎對(duì)于查詢的重要度,將重要度排名靠前的幾個(gè)成員搜索引擎優(yōu)先調(diào)度使用,并可通過多次查詢,實(shí)時(shí)、動(dòng)態(tài)調(diào)整調(diào)度的成員搜索引擎,使得每次查詢都選擇檢索性能最佳的成員搜索引擎、以最優(yōu)的方式完成檢索。
基于獎(jiǎng)勵(lì)機(jī)制的成員搜索引擎調(diào)度策略的具體步驟如下:
步驟1:創(chuàng)建成員搜索引擎列表并生成對(duì)應(yīng)的成員Agent。查詢前首先將盡量多的獨(dú)立搜索引擎加入引擎知識(shí)庫(kù)的搜索引擎列表中,生成與之對(duì)應(yīng)的成員搜索引擎Agent,并建立關(guān)聯(lián)。
步驟2:初始化各Agent及其成員搜索引擎A-gent的重要度。成員搜索引擎的重要度主要受三個(gè)性能因子影響:成員Agent的能力值、檢索文檔與查詢主題的相關(guān)度以及成員搜索引擎查詢的平均響應(yīng)時(shí)間。各成員搜索引擎Agent的信息在成員引擎知識(shí)庫(kù)中進(jìn)行注冊(cè),初始化各成員搜索引擎Agent的重要度,并為其分配相同的初始值。
這里,定義 C={C1,C2,C3,…,Cn,為成員搜索引擎Agent的集合(n為成員搜索引擎Agent的個(gè)數(shù)),用一個(gè)三元組表示第i個(gè)成員搜索引擎的重要度 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)時(shí)間。在初次查詢開始之前,所有成員Agent的重要度參數(shù)相同。
步驟3:根據(jù)獎(jiǎng)勵(lì)機(jī)制,計(jì)算各性能因子。查詢管理Agent將查詢?nèi)蝿?wù)同時(shí)發(fā)送給所有搜索引擎列表中的各Agent,返回查詢結(jié)果后根據(jù)其表現(xiàn)情況進(jìn)行獎(jiǎng)懲,并記錄在獎(jiǎng)勵(lì)機(jī)制庫(kù)中。對(duì)成員搜索引擎Agent各性能因子的獎(jiǎng)勵(lì)機(jī)制具體如下:
1)成員Agent的能力值Capability。每個(gè)成員Agent爬行前,查詢管理Agent會(huì)為其分配一定的爬行時(shí)間,設(shè)tc為成員Agent已用的爬行時(shí)間,tm為系統(tǒng)分配的總時(shí)間,t為成員Agent剩余時(shí)間與系統(tǒng)分配總時(shí)間的比值,即t=(tm-tc)/tm。查詢管理Agent還會(huì)為成員Agent分配用于存儲(chǔ)待爬鏈接的最大閾值(一般用可存儲(chǔ)鏈接的個(gè)數(shù)表示),設(shè)sl為待爬隊(duì)列中的鏈接個(gè)數(shù),sm為閾值,s為剩余空間與最大閾值的比值,即s=(sm-s1)/sm。那么,根據(jù)t和s,則某成員Agent Ci的能力值定義[8]如式 1:
能力值由t和s共同確定,系數(shù)決定了t和s對(duì)能力值的重要度,其中 λ∈[0,1]。CAPABILITY(Ci)的值越大,說明該成員Agent Ci的能力越高。如果某成員Agent沒有剩余空間(即t=0)或無(wú)剩余存儲(chǔ)空間(即s≤0),也就是當(dāng)t×≤0時(shí),說明該成員Agent已沒有繼續(xù)執(zhí)行爬行任務(wù)的能力。
2)檢索文檔與查詢主題的相關(guān)度Relevance。假設(shè)用DOC=(D1,D2,Dk,…,Dm)表示某成員 A-gent檢索到的文檔集合,該集合按網(wǎng)頁(yè)文檔下載的時(shí)刻順次排列,Dm為最后一篇下載的文檔。利用向量空間模型,文檔Dk可表達(dá)成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è)置一個(gè)閾值Rel(Ci),作為衡量標(biāo)準(zhǔn)。閾值的計(jì)算方法為
然后比較relevance(KW,Dk)i和Rel(Ci)的大小并觀察relevance(KW,Dk)的變化情況。設(shè) P(relevancei)為某成員Agent第j次查詢時(shí)檢索文檔與查詢主題相關(guān)度的獎(jiǎng)懲值,獎(jiǎng)懲函數(shù)如下:
①若 relevance(KW,Dk)j≥Rel(Ci),說明成員Agent Ci的任務(wù)執(zhí)行情況較好,給予獎(jiǎng)勵(lì)。獎(jiǎng)勵(lì)值為:
②若 relevance(KW,Dk)j<Rel(Ci),說明成員Agent Ci的執(zhí)行情況差,給與懲罰。懲罰值為:
③若relevance(KW,Dk)整體走勢(shì)由低變高,超過了Rel(Ci),說明該成員Agent Ci有較好的前景,可以予以獎(jiǎng)勵(lì)。獎(jiǎng)勵(lì)值為:P(relevancei)=1;
④若relevance(KW,Dk)整體走勢(shì)由高變低,低于了Rel(Ci),說明該成員Agent Ci前景較差,給予懲罰。懲罰值為:P(relevancei)=-1。
設(shè)用P(relevance)0表示開始查詢之前,檢索文檔與查詢主題的相關(guān)度重要性的初始化值。那么,第i個(gè)成員Agent的檢索文檔與查詢主題的相關(guān)度的重要性為:
3)查詢響應(yīng)時(shí)間Response-Time。假設(shè)用tr表示某成員Agent的近五次查詢的平均響應(yīng)時(shí)間,th表示響應(yīng)時(shí)間的閾值(默認(rèn)值為15 s[9]),to表示可以被接受的最大響應(yīng)時(shí)間(默認(rèn)值為45 s),PRT(Ci)表示成員Agent Ci平均響應(yīng)時(shí)間的重要性。
①若某成員Agent Ci的平均響應(yīng)時(shí)間大于閾值,則對(duì)該成員Agent Ci進(jìn)行懲罰,將其重要性減少:
②若某成員Agent Ci的平均響應(yīng)時(shí)間小于閾值,則對(duì)該成員Agent Ci進(jìn)行獎(jiǎng)勵(lì),將其重要性增加:
③若成員Agent Ci的平均響應(yīng)時(shí)間恰好等于閾值,則不予懲罰和獎(jiǎng)勵(lì),即ΔPRT(Ci)=0。
設(shè)用PRT(Ci)0代表平均響應(yīng)時(shí)間的初始化值,初始時(shí)各個(gè)成員Agent平均響應(yīng)時(shí)間的重要性相同。因此,成員Agent Ci的平均響應(yīng)時(shí)間的重要性可表示為:
步驟4:計(jì)算各成員搜索引擎Agent的重要度。得到成員搜索引擎Agent各性能因子的評(píng)價(jià)值后,再加權(quán)綜合評(píng)價(jià)即可得到成員Agent Ci的重要度,計(jì)算公式為:
式中:α-性能因子PRel(Ci)的權(quán)值;β-性能因子Capability(Ci)的權(quán)值;γ-性能因子PRT(Ci)的權(quán)值。
性能因子的對(duì)于查詢的影響越大,相應(yīng)的權(quán)值就越高。
步驟5:根據(jù)重要度排名,選擇檢索性能最佳的若干(具體數(shù)目可根據(jù)個(gè)人需求設(shè)定)成員搜索引擎Agent進(jìn)行查詢調(diào)度。
成員搜索引擎調(diào)度策略是元搜索引擎的技術(shù)核心,通過選擇良好的成員搜索引擎調(diào)度策略可以提高元搜索引擎的系統(tǒng)性能。
結(jié)果合成策略是元搜索引擎的關(guān)鍵技術(shù)之一,結(jié)果合成策略的好壞在一定程度上決定著元搜索引擎性能的優(yōu)劣?;讵?jiǎng)勵(lì)機(jī)制的結(jié)果合成策略,克服了傳統(tǒng)合成策略在檢索結(jié)果合成排名時(shí)只考慮檢索結(jié)果與查詢主題相關(guān)度的缺陷,而是結(jié)合成員搜索引擎的重要度,將查詢結(jié)果被各成員搜索引擎命中的次數(shù)也考慮在內(nèi),即由成員Agent的爬行能力值、檢索結(jié)果與查詢主題的相關(guān)度、成員搜索引擎的查詢平均響應(yīng)時(shí)間和查詢結(jié)果命中次數(shù)四個(gè)影響因素來(lái)綜合決定結(jié)果合成。
基于獎(jiǎng)勵(lì)機(jī)制的結(jié)果合成策略的基本思想是,通過計(jì)算某一查詢結(jié)果在與其對(duì)應(yīng)檢索的成員搜索引擎中的局部重要性和在所有查詢結(jié)果中命中數(shù)量的全局重要性,來(lái)綜合評(píng)價(jià)該查詢結(jié)果的整體重要性。基于獎(jiǎng)勵(lì)機(jī)制的結(jié)果合成策略的基本步驟如下:
步驟1:計(jì)算查詢結(jié)果在成員搜索引擎中的局部重要性等級(jí)值WeightRank(Itemi)
首先按照6式計(jì)算成員搜索引擎對(duì)于查詢的重要度Weight(Ci),并計(jì)算成員搜索引擎的重要度等級(jí)值WeightRank(Ci)為:
由于成員搜索引擎按其重要度降序排列,優(yōu)先選擇排名靠前的、檢索性能最佳的若干成員搜索引擎進(jìn)行調(diào)度,那么該搜索引擎的檢索結(jié)果與查詢主題的相關(guān)度越大??烧J(rèn)為查詢結(jié)果在成員搜索引擎中的重要性等級(jí)值與該成員搜索引擎的重要性等級(jí)值呈正相關(guān),即存在函數(shù)映射:
且WeightRank(Itemi)∞WeightRank(Ci)(7)
步驟2:計(jì)算查詢結(jié)果命中數(shù)量的全局重要性等級(jí)值VoteRank(Itemi)
在元搜索引擎中,由于不同搜索引擎可能使用相同的索引數(shù)據(jù)庫(kù),有時(shí)多個(gè)搜索引擎可能會(huì)出現(xiàn)相同的搜索結(jié)果。如果某個(gè)搜索結(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)對(duì)某條搜索結(jié)果Itemj命中的次數(shù)為Vote-Num(Agent(Ci),Itemj),計(jì)算其命中次數(shù)等級(jí)值VoteRank(Itemj),計(jì)算公式為:
步驟3:計(jì)算查詢結(jié)果最終等級(jí)值Rank(Itemi)
用λ和φ為影響因子系數(shù)。則由式7和式8,可推導(dǎo)出查詢結(jié)果 Itemj的最終等級(jí)值 Rank(Itemj)為:
式9 中:λ∈(0,1),φ∈(0,1),且 λ +φ =1 。
為驗(yàn)證基于獎(jiǎng)勵(lì)機(jī)制的智能元搜索引擎系統(tǒng)的性能和可行性,將本系統(tǒng)模型在JADE平臺(tái)上實(shí)現(xiàn)仿真和模擬,并與元搜索引擎萬(wàn)緯的查全率、查準(zhǔn)率和查詢響應(yīng)時(shí)間進(jìn)行對(duì)比。由于萬(wàn)緯可以調(diào)用百度、搜狐、中文Google、中文雅虎、新浪GB、天網(wǎng)等6個(gè)中文搜索引擎,以及 Google、Yahoo、Hot-Bot等3個(gè)英文搜索引擎,因此在本系統(tǒng)的成員引擎知識(shí)庫(kù)中,通過搜索引擎的API接口函數(shù)添加相同的9個(gè)中英文搜索引擎(沒有提供API接口函數(shù)的搜索引擎可直接使用其檢索結(jié)果),并生成相應(yīng)的成員搜索引擎Agent。然后隨機(jī)采取20個(gè)中英文關(guān)鍵詞在本系統(tǒng)模型中搜索,按照獎(jiǎng)勵(lì)機(jī)制對(duì)各成員搜索引擎Agent的重要度計(jì)算,經(jīng)統(tǒng)計(jì)分析,得出重要度排名前4位的成員搜索引擎為:Google、百度、搜狐、Yahoo,用以供本系統(tǒng)模型查詢調(diào)度。在20次隨機(jī)查詢中,本系統(tǒng)與萬(wàn)緯的查全率、查準(zhǔn)率和查詢響應(yīng)時(shí)間情況的對(duì)比見圖3。
通過圖2可以看出,本系統(tǒng)采取獎(jiǎng)勵(lì)機(jī)制選擇的查詢性能最優(yōu)的四個(gè)獨(dú)立搜索引擎,與萬(wàn)緯同時(shí)調(diào)用9個(gè)獨(dú)立搜索引擎檢索對(duì)比,查全率幾乎無(wú)太大影響,查準(zhǔn)率比萬(wàn)緯平均提高了11.6%,查詢響應(yīng)時(shí)間平均縮短了2.3 s。
基于獎(jiǎng)勵(lì)機(jī)制的智能元搜索引擎與傳統(tǒng)元搜索引擎相比,有以下獨(dú)特優(yōu)勢(shì):
⑴每次查詢都選擇檢索性能最佳的成員搜索引擎進(jìn)行調(diào)度,在保證查全率的基礎(chǔ)上,避免了無(wú)效成員搜索引擎檢索返回的大量重復(fù)信息,在一定程度上提高了查準(zhǔn)率。
⑵由于無(wú)效成員搜索引擎冗余信息的減少,元搜索引擎后期結(jié)果處理的負(fù)擔(dān)降低,系統(tǒng)查詢響應(yīng)時(shí)間也隨之縮短。
⑶用定量法對(duì)成員搜索引擎的查詢性能進(jìn)行量化管理,通過完善的獎(jiǎng)勵(lì)機(jī)制發(fā)掘?qū)Σ樵儩撛谟杏玫某蓡T搜索引擎進(jìn)行調(diào)度,改進(jìn)了傳統(tǒng)成員搜索引擎調(diào)度策略的性能。
⑷將Agent技術(shù)與元搜索引擎結(jié)合,使系統(tǒng)更具靈活性和可擴(kuò)展性。成員搜索引擎Agent建立后,可在成員搜索引擎知識(shí)庫(kù)列表中按個(gè)人需求增刪、修改對(duì)應(yīng)的成員搜索引擎,滿足不同用戶的個(gè)性化需求。
隨著信息量的日益擴(kuò)增,搜索引擎技術(shù)的發(fā)展稱為人們備受關(guān)注的熱點(diǎn)問題之一。本文結(jié)合前沿的Agent技術(shù),基于獎(jiǎng)勵(lì)機(jī)制的智能元搜索引擎通過完善的獎(jiǎng)勵(lì)機(jī)制對(duì)成員搜索引擎進(jìn)行調(diào)度,并根據(jù)獎(jiǎng)勵(lì)機(jī)制對(duì)查詢結(jié)果進(jìn)行歸并,在提高查準(zhǔn)率、縮短查詢時(shí)間、減輕元搜索引擎后期的結(jié)果處理負(fù)擔(dān)方面,都在一定程度上有所提高。系統(tǒng)模型中各影響因子系數(shù)的判定以及一些具體的實(shí)現(xiàn)技術(shù),還需要進(jìn)一步研究。
[1]彭喜化.基于Agent的元搜索引擎結(jié)果優(yōu)化研究[D].重慶:西南農(nóng)業(yè)大學(xué),2004.
[2]鐘 智,黃發(fā)良.基于個(gè)性化服務(wù)的元搜索引擎模型[J].河北理工學(xué)院學(xué)報(bào),2005(01):73 -75.
[3]黃國(guó)景,崔志明.基于Ontology的個(gè)性化元搜索引擎研究[J].微電子學(xué)與計(jì)算機(jī),2004,21(12):100-103.
[4]王小朋.基于代理的元搜索引擎的研究[D].遼寧:遼寧工程技術(shù)大學(xué),2005.
[5]楊剛?cè)A.基于Agent的個(gè)性化信息檢索系統(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].青島:中國(guó)石油大學(xué),2007.
[9]黃偉建,宋曉潔,王子軒.辦公自動(dòng)化系統(tǒng)中動(dòng)態(tài)工作流引擎的研究[J].河北工程大學(xué)學(xué)報(bào):自然科學(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.