基于改进PSO用户习惯感知的服务组合

赵 阳，郭 星

（安徽大学 计算机科学与技术学院，安徽 合肥 230031）

基于改进PSO用户习惯感知的服务组合

赵 阳，郭 星*

（安徽大学 计算机科学与技术学院，安徽 合肥 230031）

随着Web服务数量的急剧增加，如何动态地从大量候选服务集中选择出合适的Web服务，并组合成能够完成复杂增值业务过程需求的组合服务，是服务组合优化领域亟待解决的问题。本文提出了一种基于PSO的具有用户习惯感知能力的优化算法，并应用于离散服务组合优化问题。该算法通过对用户习惯的感知进行服务组合优化，在传统PSO算法的基础上，根据粒子与用户习惯的相似度来控制粒子收敛，使寻优过程具有用户习惯感知能力。大量实验结果验证了该算法的可行性和有效性。

服务组合；PSO；用户习惯感知；服务质量

随着网络技术的飞速发展，出现了具有良好封闭性、松散耦合和高度可集成等特点的Web服务，越来越多的企业将技术、资源以及应用加入到Web服务中。不过单独的Web服务所能够实现的功能是有局限性的，而用户提出的需求往往不能完全得到满足，Web服务组合就是为了解决该类问题。Web服务组合是通过利用Web服务的松耦合特性以及高度可集成的能力，把原子服务无缝且快速灵活地组合在一起，形成新的新增服务，而新的组合服务可以满足用户的复杂需求，而原子服务是目前已经存在的独立的简单的Web服务[1]。近年来Web服务的种类和数量越来越多，大量功能属性相同的服务存在于网络上，但是这些服务在非功能属性即服务质量（quality of ser-vice,QoS）上是不相同的。怎样将多种类别的Web服务组合起来，形成一组新的服务组合，并且要高效的完成这一组合过程是一个新的研究热点[2,3]。同时，如何在海量Web服务中，高效的选择出合适的服务来满足用户需求也成为了一个迫切需要解决的问题。

倪晚成等[4]对Web服务组合的研究现状进行了综述，对典型Web服务组合方法进行了分类，对Web服务的评价模型进行了论述。AgFlow[5]提出了五维QoS评价模型。李金忠、夏洁武和唐卫东等[6]提到有关个性化的Web服务组合问题，必要的个性化组合可以满足特定用户的特定需求，而个性化的服务组合问题也是一个亟待解决。在服务组合选择过程中，同时考虑用户的偏好和服务的QoS属性的Web服务组合算法仍然是以后研究的难点。而目前的服务组合算法大多从如何快速高效寻优的角度出发来解决服务组合问题。

粒子群优化算法（PSO）是当前较为流行的应用于基于QoS的Web服务组合问题上的智能算法，相比其他智能算法具有参数少和收敛快的特点。刘莉平等[7]提出一种基于粒子群算法的解决Web服务组合的算法，重新定义了粒子的位置、速度和运算，利用粒子群算法的智能优化原理快速得到一组优化的服务组合，并证明了算法的可行性和有效性。文献[8]提出一个改进PSO算法，设计了一种新的惯性权重，在粒子搜索的不同阶段采用不同的公式得到惯性权重，并且通过实验证明了该算法比基本粒子群算法有更好的收敛性。

常见Web组合算法都没有考虑用户偏好，本文从用户习惯感知的角度出发，结合粒子群算法，提出一种能感知用户习惯的Web服务组合算法，对于某一用户，在已知某一组服务组合是其习惯使用组合的情况下，依据该用户的这一习惯来进行寻优，从而解决用户习惯感知的服务组合问题。

为解决此类用户习惯感知的服务组合问题，必须在寻优的同时感知用户习惯。粒子群算法具有容易实现并且收敛速度快的特点，对于参数选择已有较为成熟的理论，所以本文基于粒子群算法提出一种用户感知的服务组合算法。

1 Web服务组合

为了清晰的描述本文的服务组合问题，此节给出在描述服务组合问题中涉及到的相关定义以及基于QoS的服务组合模型。

1.1 相关定义

定义1（服务类，S） 服务类是指一组具体服务的抽象，并且同一服务类的服务具有相同的功能，而不同具体服务之间具有非功能属性上的差异。由满足这些要求的多个服务组成的服务类是服务组合的基本组成单元。用此式子来抽象表示第i个服务类：，其中Si包含m个具体候选服务。

定义2（服务组合，CS） 服务组合是由多个服务组成的一组服务，这些服务是来自不同的服务类中的某一具体服务，将这一组服务称为服务组合。可将其抽象表示为：CS={S1,…,Si,…,Sn} ，表示服务组合由来自n个服务类的服务组成。

1.2 基于QoS的服务组合问题模型

Web服务组合一般有4种基本结构。因为除顺序模型外的另外3种模型都可以转换为顺序模型[9]，所以本文采用顺序模型来研究服务组合的优化问题。假设本文研究的Web服务有4个QoS参数，分别为响应时间（T）、服务费用（C）、可用性（A）、信誉（Rep）。各种流程的QoS计算模型如表1所示。

表1 服务组合QoS计算公式

对QoS的各项属性，有的属于正影响，值越高越符合用户需求，而有的属于负影响，值越小越符合用户需求。另外，各项属性的取值不是一个数量级。为解决这两个问题，必须进行分类和归一化操作。本文按照如下公式进行归一化操作：

其中，和分别为Ti对应的所有Si中QoS指标最大值和最小值。按照各项属性属于成本型或效益型来选择公式进行转换。组合服务的适应度评价函数定义为：

其中qk为归一化转换的第k个QoS属性值。wk为第k个属性对应的权值。

2 UHPPSO算法描述与模型

2.1 标准粒子群算法

粒子群优化（particle swarm optimization,PSO）算法最早由 Eberhart和 Kennedy[10]共同提出。在基本粒子群算法中，每个个体成为一个“粒子”，代表一个潜在的解。每个粒子的飞行的方向和下一次的位移由该粒子的飞行速度所决定。对于整个粒子群，每次粒子都会依据该粒子的历史最优解pi和整个群体曾到达的历史最优解pk来进行更新，与鸟群搜寻食物的过程十分相似。例如，如果搜索空间为n维，该空间的某一粒子i的位置xi=(x1，x2，x3…，xn)，速度vi=(v1，v2，…，vn)，历史最优解pi=(p1，p2，…，pn)，全局最优解pg=(p1，p2，…，pn)，则i的速度和位置的更新公式为[10-13]：

其中t为当前进化次数，c1，c2被称作学习因子，作用是决定pi，pg对新速度的影响能力，r1和r2为[0,1]区间上的均匀分布的随机变量。Shi和Eberhar在1998年正式引入惯性权重的概念[11]。为了更好的控制算法全局的寻优能力，在速度公式中引入一个惯性权重w，将式（3）变为：

式（4）和式（5）合称为标准粒子群算法（standard particle swarm optimization,SPSO）。有很多相关论文中提出惯性权重策略来改进基本粒子群算法的性能,通过惯性权重的大小来控制算法的收敛速度。采用最多的是Shi提出的线性递减惯性权重值[10]：

其中wmax，wmin分别为初始惯性权重的值和最终的惯性权重值，一般取wmax=0.9，wmin=0.4。

2.2 编码方案

服务组合CS可抽象表示为CS=(S1,S2,…,Si,…,Sn)，S表示每个任务对应的服务类，而粒子群算法中的每一个粒子的位置X=(x1,x2,…,xi…xn)，对应一个服务组合，其速度决定飞行方向和下一步位移，由速度得到新的位置后，将对应的服务组合通过公式（2）计算出该位置的适应度。运用粒子群算法进行求解的基本思想如下：初始化一定数量的初始粒子，每个粒子表示一个可能的服务组合解。在粒子群的迭代过程中，粒子根据全局最优解和粒子本身经过的历史最优解进行更新。

2.3 UHPPSO算法思想与模型

假设用户曾经选择过的服务组合对应的粒子为A=(a1,a1,…,ai,…,an)，将此粒子设置为比较粒子，用以感知用户的习惯。在计算惯性权重大小时，考虑当前粒子位置与比较粒子A的相似程度，得到对应的惯性权重值，用以控制粒子收敛。

2.3.1 粒子间相似度

在给出新的惯性权重公式之前，先定义粒子间相似度的计算方法。

假设有两个粒子：粒子P和粒子Q，其粒子间的相似度用Sim(P,Q)表示。每个组合对应的组合服务可按表1计算出组合服务的QoS值，本文用一个四元组QoS=(Time,Cost,Avai,Rep)表示，粒子P、Q间的相似度用其对应的服务组合QoS值间的4维欧几里德距离表示[14]。4维空间的欧几里德距离计算公式为：

其中x1，x2，x3，x4分别为P的四项 QoS 属性值，y1，y2，y3，y4分别为Q的四项QoS属性值。P、Q间的欧几里德距离越大，二者间的相似度越低。由此定义粒子间相似度的计算公式：

时，二者的各属性完全相同，此时Sim(P,Q)=0.5。由于QoS经过归一化处理后的范围是[0,1]，所以d的范围是[0,2]，

时，Sim(P,Q)=0.25。所以P、Q二者间相似度的范围是[0.25,0.5]。

2.3.2 用户习惯感知的惯性权重策略

为了感知用户习惯，本文提出的UHPPSO算法将粒子间相似度与传统PSO算法中的惯性权重公式结合，速度更新时，使用如下改进的惯性权重公式来进行粒子的速度更新可以达到感知用户习惯的目的。

用户习惯感知的惯性权重策略在Shi提出的线性递减惯性权重公式，即式(6)的基础上加入相似度，使算法更趋向于收敛于与比较粒子A相似度更高的点，所对应服务组合更符合用户的习惯。为得到此效果，对式(6)做出如下改进：

该式保留了惯性权重的线性递减性质的同时，引入了相似度，使得算法获得了用户习惯的感知能力。其中P为当前粒子，A为比较粒子。二者间相似度越高，w值越小，算法收敛越快，反之收敛越慢。即算法更倾向产生和用户习惯更相似的组合服务。

2.4 算法流程

基于上述思想和模型，本文改进算法的归纳表述如下。

UHPPSO算法

Step 1：置当前迭代次数t=0。初始化m个粒子的初始位置和速度；

Step 2：设定一个比较粒子A表示用户曾经选择过的服务组合；

Step 4：初始化每个粒子的历史最优位置、历史最优适应值。根据所有粒子的历史最优位置、历史最优适应值，计算种群的全局最优位置，全局最优适应值；

Step 5：由式(8)计算粒子每个粒子P与A的相似度Sim(P,A)；

Step 6：根据式(5)、(9)更新粒子速度及位置；

Step 7：计算出新的到的粒子的适应度；

Step 8：对该粒子的历史最优位置和全局最优位置进行更新；

Step 9：判断是否达到最大迭代次数，若达到则结束，否则转至Step 5。

3 仿真实验与分析

3.1 实验数据与环境

为了验证本文所提出的算法在服务组合应用中的性能，本文进行了大量的实验。由于其它几类服务组合模型都可以转换为顺序模型，本文使用顺序模型在QWS数据集上进行了多次仿真实验。该数据集由Zeng等提供[5,15]，包含250 0个Web服务的QoS属性。实验只取其中的服务的响应时间、调用一次服务所需的花费、服务的可用性以及服务的信誉四个评价指标。

实验硬件环境为：Intel Core i5-4200U CPU，4.00 GB RAM。实验软件环境为：Matlab 6.0，Windows7 64位操作系统。

3.2 实验参数设置

实验参数设定如表2所示，本文的实验结果为实验次数N=20时计算得到的平均实验数值。实验比较了标准粒子群算法与本文算法的以下各项性能。

表2 实验参数设定

3.3 可行性

为了验证本文算法的可行性，模拟2.3节的场景，在QWS数据集上进行了相应的实验。接下来将本文的UHPPSO算法与标准PSO算法进行比较。将任务数分别固定为5,10,15,20时，增加候选服务的数量。实验结果如图1所示。

根据适应度评价函数，以及2.2节归一化操作公式可知，所有指标的数值均是越小越好，由此计算出的适应度越低，表示解的质量越好。所以，从图1可看出，随着候选服务数的增加，解的质量越来越高，并且，通过比较各个子图，在不同任务数下，子任务数越少，解的质量越高。并且UHPPSO算法的解的质量明显高于PSO算法。可以看出，本文算法通过采用线性递减的惯性权重和粒子间相似度的方法来控制粒子收敛，是可行的，并且增强了算法的寻优能力。

图1 算法在不同候选服务数下的寻优性能对比

图2 用户习惯对结果的影响

3.4 用户习惯的影响

文章开头提出的服务组合应用的情景下，为了验证本文算法在用户习惯感知方面的优越性，本文就算法的解的用户感知情况将UHPPSO算法与PSO算法进行了对比。用最终解与比较粒子的粒子间相似度来衡量其感知能力，在不同任务数下的实验结果如图2所示。

由粒子相似度定义可知，解与比较粒子间的相似度越高，说明算法的用户习惯感知能力越好。所以从图2可以看出，UHPPSO算法寻得解的用户习惯感知能力要明显优于PSO算法，验证了该算法的用户感知能力。在考虑用户的选择习惯时，本文提出的算法在用户习惯感知方面具有明显的优越性。通过图2的各个子图可以看出，这一性能在候选服务数少时更为明显。随着候选服务数的增加，其感知能力也会随之下降。

以上实验结果验证了本文算法的可行性以及算法对用户习惯感知能力。本文算法在寻优性能和用户习惯感知能力上明显的优于PSO算法。本文提出的算法在提高解的质量的同时，增加了用户习惯的感知能力。

4 总结

本文从解决考虑用户习惯的服务组合问题出发，提出了一种基于改进PSO的UHPPSO算法。在描述算法时，定义了粒子间相似度的概念，并使用相似度来感知用户习惯，使得算法的寻优过程具有用户感知能力，最后通过实验验证了本文算法的可行性和用户感知能力。

[1]Alrifai M,Risse T,Nejdl W.A hybrid approach for efficient web service composition with End-to-End QoS constraints[J].ACM Transactions on the Web,2012,6(2)：1-7.

[2]范小芹，蒋昌俊，方贤文，等.基于离散微粒群算法的动态Web服务选择[J].计算机研究与发展，2010，47（1）：147-156.

[3]刘书雷，刘云翔，张 帆，等.一种服务聚合中QoS全局最优服务动态选择算法[J].软件学报，2007，18（3）：646-656.

[4]倪晚成，刘连臣，吴 澄.Web服务组合方法综述[J].计算机工程，2008，34（4）：79-81.

[5]Zeng L Z,Benatallah B,Ngu A H,et al.QoS-aware middleware for Web Services Composition[J].IEEE Transactions on Software Engineering,2004,30(5)：311-327.

[6]李金忠，夏洁武，唐卫东，等.基于QoS的Web服务选择算法综述 [J].计算机应用研究，2010，27（10）：3622-3638.

[7]刘莉平，陈志刚，刘爱心.基于粒子群算法的Web服务组合研究[J].计算机工程，2008，34（5）：104-106,112.

[8]Yuan Q U.改进粒子群优化算法在服务组合中的应用[J].计算机工程，2011，37（17）：130-132.

[9]Cardoso J,Sheth A,Miller J,et al.Quality of service for workflows and web service processes[J].Web Semantics：Science,Services and Agents on the World Wide Web,2004,1(3)：281-308.

[10]Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C]//Micro Machine and Human Science,1995.MHS'95,Proceedings of the Sixth International Symposium on,1,1995：39-43.

[11]Shi Y,Eberhart R C.A modified particle swarm optimizer[C]//The 1998 IEEE International Conference on,1998：69-73.

[12]ShiY,Eberhart R C.Parameter selection in particle swarm optimization[C]//International Conference on Evolutionary Programming.Springer Berlin Heidelberg,1998：591-600.

[13]Poli R,Kennedy J,Blackwell T.Particle swarm optimization[J].Swarm Intelligence,2007,1(1)：33-57.

[14]肖文娟，段玉聪.基于时间序列的感知QoS的云服务组合[J].计算机工程与科学，2014，36（11）：2061-2066.

[15]Zeng L,Benatallah B,Dumas M,et al.Quality driven web services composition[C]//Proceedings of the 12th international conference on World Wide Web,2003：411-421.

User’s habit-perceptive service composition based on improved PSO

ZHAO Yang,GUO Xing*
(School of Computer Science,Anhui University,Hefei Anhui230601,China)

With the sharp increase in the number of web services,it has become a problem to be solved in the service composition optimization field how to select suitable web services dynamically from a large number of candidate services sets,and combine them into a composite service to meet the complex need of value-added business process.This paper proposes a user’s habit-perceptive optimization algorithm based on PSO,and applies it to the discrete service composition optimization problem.The algorithm optimizes the service composition through user’s habits perception.Based on traditional PSO,it controls the particle to convergent according to the similarity between the particle and user’s habits,thereby optimizing the user’s habit-perceptive process.The feasibility and validity of the proposed algorithm were verified with a large number of experimental results.

service composition;PSO;user’s habit-perceptive;quality of service

TP393

A

1004-4329（2017）03-053-06

10.14096/j.cnki.cn34-1069/n/1004-4329（2017）03-053-06

2017-04-14

国家支撑计划（2015BAK24B01）资助。

郭 星（1983- ），男，博士，讲师，研究方向：服务计算、云计算、智能算法。Email：guoxing@ahu.edu.cn。