一种基于奖励机制的智能元搜索引擎

黄伟建，祝月红，杜巍

(河北工程大学信息与电气工程学院，河北邯郸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 基于奖励机制的结果合成策略

结果合成策略是元搜索引擎的关键技术之一，结果合成策略的好坏在一定程度上决定着元搜索引擎性能的优劣。基于奖励机制的结果合成策略，克服了传统合成策略在检索结果合成排名时只考虑检索结果与查询主题相关度的缺陷，而是结合成员搜索引擎的重要度，将查询结果被各成员搜索引擎命中的次数也考虑在内，即由成员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.