基于梯度的改进动态Web服务选择算法

杨丽琴，康国胜

(1.上海中医药大学 计算机综合教研室，上海 201203;2.复旦大学 计算机科学技术学院，上海 201203)

1 概 述

随着服务计算技术的迅猛发展，互联网上的可用服务的数量迅速增长。然而，单个Web服务提供的功能往往比较单一，为了实现更复杂的功能，需要将共享的多个Web服务组合成为用户所需要的复杂服务，满足用户定制化的需求。因此，Web服务组合优化问题成为服务计算研究的一个挑战。

支持QoS的Web服务选择主要分为三大类。第一类，研究单个服务请求的Web服务优化选择[1-3]；第二类，研究面向多个相同或相似功能服务请求的全局优化Web服务选择[4-5]；第三类，研究组合服务中动态Web服务优化选择[6-7]。文中主要考虑第三类情形。通常，对一个复杂的功能，会建立一个业务流程来实现，该业务按一定的流程结构组成，每个流程节点通过调用服务来完成，最终整个流程就形成了一个组合服务。然而，互联网环境复杂多变，带来Web服务质量的动态变化。即使Web服务的功能相同或相似，但是它们的服务质量(quality of service，QoS)参数(如执行费用、信誉等级、执行时间等)可能不同。而且，同一服务在不同的时间点服务质量也可能不同。因此，如何从满足各节点功能需求的服务中选出最终的服务，形成一个组合服务来完成用户的定制化需求成为一个难题，该问题文中称为动态Web服务选择。尤其是在当前大数据、云计算环境下，服务选择问题显得尤为严峻。

目前，关于组合服务中的动态Web服务选择的研究大多是基于QoS局部最优的原则[8]，即独立地为流程中的每个节点选择一个满足业务功能且服务的综合服务质量最优的服务。这种方法没有考虑单个服务节点质量对组合服务中的其他节点质量的影响，即考虑了满足局部约束但没考虑满足全局约束，因此无法解决多目标多约束的QoS全局优化问题。比如：对一部分服务质量需要满足约束条件即可，而对另一些服务质量需要尽量优化。一个具体的例子如下：在对组合流程中的费用和执行时间做约束的条件下使得可靠性和信誉等级最高。针对组合服务中的QoS全局最优Web服务选择问题，目前已有一些相关工作[9-12]，但均具有以下缺点：集中在解决局部优化问题以及单目标问题，无法解决多目标的优化问题；只提供单个的优化方案，用户无法从多个优化方案中进行选择；计算量大、算法复杂度高，随着流程中业务节点以及节点对应的候选服务的增多，组合优化问题的求解效率将大大降低。因此，使用启发式算法来提高Web服务组合优化问题的求解是一个可行方案。针对以上服务组合优化选择算法的缺点，文献[13]基于多目标遗传算法提出了一种动态选择QoS全局最优化算法。首先将服务动态组合优化建模为一个带QoS约束的多目标优化问题；然后，采用遗传算法启发式原理求解多目标优化问题；最后，产生一组满足约束的Pareto优化服务组合方案。这种启发式算法解决了多目标优化求解的问题，然而算法的执行效率还需要改进。基于粒子群优化算法，文献[6]出了解决动态Web服务优化选择问题的算法PSO-GODSS，该算法不仅解决了前述的3个问题，并改进了动态Web服务选择的执行效率。实验结果证明相比遗传算法，PSO-GODSS算法的执行效率和收敛速度均较优，但依然还有待提高。尤其在当前的大数据环境下，Web服务的规模非常庞大，算法的求解效率显得尤为重要。

在文献[6]的基础上，针对多目标多约束服务组合优化问题，文中引入梯度的方法改进传统的粒子群算法，提出了解决该问题的改进算法gPSO-GODSS(gradient PSO-GODSS)。相对于文献[6]中的PSO-GODSS算法，该算法收敛速度更快，能够快速找到全局最佳服务组合决策。

2 服务组合优化问题

定义(多约束多目标的优化路径，即MCOOP)[6]：对于图G=(N,E,W)，其中N为顶点集，E为链路集，W为链路权重，设存在k(k≥2)个约束Ci(i=1,2,…,k)，从源点S到目的点T的全部路径称之为解空间的集合Ω，对∀P∈Ω，具有m(m≥2)个非负的性能度量指标f1,f2,…,fm，若P*∈Ω，∀P∈Ω(P≠P*)，在P和P*均满足约束Ci的条件下，对于所有的度量准则均使得fi(P*)≫fi(P)，至少存在一个严格不等式fi(P*)≻fi(P)(i=1,2,…,m)成立，则称P*为多约束条件下多目标问题的Pareto优化解。其中≫和≻是两个偏序关系，分别表示不劣于和优于关系。

服务节点(service node，SN)是一个抽象概念，各服务节点只包含对Web服务的功能描述和接口信息，不绑定具体的Web服务。服务组合按照流程模型的方式来建模，由多个业务或服务节点按照一定的顺序结构组成，每个服务节点对应一个Web服务群(service group，SG)。同一服务群中的多个Web服务具有相同或相似的功能，而QoS不尽相同。一个包含n个服务节点的串行结构服务组合流程模型如图1所示。图中，第i个服务节点SNi含有ni个服务，每个业务节点对应一组具有相同或相似功能的候选Web服务，称之为一个服务群，将其表示为SGi=(Si,1,Si,2,…,Si,ni)(i=1,2,…,n) 。

图1 串行服务组合流程

基于动态Web服务选择的组合服务QoS全局优化问题，即在业务流程的执行过程中，在各业务节点对应的候选服务集合中分别选择针对全局是优化的服务实例，使得整个流程可以执行完成，实现整体的业务流程功能，同时满足组合服务流程的全局服务质量约束，使得多目标达到最优。然而，该问题的求解是一个挑战。

结合前面介绍的MCOOP问题，可把Web服务组合中的动态服务选择QoS全局优化问题进行转化，将其建模为一个求解服务组合流程图中带QoS条件约束的多目标优化路径问题，从而解决服务组合优化问题。每个服务节点所对应的服务群中的服务对应图中的顶点。为方便分析，在图中添加两个虚节点S和T，则图1对应的串行服务组合流程如图2所示。

图2 服务组合流程(串行结构)

文中将提出求解动态Web服务选择QoS全局优化问题的gPSO-GODSS算法。如前所述，服务组合流程常建模为一个基于Web服务的业务流程。业务流程由不同的流程结构组成，常用的流程结构主要有如下四大类型：串联模式、并联模式、选择模式和循环模式。大多数服务组合流程均可由这四种基本模型组合而成。针对这四种基本模型的组合服务QoS参数计算方法，已有一些相关工作[14-15]。为了计算组合服务在各维度的综合质量，文中对四种基本模式的QoS进行聚合[6]。下面，以执行时间T、执行费用C、信誉等级Rep和可靠性R四种服务质量为例介绍其聚合方法。在组合服务CS中，Si为执行组合服务中满足单个业务节点功能的具体服务，Si和CS的QoS服务质量分别建模表示为Q(Si)=(Ti,Ci,Repi,Ri)、Q(cs)=(Tcs,Ccs,Repcs,Rcs)，四种基本模式的QoS参数聚合方法如表1所示。其中，设选择模式中的第i个分支被选择的概率为αi，循环模式中的循环次数为k。

表1 四种基本模式的QoS参数计算方法

3 gPSO-GODSS算法描述

3.1 MCOOP问题描述

在MCOOP问题中，将信誉等级Rep和可靠性R两个质量属性作为约束，要求其值大于一定的值；目标则是使组合服务的执行费用C(P)和执行时间T(P)最小化。因此，该问题可形式化为：

minf(P)={[T(P),C(P)]}

(1)

其中，T(P)、C(P)、Rep(P)和R(P)分别表示服务组合流程的QoS聚合公式，根据第1节表1中的QoS聚合方法计算。

式1表示使T(P)和C(P)两个目标函数同时最小化。在实际场景中，QoS属性的个数可能多于4种，可根据具体的场景选择合适的QoS参数作为优化模型的目标属性和约束属性。因此，文中的MCOOP模型具有可扩展性。

3.2 MCOOP问题转化为单目标问题

在解空间中寻找多目标的优化解，需要有一个评价机制来评估可行解的好坏。文中使用欧氏距离来构造评价函数。首先分别求解单目标的解，将其作为理想点，然后计算可行解对应的组合服务的综合执行时间和执行费用到理想点的欧氏距离作为评价可行解的适应值函数，这样便将多目标问题转化为单目标问题。最后，利用单目标的求解方法求出最优解，并把这些最优解作为多目标的最优解。构造的MCOOP问题的评价函数如下：

(2)

其中，(T*,C*)为一个理想点。由此可知，N个目标就对应一个由N维向量表示的理想点。文中的理想点(T*,C*)是对T(P)和C(P)在各约束条件下分别求出的单目标最优值，它们的计算方法如下：

T*=min{T(P)|Rep(P)≥Rep0,R(P)≥R0}

(3)

C*=min{C(P)|Rep(P)≥Rep0,R(P)≥R0}

(4)

为了求解理想点，根据组合服务QoS属性的聚合计算方法可得，在各候选服务集合中均选择执行时间最短的服务形成的组合服务的综合执行时间为T*；在各候选服务集合中均选择执行费用最低的服务形成的组合服务的综合执行费用为C*，从而得到组合服务的综合执行时间和执行费用的理想值。

3.3 PSO算法

粒子群优化算法(PSO)是一种进化计算技术，由Russel Eberhart和James Kennedy于1995年提出，源于对鸟群捕食的行为研究[16]。算法最初受飞鸟和鱼类等集群活动规律的启发，模拟种群间个体协作来搜索问题的最优解。该算法的优势是易于实现同时又有深刻的智能背景，既适合科学研究，又适合工程应用，且没有许多参数的调节。关于PSO的更多详情可参考文献[17-18]。MCOOP问题是一个NP难问题[17]，因此使用智能进化算法求解是一个合适的选择。PSO算法作为一种启发式的智能优化方法，具有群体寻优、并行计算等特点。因此，可用于各种NP难问题的近似求解。

PSO算法的初始种群为一群随机粒子，在每一次迭代中粒子通过跟踪局部“极值”和全局“极值”(gbest和pbesti)来更新粒子的速度和位置，其迭代公式如下：

νi(t+1)=wvi(t)+c1r1(pbesti-xi(t))+c2r2(gbest-xi(t))

(5)

xi(t+1)=xi(t)+vi(t+1)

(6)

其中,r1和r2是(0,1)之间的随机数；c1和c2是两个学习因子，分别表示将每个微粒向局部最佳位置和全局最佳位置移动的统计加速项的权重。式5的第一项为记忆项，第二项为自身认知项，第三项为群体认知项。为了使粒子维持一定的惯性，在原来速度基础上乘以一个惯性权重因子w，使粒子既能有原来的运动趋势又能探索新的区域。w值越大，全局寻优能力越强，局部寻优能力越弱；w值越小，则反之。w采用较多的是线性递减权值策略进行设置，其公式如下：

(7)

其中，wmax和wmin的经典取值应为：wmax=0.9，wmin=0.4。

在每一维，粒子都有一个最大的限制速度vmax，决定当前位置与最好位置之间区域的分辨率(或精度)。当粒子在某一维度的速度超过了最大限制速度vmax，则将其速度设定为最大的限制速度vmax。因为粒子运动速度过快，则单次迭代时越过的位移会比较大，从而容易越过极小值；相反，如果粒子的运动速度太慢，则单次迭代移动的位移太小，一方面可能越陷入局部极小值，另一方面可能导致长时间无法收敛。

3.4 gPSO-GODOSS算法设计

假设组合服务流程模型中有m个业务节点，第i个业务节点对应ni个服务实例，即SGi=(Si1,Si2,…,Sini)。其中Sij为第i个业务节点对应的某个服务实例的编号。第i个业务节点选择的服务实例表示为xi=Sik，则最终的组合服务方案可形式化为一个m维的向量xi=(xi1,xi2,…,xim)，其中xik∈[1,nk]。

文中考察的速度、位移模型均是离散型数据，因此需要对xi的编码进行离散化，改进原始粒子群算法中粒子的速度、位移模型，保证粒子在整数空间内移动。具体改进的公式如下：

vid(t+1)=int(wvid(t))+∅1+∅2

(8)

xid(t+1)=xid(t)+vid(t+1)

(9)

其中，∅1和∅2为均匀分布的整数。∅1∈[a1,b1]，p{∅1}=1/m1,m1=⎣b1-a1+1」；∅2∈[a2,b2]，p{∅2}=1/m2,m2=⎣b2-a2+1」，其中

式8和式9反映了PSO进化计算的基本思想，并将进化控制在整数空间内。需注意：两式表示的是粒子在某一维的速度和位置变化。式8和式9使得PSO可应用到离散的情形。收敛速度快是PSO的一个优点，但若在起始阶段过快，反而可能会收敛不到全局最优解。为保证PSO不仅收敛速度快，且收敛到全局最优解，文中基于梯度的思想进行改进，指导速度的变化。将粒子的变化速率作为梯度，定义如下：

(10)

将粒子xi在第d维的梯度记为∅3，则

(11)

将梯度信息引入式8，可得：

vid(t+1)=int(wvid(t)+α(t)(∅1+∅2)+(1-α(t))c3∅3)

(12)

式12中包含了梯度的信息，其中α(t)和1-α(t)用来平衡PSO和梯度，c3为一个给定的常数。将结合梯度信息的PSO称为gPSO。文中根据xi，采用Sigmoid函数来定义，如式13所示，函数图像如图3所示。

(13)

由此可见，α(t)的值和xi相关。当粒子的f(xi(t))越大时，α(t)越大，表示gPSO在一个大的解区域进行搜索；当粒子的f(xi(t))越小时，α(t)越小，表示gPSO在一个小的解区域进行搜索，使得gPSO较早达到收敛，且不跳过最优解。

图3 Sigmoid函数图像

基于前面的QoS属性聚合方法和位置向量xi的编码表示，以及基于梯度改进的速度、位移模型，结合基本PSO的智能进化思想，文中提出求解MCOOP问题的改进算法gPSO-GODOSS，具体的过程描述如下：

Step1：将多目标问题向单目标优化问题转化；

Step2：初始化所有粒子的速度和位置，并给出参数赋值；

Step3：根据粒子的位置解码成对应的服务组合方案，计算组合服务的综合信誉等级和可靠性，判断其是否满足约束条件。若满足，则按照评价函数计算该粒子的适应值；否则，赋予该粒子一个最差的适应值即可，并重新优化；

Step4：计算粒子xi的局部最佳位置pbesti。具体方法如下：将其适应值与其本身经历过的局部最佳位置pbesti的适应值进行比较，若更优，则将xi的值赋给pbesti；

Step5：计算粒子xi的全部最佳位置gbest。具体方法如下：将其适应值与所有粒子经历过的全局最佳位置gbest的适应值进行比较，若更优，则将xi的值赋给gbest；

Step6：更新粒子的速度和位置，然后检查新位置和速度的范围，限制粒子的搜索范围和最大速度；

Step7：循环计算所有粒子，即重复Step3～Step6；

Step8：t=t+1；

Step9：判断是否满足终止条件。若不满足，则返回Step3。

gPSO-GODOSS的时间复杂度为O(mN2T)，其中T为迭代次数，N为粒子群规模，m为抽象服务数。

4 实验结果与分析

针对文献[6]中提出的组合服务流程例子进行比较实验，其中计算机配置为Pentium D 3 400 MHz处理器，4 G内存，Windows 7操作系统，算法用Matlab7.0实现。仿真实验的流程如图4所示。

图4 服务组合流程

图4中各服务节点对应一个候选服务集合，每个候选服务集合中的服务实例的QoS各属性值随机生成，并采用极大极小方法标准化。根据第2节中服务组合流程基本模式及QoS聚合方法，构造适应值函数和约束条件。实验中设Rep0=0.8，R0=0.5。其他参数设置如下：c1=c2=2，c3=0.05，itermax=100，w按式7进行计算。实验中的候选服务集合的服务数量规模为10，迭代次数分别为100、200、300、400。文中根据执行时间和收敛速度来评价gPSO-GODSS算法的可行性和有效性，与文献[6]中的多目标粒子群算法PSO-GODSS的执行结果进行对比及分析。

首先，比较每一代种群的平均适应值。如图5所示，PSO-GODSS在第63代收敛到最优值，而gPSO-GODSS在第34代已收敛到最优值，表明gPSO-GODSS的收敛速度优于PSO-GODSS的收敛速度。因此，从收敛速度上看，gPSO-GODSS优于PSO-GODSS。

图5 算法收敛速度的比较

下面比较算法收敛的执行效率，如图6所示。在相同迭代次数下，gPSO-GODSS的执行时间和PSO-GODSS的执行时间非常相近。但由图5可知，gPSO-GODSS的收敛速度较快，找到最优解时的迭代次数更少，故达到收敛的时间开销会更短。因此，从收敛的执行效率上说明了gPSO-GODSS更具可行性。

图6 算法执行时间比较

5 结束语

针对组合服务流程中QoS全局最优动态Web服务选择问题，基于粒子群算法及梯度下降的思想，提出了求解该问题的gPSO-GODSS改进算法。利用粒子群算法的智能优化原理进行优化，通过在PSO的速度更新公式中引入梯度的方法，不仅保证算法快速收敛且收敛到全局最优解。实验结果证明了gPSO-GODSS算法的可行性和有效性，且算法收敛的执行效率和收敛速度均优于传统的离散粒子群算法。