基于知识的人工蜂群服务组合优化算法

王 野,周井泉,常瑞云

(南京邮电大学 电子科学与工程学院，江苏 南京 210003)

基于知识的人工蜂群服务组合优化算法

王 野,周井泉,常瑞云

(南京邮电大学 电子科学与工程学院，江苏 南京 210003)

近年来，Web服务组合问题一直是研究热点，是典型的NP难题。随着Web服务技术的发展，用户更加注重服务质量。目前，将人工蜂群算法应用于连续性优化问题的研究比较多，然而将其用于解决Web服务组合这一离散化问题却不多见。为了提高在大量Web服务中快速有效找到针对特定问题的最优Web服务组合的效率，以满足用户对服务质量日益提高的需求，文中提出一种基于服务顺序知识的人工蜂群算法(KABC)来解决这一NP问题。首先，建立了单个服务的QoS评估模型，并提出了应用于Web服务组合优化问题的QoS数学模型。其次，算法运用当前较优解的服务顺序知识来指导后续解的更新，加快了算法的收敛速度，提高了精度。实验结果表明，与原始的ABC、PSO算法相比较，KABC具有更快、更优的搜索能力以及更好的求解质量。

Web服务组合；NP；人工蜂群算法；知识

0 引 言

在面向服务的计算模式下，网络中已存的Web服务能够无缝地组合起来，进而形成新的功能更强的增值服务来满足用户日益提高的需求。尤其是在开放动态的Web环境中，如Ad-Hoc，WSN等，需要从海量的候选服务中选择最优的服务。然而，具有相同功能的服务数量随着网络技术的发展而急剧增加，在选择服务时既要考虑服务功能的方面，还要考虑到服务质量(Quality of Service，QoS)[1]这些非功能性的指标，如服务响应时间、可用性、代价等。候选的Web服务集合之间进行的“爆炸”组合，是一个典型的NP难题[2]。如何从具有不同QoS属性的高度动态化的服务中，高效率地选择满足用户QoS需求的服务，已成为服务组合中所面临的一个关键难题,具有重要的理论意义和实用价值。

Web服务组合起源于软件重用，其基本思想是通过已有的Web服务，按照一定的组合逻辑，产生新的或质量更高的服务来满足用户需求，实现服务的增值。文献[3]分析了Web服务组合的概念和实现框架。根据研究侧重点及其依赖的技术基础，将WSC方法归为两大类别—基于工作流、状态演算和进程代数模型描述的过程驱动的组合方法和基于语义描述的自动服务组合方法。

为了解决服务组合这一NP难题，研究者做了大量研究。文献[4]提出了一种基于OWL-S和HTN的Web服务组合架构，并在此基础上提出了基于改进的K-means的服务集合算法。该算法依据不同服务之间的关联，用K-means方法将众多服务划分成一些集群，减少了服务的匹配时间，提高了算法的效率。粒子群算法(PSO)具有控制参数少、收敛速度快的优点，但容易受到当前最优解的引导陷入局部收敛。文献[5]改进了PSO算法，并应用于Web服务组合之中。该算法使用基于粒子圆周轨道和零惯性权重，基于三角函数的动态学习因子，控制粒子群的行为，使粒子的局部认知和全局搜索能力达到较好的平衡。文献[6]改进了PSO算法并用来解决Web服务选择问题。该算法采用自适应权值调整和非统一变异策略获得了较为满意的结果。人工蜂群算法凭借其算法实现简单、收敛精度高而得到广泛的应用。文献[7]改进了人工蜂群算法，通过引入混沌策略产生新的解来代替面临丢弃的解，使得算法跳出局部最优解，同时引入禁忌搜索策略避免跟随蜂的重复搜索，提高了算法的成功率以及搜索效率。

为了进一步提高服务组合问题的求解效果，文中提出一种基于知识的人工蜂群算法(Knowledge-basedArtificialBeeColony，KABC)。通过设计一种针对Web服务组合优化问题的服务顺序知识，引导算法后续解的更新，加快算法的收敛速度，并提高精度。实验结果表明，KABC求解质量优于原始的ABC和PSO算法。

1 Web服务组合问题描述

QoS代表着一个Web服务的非功能属性。成本(C)、可靠性(R)、响应时间(T)是其中较为重要的三个属性。一条完整的服务组合路径主要包含以下三个部分：

子任务：服务组合的基本单元。每一个子任务从它的候选服务中选择一个Web服务来完成对应的功能。所有子任务完成各自对应的部分功能后，按照用户的需求组合形成最终的服务。

候选服务：每一个候选服务都有不同的非功能属性QoS值，其中一些参数由服务提供者给出，另外则由服务使用者提供。同一个子任务下的候选服务具有相同的功能，即都能完成该子任务，但各自的QoS属性值不同。

服务组合：组合服务由不同子任务选出的候选服务按照一定的逻辑或者拓扑组合而成。组合后的服务具有更强大的功能，满足用户更高的需求。组合服务的整体QoS值可由候选服务按照相互组合结构计算获得。

Web服务有四种基本结构(见图1)：顺序结构(a)、循环结构(b)、并行结构(c)和选择结构(d)。

在顺序结构中，任务按照先后顺序依次执行；在循环结构中，一个任务将被循环执行许多次；在并行结构中，所有的并行任务可以同时执行，但是只有所有的并行任务都执行完毕才可进行接下来的任务；在选择结构中，每一个子任务都能完成需求的功能，并且只要有一个分支任务执行完成就可继续向下执行后续任务。

图1 Web服务组合四种基本结构

因为组合Web服务是由上述四种基本结构组成，因此一个结构确定的服务组合的QoS可以通过对应基本结构的QoS属性计算获得。四种结构的成本(C)、可靠性(R)、响应时间(T)计算公式如下：

(1)

(2)

(3)

其中：n是任务数目；k是循环次数；pi是选择结构中分支的选择概率。

这些QoS指标中有的是值越大越好，如可靠性，称为效益型指标，属于正指标。相反地，成本、响应时间则是成本型指标，属于负指标。

为了能够统一计算，需要对各个QoS指标值进行标准化处理。公式如下：

正指标(可靠性)：

(4)

负指标(成本、响应时间)：

(5)

其中：Q是原始QoS属性值；Qstand是标准化后QoS属性值。

标准化之后，将其他三种组合结构转化为顺序结构[8]，从而简化计算。因此，基于QoS的Web服务组合计算模型定义如下：

(6)

其中，ω表示各个属性的权值，且ω1+ω2+ω3=1。

2 算法描述

近年来，越来越多的研究者开始探索智能优化算法迭代过程中演化与学习之间的联系。在求解Web服务组合问题时，可以利用优化过程中准最优解的相关知识，然后用获得的知识来指导后续的优化过程。

基于上述理念，文中提出一种基于服务顺序知识的人工蜂群算法来解决Web服务组合问题。

2.1 服务顺序知识

文献[9]提出了一种弧段顺序知识(Arc Priority Knowledge，APK)，用以描述所需弧段之间顺序的一种累积知识。在求解Web服务组合优化问题时，经常要考虑相邻的两条服务弧段之间的关联。为了有效利用该关联信息，文中以弧段顺序知识为基础，提出了服务顺序知识。和弧段顺序知识相比，其不同点在于：文中根据组合问题的子任务数以及每个子任务下候选服务的数目来限定记录服务顺序知识矩阵的行和列的大小。假设子任务数是n，每个子任务的候选服务数是m。仅考虑相邻两个子任务之间的服务顺序知识，那么每个解(维度为n)都有n-1段服务顺序，记录一个服务顺序所需要的矩阵大小为m×m，因此总的计数矩阵大小为(n-1)m×m。

服务顺序知识的抽取：按照如下方式从已获得的准最优解中抽取弧段顺序知识。对于任意一个新生成的组合方案，将它插入到当前的种群中，然后将种群中所有的方案按照适应度值的大小由高到低排列。如果新生成的方案处于种群的前20%，则采用新方案来更新服务顺序知识。例如，新生成的组合方案顺序是2→4→1→3，那么新方案中出现了三个服务序列(2，4)，(4，1)和(1，3)。将服务序列(2，4)，(4，1)和(1，3)在计数矩阵出现的次数分别增加1次。

服务顺序知识的应用：为了防止更新后的准最优解在算法后续的更新过程中遭到破坏，使用服务顺序知识指导后续的解更新。若某服务序列在已获得准最优解中出现的次数非常多，那么在下一轮的迭代过程中则以较小的概率选择该服务进行更新；反之，则以较大概率破坏该服务序列。

假设服务顺序知识如表1所示。当前的个体为2→4→1→3，则服务序列为(2，4)，(4，1)，(1，3)，在准最优解中出现的次数分别为11，16和8，在服务序列(2，4)，(4，1)，(1，3)之间选择更新的概率分别为37.50%、6.25%和56.25%。计算方法为：将三条服务顺序出现的次数11、16和8取相反数得-11、-16和-8，然后加上一个最小正整数17使得相反数变为正数6、1和9，最后除以三个数之和16得到服务顺序更新概率分别为37.50%、6.25%和56.25%。

表1 服务顺序知识

2.2 人工蜂群算法

人工蜂群算法[10]是Karaboga于2005年提出的一种模拟蜂群觅食行为的群体智能优化算法。对比其他智能算法，该算法控制参数少、易于实现，受到众多学者的关注。

在ABC算法中，有三种分工不同的蜜蜂，分别是引领蜂、跟随蜂和侦察蜂。引领蜂是负责探索优质蜜源并进行初步邻域搜索的蜜蜂，数量和蜜源数量相等；跟随蜂根据引领蜂传递蜜源信息，有选择地对蜜源进行邻域搜索，跟随蜂数量与引领蜂数量相等；侦察蜂则是进行全局随机搜索，防止漏掉质量更高的其他蜜源。每只蜜蜂都对应一个解，引领蜂代表当前种群的现有解；跟随蜂代表潜在的邻域搜索解；侦察蜂则代表全局随机搜索解。

一个蜜源的位置代表优化问题一个可能的解，解的适应度用花蜜的质量表示。首先，ABC算法随机生成含有SN个解的初始种群。每个解xi(i=1,2,…,SN)是一个D维的向量。然后，引领蜂先对对应的食物源(解)进行一次邻域搜索，并选择花蜜数量多也就是适应度较高的食物源(解)。跟随蜂按照概率选择食物源。花蜜越多的食物源，被选择的概率越大。跟随蜂会对被选中的蜜源进行一次邻域搜索，并选择较优的解。跟随蜂按照概率值pi选择食物源，计算表达式如下：

(7)

其中，fitnessi是第i个解的适应度。

引领蜂和跟随蜂按照式(8)进行邻域搜索[11]：

vij=xij+rand(xij-xkj)

(8)

其中：k∈{1,2,…,D},j∈{1,2,…,D}，k和j都是随机选取的，但是k不能等于i；rand是-1和1之间的随机数。

如果某个解经过limit次循环之后仍然没有得到改善，那么这个解就要被舍弃掉。假定丢掉的解是xi，那么就由侦察蜂按照式(9)产生一个新的解来代替xi。

(9)

2.3 基于知识的人工蜂群算法解决Web服务组合

应用KABC算法求解Web服务组合优化问题，首先要解决的是蜂群的初始化。假设服务组合共包含n个子任务，每个子任务待选的Web服务个数都是10，那么每个待选子服务可用WSij(C,R,T)表示。其中，i为子任务的编号，j为完成该子任务的候选服务的编号。设定蜂群的每个成员(解)代表一条服务组合路径，用向量X=[x1,x2,…,xn]表示[12]，解的维度与服务组合问题的子任务数一致。举例来说，服务组合路径WS15→WS26→WS39→WS40→…→WSn7可以用X=[5,6,9,0,…,7]来表示。

然后是适应度值fitness(X)的计算问题。根据解X=[5,6,9,0,…,7]各个维度的编号读取每个已选服务的成本、可靠性和响应时间三维QoS属性值。按组合问题的组合结构(顺序、循环、并行和选择)，结合式(1)、(2)、(3)和(6)计算求得该解对应的适应度值。同时，无论引领蜂、跟随蜂还是侦察蜂对应的解都是一个整型向量X，并且只有解的适应度值得到了提高，算法才会对现有的解进行更新，所以必须对解的更新机制进行整形化。具体公式如下：

vij=xij+[rand(xij-xkj)+0.5]

(10)

其中，[]是取整符号。

KABC算法应用于Web服务组合问题具体步骤描述如下：

步骤1：设置相关参数。引领蜂个数=跟随蜂个数=SN，最大迭代次数为MCN，控制参数为limit。

步骤2：初始化蜂群。随机产生SN个蜜源X，并计算适应度值fitness(X)。

步骤3：引领蜂按式(10)进行邻域搜索，并根据新旧蜜源的适应度值采取“贪婪原则”进行选择。

步骤4：若当前迭代次数小于MCN*20%，则转向步骤5，否则运用已获得的弧段顺序知识选择引领蜂合适的弧段进行更新。

步骤5：根据式(7)计算各蜜源被选择的概率，跟随蜂采用“轮盘赌”原则进行选择，并按式(10)进行邻域搜索。

步骤6：若当前迭代次数小于MCN*20%，则转向步骤7，否则运用已获得的弧段顺序知识选择引领蜂合适的弧段进行更新。

步骤7：若某蜜源经过limit次迭代适应度值仍未得到改善，则与之对应的引领蜂转为侦察蜂，即重新生成蜜源。

步骤8：从已获得的准最优解中抽取弧段顺序知识，记录在矩阵中。

步骤9：记录目前最优蜜源，若当前迭代次数小于最大迭代次数MCN，转向步骤3进行下一次迭代，否则输出最优解作为优选结果。

3 实验分析

鉴于目前还没有统一的实验平台以及相关数据集[13]，本实验所采用的是随机生成各个Web服务QoS的三维属性值，每一维对应的权重都是1/3。实验中服务组合的子任务数是20，每个子任务的候选服务数是100。由上文可知，服务顺序知识矩阵的规模应是1 900×100。实验环境为联想G490，Intel(R)Core(TM)i5-3230MCPU@ 2.60GHz,4GBRAM,Windows8,VC6.0。

为了验证KABC算法的有效性，选取原始的ABC、PSO算法作为比较对象[14]。设置最大迭代次数MCN=100，种群规模NP=200，limit=100。考虑到智能算法的随机性，每次实验运行100次，记录算法求解的最大值、最小值、平均值和中间值。

图2为原始ABC、PSO以及KABC算法求得的解的平均适应度值随迭代次数增加而变化的过程。

图2 算法平均适应度值演变趋势

由图可知，从第20次迭代开始引入服务顺序知识以后，KABC算法可以迅速将解的适应度值提高到一个更高的数值，增强了算法的精搜能力。在求解过程中，KABC的平均适应度值始终优于其他两种算法，这说明基于知识的ABC算法更加适合解决复杂的服务组合问题，与理论预期相符。

图3为三种算法运行100次，所得解的适应度的最大值、最小值、平均值和中间值的对比情况。

图3 算法运行100次数据统计

对比柱状图，在运行次数同为100、最大迭代次数同为100的情况下，KABC算法在适应度最大值、最小值、平均值、中间值都大于其他算法，并且4个值之间的差距很小，说明该算法的稳定性更好。

4 结束语

文中给出了Web服务的QoS属性的评估模型以及数学计算模型。通过引入服务顺序知识，改进了ABC算法并用来解决Web服务组合优化问题。实验结果证明了KABC算法的有效性和可行性。然而，基于知识的ABC算法的寻优能力以及适应大规模服务组合问题的能力也有待加强。这些将是后续研究工作的重点。

[1]ZengL,BenatallahB,NguAH,etal.Qos-awaremiddlewareforwebservicescomposition[J].IEEETransactionsonSoftwareEngineering,2004,30(5):311-327.

[2]WoegingerGJ.ExactalgorithmsforNP-hardproblems:asurvey[M]//JungerM.CombinatorialOptimization.Berlin:Springer,2003:185-207.

[3] 倪晚成,刘连臣,吴 澄.Web服务组合方法综述[J].计算机工程,2008,34(4):79-81.

[4]TangX,TangF,BingL,etal.DynamicwebservicecompositionbasedonserviceintegrationandHTNplanning[C]//Procof2013seventhinternationalconferenceoninnovativemobileandinternetservicesinubiquitouscomputing.[s.l.]:[s.n.],2013:307-312.

[5] 温 涛,盛国军,郭 权,等.基于改进粒子群算法的Web服务组合[J].计算机学报,2013,36(5):1031-1046.

[6]HuCH,ChenXH,LiangXM.DynamicservicesselectionalgorithminWebservicescompositionsupportingcross-enterprisescollaboration[J].JournalofCentralSouthUniversityofTechnology,2009,16(2):269-274.

[7]HeJ,ChenL,WangX,etal.Webservicecompositionoptimizationbasedonimprovedartificialbeecolonyalgorithm[J].JournalofNetworks,2013,8(9):2143-2149.

[8]WangP.QoS-awarewebservicesselectionwithintuitionisticfuzzysetunderconsumer’svagueperception[J].ExpertSystemswithApplications,2009,36:4460-4466.

[9] 姚 锋,邢立宁,李菊芳,等.求解双层CARP优化问题的知识型遗传算法[J].系统工程理论与实践,2014,34(1):239-247.

[10]KarabogaD,BasturkB.Apowerfulandefficientalgorithmfornumericalfunctionoptimization:ArtificialBeeColony(ABC)algorithm[J].JournalofGlobalOptimization,2007,39(3):459-471.

[11]KarabogaD,GorkemliB,OzturkC,etal.Acomprehensivesurvey:ArtificialBeeColony(ABC)algorithmandapplications[J].ArtificialIntelligenceReview,2012,42(1):21-57.

[12]ZhaoX,SongB,HuangP,etal.AnimproveddiscreteimmuneoptimizationalgorithmbasedonPSOforQoS-drivenwebservicecomposition[J].AppliedSoftComputing,2012,12:2208-2216.

[13]Al-HelalH,GambleR.Introducingreplaceabilityintowebservicecomposition[J].IEEETransactionsonServicesComputing,2014,7(2):198-209.

[14]TaoF,LaiLiY,XuL,etal.FC-PACO-RM:aparallelmethodforservicecompositionoptimal-selectionincloudmanufacturingsystem[J].IEEETransactionsonIndustrialInformatics,2013,9(4):2023-2033.

Artificial Bee Colony Algorithm for Service Composition Based on Knowledge

WANG Ye，ZHOU Jing-quan，CHANG Rui-yun

(College of Electronic Science and Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Web service composition,as a NP hard problem,has always been a hot research in recent years.With the development of Web service technology,users pay more attention to quality of service.Many researches on Artificial Bee Colony (ABC) are carried out to solve continuous optimization problems.It is rare for using ABC to tackle the Web Service Composition Problem (WSCP) of discrete optimization.In order to improve the efficiency of finding the best service composition,a Knowledge-based Artificial Bee Colony (KABC) algorithm is proposed and applied to WSCP.Firstly,the QoS model of a single Web service and mathematics model of a service composition are built.Secondly,the knowledge of service sequence of the high quality solutions is used to guide the updating of next generation solutions,so as to accelerate the convergence speed and improve the precision of solutions.Experiment shows that compared with original ABC and PSO,KABC has a better performance on WSCP.

Web service composition;NP;artificial bee colony;knowledge

2015-07-27

2015-11-05

时间：2016-05-05

国家自然科学基金资助项目(61401225)

王 野(1991-)，男，硕士研究生，研究方向为服务组合优化问题；周井泉，博士，教授，硕士生导师，研究方向为通信网络的信息管理和控制。

http://www.cnki.net/kcms/detail/61.1450.TP.20160505.0817.054.html

TP301.6

A

1673-629X(2016)05-0046-05

10.3969/j.issn.1673-629X.2016.05.010