基于改進蟻群算法的高校圖書館書目檢索策略研究*

葛景陶

(湖南工業職業技術學院，湖南長沙410208)

基于改進蟻群算法的高校圖書館書目檢索策略研究*

葛景陶

(湖南工業職業技術學院，湖南長沙410208)

針對傳統的基于關鍵字查詢的信息檢索系統存在的不足，提出了一種基于改進蟻群算法的高校圖書館書目檢索策略。針對蟻群算法隨機優化方法的聚類結果不穩定性問題，提出了基于改進蟻群算法的圖書智能檢索系統的基礎模型，實驗證明，改進后的蟻群算法智能檢索系統能夠檢索到與關鍵字語義相關的信息，如同義、近義等關系，提高了傳統圖書檢索系統的檢索效率。

蟻群算法;高校;圖書館;書目檢索

目前，大多數高校圖書館的圖書信息搜索引擎主要是基于關鍵詞的全文匹配和基于主題分類進行檢索的，近年來，縱觀國內關于圖書館書目查詢的研究主要有:針對圖書館館藏急劇增長的現狀，龔寧靜分析了MARC數據的結構和一些特殊字符在此結構中的功能。其次確定什么形式的數據用戶易于理解。對MARC數據的轉換和提取方法進行分析，提出MARC數據的轉換提取方案和流程，給出JSP下的代碼實現。馮蘊琛認為Web式檢索已經是許多圖書館普遍使用的館藏資源檢索方式，但對無條件購買Web式檢索模塊的圖書館來說可以通過分析、研究中國機讀目錄格式，自行開發格式轉換程序把館藏數據轉換到后臺數據庫中，再利用動態網頁語言實現資源Web式檢索。曾莉針對開放式書庫讀者查找書籍不便的問題，分析現有的無線和RFID系統，提出結合書目檢索系統的相關信息，開發面向讀者的書籍定位系統。該系統可以大大縮短讀者找到書籍的時間，并減少工作人員的重復工作。劉永強將檢索結果圖形化、可視化，采用圖書書脊圖片作為人機界面，并就該系統的實現做詳細的探討。李永芳，陳志東，范春梅等對國家圖書館使用的書目檢索系統和大型網絡書店當當的書目檢索系統在檢索功能、檢索結果、用戶管理等幾個方面進行了比較，并對比較結果進行分析。指出目前圖書館書目檢索系統存在的問題以及由此引發的思考。孫萍探討了基于WAP的圖書館移動服務系統的技術框架，并利用WAP實現了移動終端在線書目檢索系統。該系統的建成，方便用戶通過WAP手機可以隨時隨地訪問圖書館業務，為圖書館拓展了新的服務途徑。章旭，錢龍華等認為傳統的書目檢索系統一般只能檢索本地或單一館藏的圖書情報資料，不能對多個館藏資料進行聯合書目檢索。提出了一個基于Web集成的聯合書目檢索系統，它能夠根據讀者提供的檢索關鍵字同時從多個圖書館的Web書目檢索系統中檢索出相應書目信息，并集成在統一的數據庫中，再將書目數據以Web方式返回給讀者。由于大多數圖書館均提供了Web書目檢索系統，因此該聯合書目檢索系統具有通用性和可行性的特點。

通過以上文獻分析可知，雖然研究者在圖書檢索中引入了一些比較新的概念與方法，也取得了一定的成果，但并不能真正解決用戶實際的需求。針對以上分析，提出了一種基于改進蟻群算法的高校圖書館書目檢索策略，同時，將聚類分析應用到書目信息查詢當中，返回更符合用戶需求的書目信息。針對蟻群算法隨機優化方法的聚類結果不穩定性問題，提出了基于改進蟻群算法的圖書智能檢索系統的基礎模型，實驗證明，改進后的蟻群算法智能檢索系統能夠檢索到與關鍵字語義相關的信息，如同義、近義等關系，提高了傳統圖書檢索系統的檢索效率。

一、蟻群算法

蟻群算法(ant colony optimization，ACO)，又稱螞蟻算法，是一種用來在圖中尋找優化路徑的機率型算法。作為一種通用型隨機優化方法，蟻群算法最初只是隨機地選擇搜索路徑并且不需要任何先驗知識，隨著對解空間的了解，搜索才變得有規律，并逐漸逼近直至最終達到全局最優解。蟻群算法是一種模擬進化算法，初步的研究表明該算法具有許多優良的性質。針對PID控制器參數優化設計問題，將蟻群算法設計的結果與遺傳算法設計的結果進行了比較，數值仿真結果表明，蟻群算法具有一種新的模擬進化優化方法的有效性和應用價值。螞蟻所在的環境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內的環境信息。環境以一定的速率讓信息素消失。蟻群算法所利用的搜索機制呈現出一種正反饋或自催化的信息素特征。蟻群算法模型由下面公式描述:

Ant System最先用于求解旅行商問題(TSP)，下面就以TSP問題為例來說明Ant System。設m為蟻群數量;dij為城市i，j之間的距離;τ(t)為t時刻連接城市i和j的路徑(i，j)上的殘留信息量，初始時刻各路徑上信息量相等，設τ(0)=C(C為常數);η表示城市i轉移到城市j的期望程度，可根據某種啟發式算法具體確定，在TSP問題中一般取ηij=l/dij。

螞蟻k(k=1，2，…，m)根據各條路徑上的信息量決定轉移方向，t時刻螞蟻k從城市i向城市j轉移的概率Pkij(t)計算式為

式中，j∈allowedk，s∈allowedk，allowedk={0，1，…，n－1}－tabuk表示螞蟻k下一步允許選擇的城市。與自然蟻群系統不同之處在于人工蟻群系統具有一定的記憶力，tabuk(k=1，2，…，m)用于記錄螞蟻k所走過的城市，集合tabuk隨著進化過程進行動態調整。人工蟻群保留了自然蟻群信息素揮發特點，隨著時間的推移，以前留下的信息逐漸消逝，參數ρ(0≤ρ＜1)表示信息素的持久性，1－ρ則表示信息素的衰減度。在每只螞蟻完成對所有城市(n個)的訪問后(即一次循環結束)，各路徑的信息素量根據式(1．2)，式(1．3)進行調整。

在(1．4)式中，Q是1個常數，表示螞蟻所留的信息素量，Lk表示第k只螞蟻在本次循環中所走路徑的長度。在初始時刻，τij(0)=C，Δτij=0(i，j=0，1，…，n－1)。ηij表示由城市i轉到j的期望程度，可根據具體問題選擇不同啟發算法具體確定，τij，Δτij及Pkij的表示形式各不相同。M．Dorigo定義了3種不同的模型:Ant cycle system，Ant quantity system及Ant density system，它們的差別在于表達式(1．4)的不同。

Ant quantity system模型中

Ant density system模型中

Ant quantity system，Ant density system模型利用的是局部信息，Ant cycle system模型利用的則是整體信息。其求解TSP時性能較好，通常被采用為基本模型。

二、基于改進蟻群算法的書目檢索策略

目前除了已得到公認的遺傳算法、模擬退火算法、粒子群算法等智能算法外，蟻群算法也已開始在這個行列中嶄露頭角，為復雜的組合優化問題提供了新穎且有競爭力的解決方法。主要步驟如下:

(一)全局更新規則

在蟻群系統中，只有全局最優的螞蟻才被允許釋放信息素。這種選擇，以及偽隨機比例規則的使用，其目的都是為了使搜索過程更具有指導性:螞蟻的搜索主要集中在當前循環為止所找出的最好路徑的領域內。全局更新在所有螞蟻都完成它們的路徑之后執行，應用式對(2．2)所建立的路徑進行更新。

其中，α為信息素揮發參數，0＜α＜1;Lgb為到目前為止找出的全局最優路徑。上式規定，只有那些屬于全局最優路徑的邊上的信息素才會得到增強。

(二)局部更新規則

在建立一個解決方案的過程中，螞蟻應用式(2．3)的局部更新規則對它們經過的邊進行激素更新。

其中，ρ為一個參數，0＜ρ＜1。由實驗發現，設置τ0=(nLnn)－1可以產生好的結果，其中n是城市的數量，Lnn是由最近的領域啟發產生的一個路徑長度。一只螞蟻從城市i向城市j移動時，局部更新規則的應用使得相應的信息素軌跡量逐漸減少。實驗表明，局部更新規則可以有效地避免螞蟻收斂到同一路徑。

(三)最優－最差螞蟻系統的工作過程

最優—最差螞蟻系統主要修改了蟻群系統中的全局更新公式。當所有螞蟻完成一次循環后，增加對最差螞蟻所經過的路徑信息素的更新。若(r，s)為最差螞蟻路徑中的一條邊，且不是最優螞蟻路徑中的邊，則該邊上的信息素量按式(2．4)調整

其中，ε為該算法中引入的一個參數，Lworst表示當前循環中最差螞蟻的路徑長度，Lbest表示當前循環中最優螞蟻的路徑長度;τ(r，s)表示城市r和城市s之間的信息軌跡量。算法的具體步驟如下:

(1)初始化;

(2)根據公式(1．1)、公式(2．1)為每只螞蟻選擇路徑;

(3)每生成一只螞蟻的路徑就按公式(2．2)進行一次局部更新規則;

(4)循環執行步驟(1．2)、(1．3)直到螞蟻都生成一條路徑;

(5)評選出最優和最差螞蟻;

(6)對最優螞蟻按公式(2．2)執行全局更新規則;

(7)對最差螞蟻按公式(2．3)執行全局更新規則。

循環執行步驟(1．1)、(2．1)直到執行次數達到指定數目或連續若干步內沒有更好的解出現。

三、結果分析

為了驗證改進算法在目錄查詢中的有效性，進行使用本文提出的基于改進蟻群算法的高校圖書館書目檢索實驗。實驗的開發工具為Visual Studio 2008，開發語言為CJHJ，數據庫使用SQL Server 2008，操作系統為Windows XP，整個實現過程采用面向對象的思想。

我們以圖書館20個分類的TSP問題作為示例說明，20個分類的TSP問題是一個簡單的TSP問題，它主要解決的是在一次遍歷所有分類的前提下，尋找一個連接所有分類之間的最短路徑。給定20個分類的坐標如表1所示。

表1 20個分類的坐標數據

基本蟻群算法的參數設置:α=1，β=2，ρ=0．7，Q=1，m=20，迭代次數為100。改進的蟻群算法中新添加的參數ε令其等于1．0。這樣所得實驗結果如表2。

表2 改進型蟻群算法與基本蟻群算法計算結果比較

所獲得的最優解對應的路徑為:

四、結語

針對傳統的基于關鍵字查詢的信息檢索系統存在的不足，文章提出了一種基于改進蟻群算法的高校圖書館書目檢索策略。針對蟻群算法隨機優化方法的聚類結果不穩定性問題，提出了基于改進蟻群算法的圖書智能檢索系統的基礎模型，實驗證明，改進后的蟻群算法智能檢索系統能夠檢索到與關鍵字語義相關的信息，如同義、近義等關系，提高了傳統圖書檢索系統的檢索效率。

［1］蘇菊，王棟．一種基于讀者借閱信息的圖書檢索結果客觀排序算法研究［J］．現代圖書情報技術，2008，(7)．

［2］李石生，劉海博，趙耀．基于Deep Web的圖書檢索系統設計［J］．河北大學成人教育學院學報，2008，(1)．

［3］付凱芳．網格計算在圖書文獻信息檢索中的應用［J］．微計算機信息，2009，(24)．

［4］賈宏．基于搜索引擎的數字圖書館智能信息檢索［J］．圖書館學研究，2006，(3)．

［5］董敏紅，李文淵．網絡環境下圖書館個性化信息服務探討［J］．大學圖書情報學刊，2006，(1)．

［6］Boudouda H，Seridi H，Akdag H．The Fuzzy Possibilistic C－Means Classifier［J］．Asian Journal of Information Technology，2005，4(11):981－985．

2011－04－28

葛景陶(1978－)，女，湖南邵東人，助理館員。