基于改進遺傳算法的海量文獻數據查詢優化

王岳， 張叢昱， 吳長靜

(國網山東省電力公司， 山東, 濟南 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 總結

本文研究了多源環境中的源選擇問題，并提出了利用改進的遺傳算法在搜索空間尋找最優解。算法求解過程中，適應度函數同時考慮了源內容和源標簽來評估用戶查詢的源相關性。實驗驗證了本文所提方法在分布式信息檢索中的有效性。

在未來的工作中，可進一步考慮不同源之間的關系，并重新組合相似的資源，以允許資源共享。