基于改进蚁群算法的构件检索优化方法

张灿青彭成薛智山满君丰

（1.湖南工业大学计算机与通信学院株洲412007）（2.智能信息感知及处理技术湖南省重点实验室株洲412007）

基于改进蚁群算法的构件检索优化方法

张灿青1，2彭成1薛智山1，2满君丰1，2

（1.湖南工业大学计算机与通信学院株洲412007）（2.智能信息感知及处理技术湖南省重点实验室株洲412007）

在基于构件的系统软件实现过程中，根据用户需求对构件进行检索和选择越来越成为了构件系统的研究重点。利用基于信息素更新的改进基本蚁群算法来优化构件的复用规则，从而提高系统用户对所需构件选取的准确性和有效性。最后经实验结果证明，该方法搜索出来的构件复用规则准确率为75.2%，高于基本蚁群算法和模拟退火算法，对构件的检索和选择起到了较好的支持。

构件检索；改进蚁群算法；复用规则

Class NumberTP301.6

1 引言

随着软件多需求及复杂度的不断增长，软件的开发成本和效率问题显得越来越重要，而基于构件重复利用的开发模式已经成为软件工程中的研究重点。所谓构件复用就是重复利用已经开发成熟的程序或已积累的知识经验来减少在开发过程中具有相似功能或模式的重复工作［1］。构件复用已经在Web Services等一些服务软件架构中有了成熟的应用。目前，根据构件结构和功能性的不同，已经提出了很多相应的构件检索方法。例如，基于构件刻面分类的RE-BOOT、NATO分类方法，还有根据多种组合分类方式的青鸟构件库等都有了实际的应用［2］。随着人们对构件检索的理论研究及程序开发，Alnusair团队在构件的多刻面描述方法的构件检索中取得了很大的成果。Wang等使用模型树匹配方法对构件刻面描述进行匹配原则，提出了一种可重复利用的构件刻面描述性的匹配模型［3］。对构件的检索主要包括两方面，一是对构件的适用性进行检索，另一方面是对构件本身结构或功能的理解效率。目前已有的研究工作主要侧重对构件使用的检索效率，使用最多的就是基于刻面分类的构件检索方法，而对构件自身的理解还比较少。但目前在构件复用过程中对构件的检索和择取还具有以下几个问题：怎么在繁多的已检索结果中筛选对使用者真正有用的构件；如何借鉴其他复用者的构件经验来指导当前使用者对构件进行选择。

本文以提高构件的检索效率为目标，结合群体智能算法中具有典型应用的基本蚁群算法，从构件的属性信息和系统业务所需功能中建立搜索列表，利用改进基本蚁群算法对构件的复用规则和功能性特点等进行检索筛选，使构件复用者能够在构件检索结果中选取符合自己需求的构件。

2 相关知识

构件是系统软件中的重要组成部分，它实现系统业务特殊的功能，且符合统一的接口规范并实现具体接口方法［4］。如何根据系统软件的需求在构件库中找到符合自身功能的构件组合是构件复用的关键问题，并根据构件描述方式及分类方式选择适当的构件检索方法。在构件检索过程中，构件复用者根据系统软件业务对所需构件的需求构建索引，然后现有构件库根据构件的属性、功能等信息建立查询语句或视图，最后根据相关检索算法检索出构件组合。一般的构件检索结构如图1所示。

图1 构件检索结构

3 改进蚁群算法的构件检索

3.1 算法改进策略

由于基本蚁群算法具有易收敛于局部最优解和收敛速度慢等缺陷［5］，为提高算法搜索的高效性及可靠性，对基本蚁群算法的规则进行改进。

规则1：首先一轮蚂蚁搜索路线结束后，比较各路径中对应的信息素总量的大小，且只对本组中信息素浓度最大（即构件组合的效率值最大）的蚂蚁爬行路径进行信息素的更新。经过测试证明，改进蚁群算法的收敛速度和搜索结果准确率都有明显提高。

规则2：为了解决算法过早陷入局部最优解的早熟现象及停滞收敛性问题［6］，设定蚁群算法的最优路径列表为L，设路径列表的长度为Y，Y的值可根据某具体问题的规模大小而定。对每轮中蚂蚁寻优过程中信息素浓度（即本轮新搜索到信息素浓度所对应的构件组合）最大的爬行路径进行比较，并按大小顺序依次保存Y个最优的（即信息素浓度最大）路径到L中，其最大的路径放在L列表的第一个元素位置，并依次类推进行排列。当算法执行完最大循环次数之后，取L列表中的第一个元素与信息素浓度最大的蚂蚁路径进行比较：如果值大小相同，表示本次寻优的值可能收敛于全局最优解，信息素浓度最大的路径表示的构件组合即为最优构件组合；如果值大小不同，表示算法收敛于局部最优解，信息素浓度最大的路径应该与L列表中的路径进行比较后再得到最优结果［7］。按照L列表中路径从大到小的排列顺序搜索当前有效的、构件组合最优的组合列表。

基于基本蚁群算法的以上两个改进规则，若要保证算法找到全局最优解，至少需要有一只蚂蚁在一次路径寻优过程中选择了全局最优路径。但是倘若所有的蚂蚁都没有选择最优路径，此时算法的改进规则就无法搜索到最优解。为了避免或减少这种情况出现，可在算法适当的运行时刻判断算法是否正在或将要收敛于局部最优解，如果此刻的值收敛于局部最优解，则删除此刻路径局部最优解的值以提高算法全局选优的概率［8］。

3.2 算法MPDACO全局优化算法

1）设算法最大循环次数为Ncmax，蚂蚁个数为m，初始化时间t=0，蚂蚁循环变量k=0，禁忌表tabuk(k=1，2，…，m)，循环控制变量Nc=0，路径表pathk(k=1，2，…，m)，最优构件组合列表L等，将蚂蚁放置于构件组合路线中的初始位置节点，设组合路线中每条弧所表示的各QoS信息素浓度值τij(t)为MPDACO局部优化算法中所选择构件组合表示的信息素浓度值，若对应的信息素浓度值为空，此时令构件弧上的信息素τij(t)=const，其中const为常数，const的取值不可影响算法程序的下一步运行；

2）循环次数Nc=Nc+1，若Nc>Ncmax，则退出循环，跳转到步骤10）结束；

3）蚂蚁数目k=k+1，若k>m，则退出k循环，跳转到步骤8）；

4）搜索与蚂蚁所在节点相连路线的节点位置，再按照状态转移概率公式计算出转移概率的值，选择从该节点位置发出的下一个节点（即选择此节点和下一节点确定的构件）；

5）更新禁忌表tabuk，将新选择的节点添加到禁忌表中；并记下蚂蚁调用该构件后取得的各属性值Q1，Q2，…，Qn，用信息素进行相应的表示。若发现该构件的状态为无效，则在构件组合路线中将这一构件删除；

6）如若新选择的节点正好是构件组合路线的终点，则此蚂蚁寻优过程结束，跳转到步骤7）；否则跳转到步骤4）；

7）记录并计算蚂蚁此轮构件寻优路径新添加进来的信息素总和，这里新添加信息素总和指的是各个子构件新增信息素的加和；若此轮所有蚂蚁搜索路径结束，则跳转到步骤8），否则跳转到步骤3）；

8）比较本轮中所有蚂蚁选择构件组合的新增信息素总和，然后得到新增信息素总和值最大的构件组合列表并更新信息素规则，再把该新增信息素总和值最大的构件组合与最优构件组合列表中的构件组合进行比较：如果优于组合列表中最差的构件组合，则将该构件组合添加到最优构件组合序列中；如果最优构件组合列表已达到限定数量，则在添加该构件前需先删除最差的构件组合；

9）清空路径表pathk、禁忌表tabuk，跳转步骤2）；

10）将信息素最大的构件组合与最优构件组合列表L中的构件组合进行比较，得到最优的构件组合。

构件组合优化过程，有时需要根据构件的多个QoS值整体计算出最优的构件组合，利用MPDACO算法来计算得到τij(t)。设路径(i，j)表示的构件为s，且构件s共包含n个QoS属性值Q1，Q2，…，Qn，对应的转换函数为Q1(s)，Q2(s)，…，Qn(s)，各权值分别为w1，w2，…，wn，则构件s第r个QoS属性对应的信息素pheromoner的计算公式为：

从而τij(t)的计算公式如下：

进一步计算得到状态转移概率的计算公式为

图2 MPDACO算法性能测试图（构件数=100）

如果有接连多只蚂蚁的爬行路线相同，则表明该算法趋向于收敛；否则，当路径y点在完成信息素浓度的更新之后，需要继续进行下一轮的寻优搜索。在改进蚁群算法的规则中，将其中符合要求的添加进来，不符合的则删除。当一轮搜索完成之后，被添加进来的路径将从原路径列表中去除，并且继续下一轮的路径搜索，直到满足构件组合列表的数量小于给定值为止。

4 实验及分析

实验环境：服务器处理器为Inter Xeon CPU E5620，双处理器，主频均为2.4 GHz，内存为32 GB，操作系统为Windows 7专业版，编译器为Matlab2010。使用的构件库部分数据列表如表1所示。

本文使用基于信息素更新规则的改进蚁群算法对构件检索的方法，并将评估标准分为极好、好、良好、较差四类。最后通过实验验证提出的基于信息素更新规则的改进蚁群算法对构件复用性能起到一定的优化作用。

表1 构件库采集数据

算法中参数的设定也是个关键问题，参数或大或小均不能全面验证自身的有效性。经多次实验测试，本算法中参数设为如下时较为合适：蚂蚁数量设为600，信息素挥发常用系数为0.20。各算法对实验分别进行多次操作验证，得到一个较为稳定的值。在不同支持度阈值条件下，模拟退火算法、基本蚁群算法和改进蚁群算法搜索出来的规则数各平均值如图3所示。

图3 搜索规则数的比较

随着支持度阈值的增加，搜索出来的信息素规则数逐渐减少。在支持度阈值不变的情况下，基于信息素更新规则的改进蚁群算法比基本蚁群算法搜索出的规则数更多。改进蚁群算法虽比模拟退火算法搜索出来的规则数少，但模拟退火算法也有较明显的缺陷，其算法运行时间过长，且搜索出来的规则质量不高。三种算法搜索出来的复用规则经数据验证，各算法的准确率平均值分别如图4所示。

实验结果显示，使用基本蚁群算法和模拟退火算法的平均准确率分别为71.8%和68.1%，而基于信息素更新规则的改进蚁群算法的准确率则高达75.2%，可知基于信息素更新规则的改进蚁群算法检索性能有一定的提升。

图4 不同算法的准确率比较

5 结语

本文依照算法搜索机制，将基于信息素更新规则的改进基本蚁群算法应用到系统构件检索的优化问题中，并通过实验验证该改进算法的有效性和可靠性，从而提高了构件组合的检索性能。同时相比较于模拟退火算法68.1%的准确率和基本蚁群算法71.8%的准确率，基于信息素更新规则的改进蚁群算法的构件检索性能有所提高，其准确率达到了75.2%。但仍存在一些不足：由于构件的可复用性会受到多种因素的影响［10］，所以对于检索出来的构件组合要想满足各种业务需求是比较困难的。

［1］廖军，谭浩，刘锦德.基于Pi-演算的Web服务组合的描述和验证［J］.计算机学报，2005，28（4）：635-643.

LIAO Jun，TAN Hao，LIU Jinde.Describing and Verifying Web Service Using Pi-Calculus［J］.Chinese Journal of Computers，2005，28（4）：635-643.

［2］Guo Su-Chang，Huang Hong-Zhong，WANG Zhong-Lai，et al.Grid service reliability modeling and optimal task scheduling considering fault recovery.IEEE Transactions on Reliability，2011，60（1）：263-274.

［3］Alnusair A，Zhao Tian.Component search and reuse：an ontology based approach［C］//Proc of IEEE Internationa Conference on Information Reuse and Integration，2010：258-261.

［4］Xu Jiangle，Xiao Zhitao，Zhao Jinghua.An improved intelligent ant colony optimization based on genetic algorithm［J］.Microelectronics&Computer，2011，28（8）：47-50.

［5］Yuan Donghui，Liu Dayou，Shen Shiqun.Improved AC-GA based data association method for multi-target tracking［J］.Journal on Communications，2011，32（6）：17-22.

［6］姚全珠，冯欢，田琳.基于云端的构件库检索模型［J］.计算机应用，2016，36（S1）：262-264.

YAO Quanzhu，FENG Huan，TIAN Lin.Retrieval model based on cloud component library［J］.Journal of Computer Applications，2016，36（S1）：262-264.

［7］刘海亮，屈华敏，武方方，等.基于领域构件的余度管理软件平台研究与实现［J］.微电子学与计算机，2015，32（12）：100-104. LIU Hailiang，QU Huamin，WU Fangfang，et al.Research and Implementation of Domain Components Based Software Development Platform of Redundancy Management［J］.Microelectronics&Computer，2015，32（12）：100-104.

［8］张雷，陈立潮，潘理虎，等.构件的标识表示与检索方法研究［J］.小型微型计算机系统，2013，34（5）：1076-1079.

ZHANG Lei，CHEN Lichao，PAN Lihu，et al.Study on Tags Representation of Components and Tags Based Components Retrieval［J］.Journal of Chinese Computer Systems，2013，34（5）：1076-1079.

［9］夏亚梅，程渤，陈俊亮，等.基于改进蚁群算法的服务组合优化［J］.计算机学报，2012，35（2）：2270-2281.

XIA Yamei，CHENG Bo，CHEN Junliang，et al.Optimizing Services Composition Based on Improved Ant Colony Algorithm［J］.Chinese Journal of Computers，2012，35（2）：2270-2281.

［10］童浩，孙航，李晶，等.基于改进蚁群算法的构件检索方法［J］.计算机应用研究，2015，32（7）：2057-2059.

TONG Hao，SUN Hang，LI Jing，et al.Method based on improved ant colony algorithm for component retrieving［J］.Application Research of Computers，2015，32（7）：2057-2059.

Component Search Optimization Method Based on Improved Ant Colony Algorithm

ZHANG Canqing1，2PENG Cheng1XUE Zhishan1，2MAN Junfeng1，2
（1.College of Computer and Communication，Hunan University of Technology，Zhuzhou412007）（2.Key Laboratory of Intelligent Information Perception and Processing Technology（Hunan Province），Zhuzhou412007）

In the process of component based software implementation，it is more and more important to search and select components according to the needs of users.Based on pheromone update，the improved basic ant colony algorithm is used to optimize the component reuse rules，which can improve the accuracy and efficiency of the system users.Finally，the experimental results show that the proposed method is 75.2%，higher than the basic ant colony algorithm and simulated annealing algorithm，which has better support for the retrieval and selection of components.

component retrieval，improved ant colony algorithm，multiplexing rule

TP301.6

10.3969/j.issn.1672-9722.2017.06.010

2016年12月20日，

2017年1月20日

国家自然科学基金项目（编号：61350011，61379058，41362015）；湖南省自然科学基金项目（编号：14JJ2115，12JJ2036）；湖南省教育厅重点项目（编号：16A059）；湖南省教育厅优秀青年项目（编号：16B071）资助。

张灿青，女，硕士研究生，研究方向：网络化软件。彭成，男，博士，讲师，研究方向：可信软件、软件工程。薛智山，男，硕士研究生，研究方向：网络化软件。满君丰，男，教授，硕士生导师，研究方向：网络化软件。