王岳， 张丛昱， 吴长静

(国网山东省电力公司， 山东, 济南 250001)

0 引言

随着信息、网络、数据库等技术的不断发展，数字文献档案馆也迎来了大数据时代。数字文献档案馆可以看作是一个由分布式知识库组成的网络[1]，然而数据信息源的多样性和异质性等特点使得许多传统的信息检索方法很难付诸实施。特别是针对大量分布式信息源进行查询操作时会返回大量的信息，导致耗费大量查询时间，从而增加检索负担。

为此，可通过采用分布式信息检索技术(DIR)改善这类问题。姚树宇等[2]在分析传统搜索引擎技术存在不足的基础上，提出了一种使用分布式技术的搜索引擎，从而提高信息检索效率。吴云[3]针对当前图书馆信息检索系统存在的信息检索误差大、工作效率低等困难，设计了一种基于大数据分析技术的图书馆信息检索系统，从而提高信息检索效率。李培等[4]研究了分布式信息检索中资源选择方法，着重介绍了检索推理网络方法、基于文献排行榜的信息库选择方法和决策理论框架方法。上述方法都在不同领域研究了分布式信息检索技术，并取得了有效成果，然而考虑到数字文献档案馆中资源多样化和广泛分布等特点，将资源发送到所有源很难处理，尤其是其中一些源可能不包含所需的信息。

本文的重点是在大量信息源背景下的信息源选择问题。为了提高多源环境下数字文献档案馆查询效率，本文将源选择问题看作是一个搜索和优化问题，其目的是从给定查询的可用源中找到接近最优的源。为此，本文提出一种改进的遗传算法解决信息源选择问题。为了评估可行解的适用性，适应度函数同时考虑源内容和源标签，用户查询选择源时，可以利用源标签获取附加信息，从而提高检索精度。

1 模型描述

本文将源选择问题定义为一个二元组模型，描述如下：

(S,q)

(1)

其中，S={s1,s2,…,sn}为n个信息源，q为用户查询信息。

源选择问题可表示为确定S的子集S′，使其元素和q之间的相似性最大，即|S′|=k<|S|=n，其中k是查询所选源的数目。

进一步对搜索空间进行建模。搜索空间包括问题的所有可能的解决方案。由于解是n个源中k个源的组合，搜索空间的大小可用阶乘公式(二项式系数)表示为

(2)

随着n增加，搜索空间范围将剧增，这给求解过程造成严重影响，解决这个问题的一种方法是使用人工智能技术，如遗传算法。

2 算法思路

本文提出一种基于改进遗传算法的方法解决信息源选择问题。为了评估可行解的适用性，同时考虑源内容和源标签，源标签用于计算源和查询之间的相似性。算法思路总结如下。

首先，算法由一组源子集表示的解形成初始种群。其次，每个可行解或染色体由考虑源标签的适应度函数进行评估，同时遗传算子(选择、杂交和变异)用于从当前种群中产生新的种群。一旦新种群被创建，遗传过程就会反复迭代，直至找到满意解。

2.1 编码方案

从前述可知，源选择问题的解为k个源的组合。因此，用包含信息源的长度为k的向量表示可行解，从而应用整数编码以简化操作。考虑到源si介于1和n之间，故可能的解是1和n之间的k个整数的向量。

2.2 适应度函数

适应度函数用来衡量染色体在当前迭代的好坏。如前文所述，本文通过利用信息源的可行解和用户查询之间的相似性的平均值对可行解sol进行评估。为了计算解sol和查询q之间的相似性，将sol视为源文档的集合。此外，计算相似性时同时考虑了源内容和用户标签。因此，相似度的计算基于2个相似度度量：术语相似度和标签相似度。相似度计算公式如下：

sim(sol,q)=simter(sol,q)+simtag(sol,q)

(3)

其中，simter(sol,q)表示解sol和查询q之间的术语相似性，simtag(sol,q)表示解sol和查询q之间的标签相似性。

(1) 术语相似度

术语相似度simter(sol,q)由式(4)给出：

(4)

其中，simter(h,q)表示解中源h与查询q的术语相似度，k为解中源的个数。

simter(h,q)可以通过向量搜索模型的余弦度量来计算。用m维空间中的权重向量表示查询和源，则simter(h,q)计算如下：

(5)

其中，thj和tqj分别是源h与查询q中的项j的权重。

(2) 标签相似度

标签相似度计算公式如下：

(6)

其中，simtag(h,q)表示解中源h与查询q的标签相似度，k为解中源的个数。

为了计算源和查询之间的标签相似度，需要考虑用于注释源的标签集，源由一组标签及其频数表示。

令T(s)为一组标签，且这些标签由用户注释特定的源s：

T(s)={t1,t2,…,tn}

(7)

其中，n为标签个数。

与源s相关联的一组标签表示为，其中tj是自由文本标签，frj是源s的标签集中标签tj的频数。则用于注释源tw(ti)的每个标签的权重计算和标准化表示如下：

(8)

其中，tw(ti)为用于注释源s的标签ti的标签权重，fr(ti)为标签ti用于注释源的频数。

在用于注释该源的一组标签上，simter(h,q)计算如下：

(9)

其中，tw(ti)是源h的标签集合中标签ti的权重。

3 算法实施过程

本节介绍利用改进的遗传算法对用户输入信息在搜索空间从给定查询的可用源中找到接近最优的源。该方法的目标是从给定的产品模型中提供实现用户所请求的特定特性的元素子集，每个元素的输入和输出步骤如图1所示。图1给出了该方法的执行过程。该方法的输入包括源s、用户查询q及每个源的标签。

图1 算法执行过程

3.1 初始化种群

一般情况下种群都是随机生成的，因此覆盖了所有可能的解(搜索空间)。算法将在每一个连续世代中，从现有种群中选出一部分来繁殖形成新一代。与之类似，进化过程从一组可能的组合中随机产生的初始种群开始。

初始群体由一组染色体组成，且每个染色体表示问题的一个解，并由一个k源向量表示。如前所述，源通过由1到n的整数进行编码。同时需注意，在群体产生过程中，应避免相同的源(重复基因)在同一染色体中，例如在染色体{2，5，3，2}中，数字2是重复的，这样的染色体构造必须避免。此外也应该避免在群体中重复相同的染色体(重复染色体)，例如{3,4,5,8}和{8,3,5,4}，虽然顺序变换，但是本质是重复过程。

3.2 基因操作

(1) 选择

选择操作思想是优先选择更好的染色体。选择复制具有高适应度值的染色体并移除具有低适应度值的染色体，需注意最佳染色体是通过评估其适应度值来确定的。

从群体中选出最佳的候选个体作为其余算子的输入，有多种方法可以用来执行父代的选择，最广泛的选择之一是遵循轮盘赌选择机制。也就是说，来自群体的每个模型片段都有可能被选择，且选择概率与它们的适应度得分成比例。因此，具有高适应度值的候选人被选为下一代的概率更高。

(2) 交叉

交叉算子用来模拟自然界中某些生物的有性生殖过程，从而产生新的个体。也就是说，2个个体混合他们的基因组信息产生一个新的个体，这个个体持有来自父母双方的一些基因信息，这可能使他更好(或更糟)地适应他的生活环境。

根据这一思想，应用于模型片段的交叉算子以2个模型片段和1个随机生成的掩码作为输入，将它们组合成2个新个体。掩码确定如何进行组合，为模型片段的每个元素指示子代是从一个父代继承还是从另一个父代继承(如果该元素是否存在于父代上，则包括该元素)。模型片段是产品模型中存在的元素的子集。由于2个模型片段都是从同一个产品模型中提取的，因此它们的组合(应用掩码)将始终返回作为产品模型一部分的模型片段。结果将产生2个个体，一个通过直接应用掩模，另一个通过应用掩模的逆运算。

4 仿真与分析

使用Java遗传算法库JGAP在Java环境中实现所提出的遗传算法。实验使用的数据集为涵盖不同领域(计算机科学、医学、法律等)的科学研究文献数据库，如表1所示。

表1 实验所用数据库

用户查询采用基于查询的抽样方法用于构建源描述，即将由单个项组成的查询发送到每个源，查询是根据源所属的领域来选择的。此外，实验中要求用户对每个源返回的前20个文档进行相关性判断，并以此形成标签集，如果源返回至少3个与查询相关的文档，则将其标签为相关。实验中，改进遗传算法部分参数如表2所示。

表2 遗传算法参数

图2为每个源由不同算法在20个查询中的平均精度对比结果。从图2可以看出，与GASS算法和传统遗传算法相比，本文所提算法的精度有所提高。这是由于考虑标签集使得算法能够找到最适合用户查询的源。仿真结果表明所提出的改进遗传算法能较好地解决分布式环境下的源选择问题。

图2 不同算法的对比结果

5 总结

本文研究了多源环境中的源选择问题，并提出了利用改进的遗传算法在搜索空间寻找最优解。算法求解过程中，适应度函数同时考虑了源内容和源标签来评估用户查询的源相关性。实验验证了本文所提方法在分布式信息检索中的有效性。

在未来的工作中，可进一步考虑不同源之间的关系，并重新组合相似的资源，以允许资源共享。