葛景陶

(湖南工業(yè)職業(yè)技術(shù)學(xué)院，湖南長沙410208)

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

葛景陶

(湖南工業(yè)職業(yè)技術(shù)學(xué)院，湖南長沙410208)

針對傳統(tǒng)的基于關(guān)鍵字查詢的信息檢索系統(tǒng)存在的不足，提出了一種基于改進(jìn)蟻群算法的高校圖書館書目檢索策略。針對蟻群算法隨機(jī)優(yōu)化方法的聚類結(jié)果不穩(wěn)定性問題，提出了基于改進(jìn)蟻群算法的圖書智能檢索系統(tǒng)的基礎(chǔ)模型，實(shí)驗(yàn)證明，改進(jìn)后的蟻群算法智能檢索系統(tǒng)能夠檢索到與關(guān)鍵字語義相關(guān)的信息，如同義、近義等關(guān)系，提高了傳統(tǒng)圖書檢索系統(tǒng)的檢索效率。

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

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

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

一、蟻群算法

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

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

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

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

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

Ant quantity system模型中

Ant density system模型中

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

二、基于改進(jìn)蟻群算法的書目檢索策略

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

(一)全局更新規(guī)則

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

其中，α為信息素?fù)]發(fā)參數(shù)，0＜α＜1;Lgb為到目前為止找出的全局最優(yōu)路徑。上式規(guī)定，只有那些屬于全局最優(yōu)路徑的邊上的信息素才會(huì)得到增強(qiáng)。

(二)局部更新規(guī)則

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

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

(三)最優(yōu)－最差螞蟻系統(tǒng)的工作過程

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

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

(1)初始化;

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

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

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

(5)評(píng)選出最優(yōu)和最差螞蟻;

(6)對最優(yōu)螞蟻按公式(2．2)執(zhí)行全局更新規(guī)則;

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

循環(huán)執(zhí)行步驟(1．1)、(2．1)直到執(zhí)行次數(shù)達(dá)到指定數(shù)目或連續(xù)若干步內(nèi)沒有更好的解出現(xiàn)。

三、結(jié)果分析

為了驗(yàn)證改進(jìn)算法在目錄查詢中的有效性，進(jìn)行使用本文提出的基于改進(jìn)蟻群算法的高校圖書館書目檢索實(shí)驗(yàn)。實(shí)驗(yàn)的開發(fā)工具為Visual Studio 2008，開發(fā)語言為CJHJ，數(shù)據(jù)庫使用SQL Server 2008，操作系統(tǒng)為Windows XP，整個(gè)實(shí)現(xiàn)過程采用面向?qū)ο蟮乃枷搿?/p>

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

表1 20個(gè)分類的坐標(biāo)數(shù)據(jù)

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

表2 改進(jìn)型蟻群算法與基本蟻群算法計(jì)算結(jié)果比較

所獲得的最優(yōu)解對應(yīng)的路徑為:

四、結(jié)語

針對傳統(tǒng)的基于關(guān)鍵字查詢的信息檢索系統(tǒng)存在的不足，文章提出了一種基于改進(jìn)蟻群算法的高校圖書館書目檢索策略。針對蟻群算法隨機(jī)優(yōu)化方法的聚類結(jié)果不穩(wěn)定性問題，提出了基于改進(jìn)蟻群算法的圖書智能檢索系統(tǒng)的基礎(chǔ)模型，實(shí)驗(yàn)證明，改進(jìn)后的蟻群算法智能檢索系統(tǒng)能夠檢索到與關(guān)鍵字語義相關(guān)的信息，如同義、近義等關(guān)系，提高了傳統(tǒng)圖書檢索系統(tǒng)的檢索效率。

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

［2］李石生，劉海博，趙耀．基于Deep Web的圖書檢索系統(tǒng)設(shè)計(jì)［J］．河北大學(xué)成人教育學(xué)院學(xué)報(bào)，2008，(1)．

［3］付凱芳．網(wǎng)格計(jì)算在圖書文獻(xiàn)信息檢索中的應(yīng)用［J］．微計(jì)算機(jī)信息，2009，(24)．

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

［5］董敏紅，李文淵．網(wǎng)絡(luò)環(huán)境下圖書館個(gè)性化信息服務(wù)探討［J］．大學(xué)圖書情報(bào)學(xué)刊，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－)，女，湖南邵東人，助理館員。