基于改进蚁群算法的高校图书馆书目检索策略研究*

葛景陶

(湖南工业职业技术学院，湖南长沙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－)，女，湖南邵东人，助理馆员。