康国胜，刘建勋，唐明董，徐 宇

（湖南科技大学知识处理与网络化制造湖南省普通高校重点实验室 湘潭 411201）

1 引言

Web服务作为一种崭新的分布式计算模式在电子商务、企业应用集成等领域扮演着越来越重要的角色。随着Web服务技术的日益成熟，越来越多稳定易用的Web服务共享在网络上，但单个的Web服务能够提供的功能有限，为更加充分利用共享的Web服务，有必要将共享的Web服务组合起来，提供更为强大的服务功能，加快系统开发的速度，快速满足用户的需求。因此，如何将若干个现存的Web服务整合起来以形成新的、满足用户需求的、增值的大粒度流程服务已成为新的应用需求。

服务组合流程模型由多个抽象的服务结点组成，每个结点只包含功能需求描述，不指定具体的服务调用实例。互联网环境中，存在多个相同或相似功能而具有不同QoS参数(如执行时间、费用等)的Web服务，如何从中选择出满足各服务结点非功能需求的具体服务，形成一个可执行的服务路径来完成用户的需求成为服务组合的关键问题，本文称其为Web服务动态选择问题。

目前，支持QoS的Web服务动态选择的研究大部分基于QoS局部最优的原则[1，2]，即对满足组合流程中单个服务结点功能需求的一组服务，根据服务的各个QoS参数信息进行加权和的排序，并以此为依据分别为各服务结点选择加权和最大的服务来执行其功能。局部最优服务选择方法中为各服务结点独立地选择服务，未考虑服务之间的相互关联性，不能解决服务组合的QoS全局最优问题，如：要求组合流程的可靠性和信誉等级均满足一定条件的情况下执行费用最低、时间最短。对于QoS全局最优问题，目前的研究工作不多[3～7]，其主要思想都是通过将Web服务组合流程的各个QoS参数线性加权为一个单目标，利用线性规划的基本原理来解决服务选择的QoS全局最优问题或者研究求解该模型的各种算法。总之，它们尚存在以下问题：

·把组合流程中的各个QoS参数线性化为一个目标函数，不能解决多目标优化问题；

·由于加权和的结果不仅对权重敏感，而且用户需要对问题有一定的认识，使得加权的方法在实际应用中不可行；

·产生的优化结果为单个解，用户没有选择的余地；

·算法的时间复杂度大，随着候选服务数量的增加，整个服务组合的性能将会受到影响。

所以，研究Web服务组合中基于服务质量的服务选择问题的智能优化算法及其实现显得尤为重要。参考文献[8]针对现有服务选择算法的不足，提出一种解决服务组合中QoS全局最优动态Web服务选择算法，解决了传统方法中难以解决的问题，但算法的执行效率还有待提高。

本文利用差异演化算法，针对参考文献[8]中的服务组合多目标优化问题进行了算法设计和求解。理论分析和实验结果表明，相对多目标遗传算法，本文提出的算法的时间复杂度低，收敛速度快，搜索的全局性更好，能够快速找到全局最佳服务组合决策。一般情况下，服务请求只要求找出满足条件约束的组合服务，而非全局最优服务，这可通过控制迭代次数来实现，因此进化算法更适合解决该类型的组合优化问题。

2 服务组合问题

动态服务组合中，服务组合流程模型由多个抽象的服务结点组成，每个结点对应一个服务群。同一服务群中的服务具有相同功能，不同的QoS。服务动态选择QoS全局最优化问题即在组合流程模型执行过程中，从各服务结点对应的服务群中选择具体的服务组成一个可执行的服务链，使得服务链在满足QoS约束的前提下，多个目标(QoS参数)达到最优。服务组合中的服务动态选择QoS全局最优化问题可转化为一个求解服务组合流程图(service composition graph,SCG)中带QoS约束条件的多目标最优路径问题，即SCG中的多约束条件下多目标最优路径(MCOOP)求解问题[8]。本文研究并提出了求解该问题的DE-GODSS算法。

服务组合流程实际是一个基于Web服务的工作流，与工作流管理联盟(WfMC)定义的4种基本模型(即串联模型、并联模型、选择模型和循环模型)相对应，大部分组合流程均可由这4种基本模型组合而成。基于4种基本模型的组合服务QoS参数、约减规则和QoS计算方法已有一些研究[3，5，8]。大多是计算基本模型的 QoS，通过恰当的聚合函数将各结点的QoS合起来构成组合服务的QoS。本文参考参考文献[8]中的方法对4种模型进行了表示和QoS参数的计算。考虑Web服务的4种QoS参数，即执行时间T、执行费用C、信誉等级Rep和可靠性R。设cs为组合服务，si为组合服务中的单个服务，则si和cs的服务质量分别为

3 DE-GODSS算法

3.1 MCOOP问题的形式化描述

为方便说明，本文将组合服务的执行时间和费用作为两目标准则，信誉等级和可靠性作为两约束条件，Rep0和R0分别表示组合服务所要求的最低信誉等级和最低可靠性，则一个带约束的多目标服务组合优化模型的形式化描述如下：

其中，P 为 Web服务组合方案，T(P)，C(P)，Rep(P)和 R(P)对应服务组合流程的QoS参数计算式，根据参考文献[8]中定义的服务组合模型QoS的聚合方法获得；式(1)表示取向量极小化，即使T(P)和C(P)两个目标函数同时极小化。QoS参数的考虑并不限于这些，主要思想是将它们看作优化模型的目标函数或约束条件，故本模型可推广到任意多个目标函数和约束条件。

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

求解多目标规划的最基本方法为评价函数。它的基本思想是借助几何或应用中的直观背景，构造评价函数，将多目标问题转化为单目标优化问题，然后利用成熟的单目标求解方法求出最优解，并把这种最优解当作多目标的最优解。本文采用理想点法来构造MCOOP问题的评价函数。

其中，（T*，C*）为一个理想点。理想点是对 T(P)和 C(P)分别求出约束最优值得到的，即：

对该多目标服务组合优化问题，根据组合服务QoS的聚合方法可知，在各服务群中均选择执行时间最短的服务形成的组合服务的执行时间为T*；同理，在各服务群中均选择执行费用最低的服务形成的组合服务的执行费用为C*。

3.3 DE-GODOSS算法设计

差异演化(DE)[9,10]算法是由Rainer Storn和Kenneth Price于1996年提出的一种优化技术。它具有记忆个体最优解和种群内信息共享的特点，其基本思想是利用从种群中随机选取的两个个体的差向量作为第三者的随机变化源，生成变异个体，然后变异个体和目标个体通过交叉操作生成新个体。若新个体的适应度优于目标个体，则新个体取代目标个体进入下一代；否则，目标个体保留到下一代。因此，它主要包括4个基本步骤：种群初始化、变异操作、交叉操作和选择操作。差异演化算法具有简单易用、收敛速度快、控制参数少等特点，在各领域得到了广泛的应用[11]。

基于差异演化算法，对第 3.2节的优化模型设计相应参数。对于存在m个服务结点的组合服务流程，第i个服务结点对应的服务群中有ni个服务，即SGi=(si,1,…,si,ni)(i=1,…，m)，为某个具体服务在该服务群中的编号。为第i个服务结点选择一个具体的服务xk=sik，则组合服务方案构成一个 m 元组 Xi=(xi1,xi2,…，xim)，xik∈[1,nk]，每个元组对应m维空间中的某一位置。

从Xi的编码方式可看出，本文研究的组合优化问题是离散型问题，方便差异演化算法的变异和交叉操作。在差异演化算法中，根据基向量、差向量个数及交叉方法的选择不同，分为10种不同的变异策略组合[11]。本文结合组合服务的特点选择DE/best/1/bin变异策略，其变异操作的计算式如式(5)所示：

其中，Xbest(t)表示第 t代种群中的最好个体；Xp1、Xp2是种群中随机选出的两个互不相同的个体，且i≠p1≠p2≠best。由此可知，该变异策略的种群规模必须大于4，否则无法进行变异操作。Xp1(t)-Xp2(t)为差异化向量；F为缩放因子，用于控制差向量的影响大小，取值在[0,2]。本文的组合优化问题属于离散问题，因此取F=1。Hi(t)为产生的变异个体。

为增加种群的多样性，差异演化算法将变异向量和目标向量按如下式子进行交叉：

其中，randij是在 [0,1]的随机小数；CR为交叉概率，CR∈[0,1]；为在[1,m]的随机整数，这种交叉策略可确保Vi(t)中至少有一位分量与目标向量Xi(t)不同。

和其他演化算法一样，差异演化也是通过“优胜劣汰”的选择操作来保证算法不断向最优解进化。本文将式(3)作为最小化的目标函数，则差异演化算法的选择策略可由式(7)来表示：

通过以上描述的差异演化的变异、交叉和选择操作使种群演化到下一代，反复循环演化，最后种群将达到最优。因此，结合差异演化算法的优化思想和服务组合中的动态服务选择问题，设计出求解MCOOP问题的DE-GODSS算法，算法的描述如下。

（1）将MCOOP问题转化为单目标优化问题，并设置算法相关控制参数。

（2）初始化种群 P(0)，t=0。

（3）计算种群 P(t)中每个个体的适应度，并根据适应度选择出最优个体。

（4）从种群P(t)中随机选出与当前个体不同的两个个体。

（5）按式(5)进行变异操作，生成变异向量。

（6）对变异向量按式(6)执行交叉操作，生成新个体。

（7）计算新个体的适应度，并与之前的最优个体的适应度比较。若优于之前的最优个体，则将当前个体作为最优个体。

（8）按式(7)执行选择操作。当新个体的适应度优于目标个体时，新个体代替目标个体进入下一代种群P(t+1)；否则，目标个体继续保留在下一代种群中。

（9）重复（4）到（8），直到种群中所有个体都执行完毕。

（10）t=t+1。

（11）判断是否满足结束条件(迭代次数)，不满足则返回（4）。

在计算个体适应度时，先将个体解码成具体的组合服务方案，再判断该方案是否满足约束条件。若满足，则按式(3)计算该个体的适应度；否则，赋予该个体最差的一个适应度。算法的时间复杂度主要由差异演化算法进行迭代的时间复杂度组成。假设迭代次数为T，种群规模为N，服务结点数为m，则算法总的时间复杂度为O(TN2m)。整个算法过程的时间复杂度主要与迭代次数、种群规模和组合服务中的服务结点数有关，而与各服务结点对应的服务群规模无关。而多目标遗传算法GODSS的总时间复杂度为O((mN2+NN*)T)，其中N*为辅助种群规模。因此，较已有的多目标遗传算法，本文设计的差异演化算法的时间复杂度较低，且无需另外设计辅助种群。GODSS算法在每次迭代赋予染色体适应度时，需对个体之间的优于关系进行排序，增加了算法的时间复杂度，而本文采用理想点的方法很好地将多目标向单目标转化，只需将个体适应度同目标个体的适应度和最优个体的适应度比较即可。因此，从理论分析可知，DE-GODSS算法规则简单，易于实现。在相同迭代次数下，算法的执行时间更少，证明该算法的可行性。

4 仿真实验及分析

本节针对参考文献[8]中的例子进行仿真实验，实验的组合服务流程如图1所示。

流程中的每个服务结点对应一个服务群，各服务群中服务的QoS参数在一定范围内随机生成，并使用极差变换方法对其进行标准化。对于信誉等级，利用模糊数学中隶属度的方法进行量化。根据服务组合流程基本模型以及QoS聚合方法，得到目标函数和约束函数。由基本模型组合服务的QoS聚合方法可知，组合服务的可靠性约束不宜设置太大，故本章中设，Rep0=0.8,R0=0.5。第3节中，已从理论分析的角度分析了本文提出算法的时间复杂度优于已有的多目标遗传算法，证明了该算法的可行性。进一步地，本节实验通过比较算法的收敛速度来验证DE-GODSS算法的有效性。实验考虑各服务群规模为10个，种群规模为100个，迭代次数为100次，与多目标遗传算法GODSS比较每一代种群的平均适应度。如图2所示，发现DE-GODSS算法的收敛速度明显优于GODSS算法。GODSS算法在71代收敛到最优值，而DE-GODSS算法在34代就已经收敛到了最优值，说明了DE-GODSS算法的有效性。

5 结束语

针对组合服务中QoS全局最优动态Web服务选择问题，基于差异演化算法，提出并设计了求解该问题的DE-GODSS算法。将服务动态选择全局优化问题转化为一个带QoS约束的多目标服务组合优化问题，通过理想点的方法将多目标向单目标转化，利用差异演化算法的智能优化原理进行优化，通过控制迭代次数，可产生多组满足约束条件的优化服务组合流程，能够更好地满足用户的需求。理论分析和实验结果表明了该算法的可行性和有效性，该算法的时间复杂度和收敛速度优于已有的多目标遗传算法。

1 Liu Y,Ngu A H,Zeng L Z.QoS computation and policing in dynamic Web service selection.In： Proceedings of the International World Wide Web Conference,ACM,Manhattan,NY,USA,2004

2 Casati F,Ilnicki S,Jin L J,et al.Adaptive and dynamic service composition in eFlow.In：12th InternationalConference on Advanced Information Systems Engineering，Stockholm,Sweden,2000

3 Zeng L,Benatallah B,Dumas M,et al.Quality driven Web services composition.In:Proceedings of the International World Wide Web Conference.ACM,Budapest,Hungary,2003

4 Ardagna D,Pernici B.Global and local QoS guarantee in Web service selection.In:Third Internation Conference on Business Process Management,Vienna,Austria,2006

5 Alrifai M,Risse T.Combining global optimization with local selection for efficient QoS-aware service composition.In:ACM,Madrid,Spain，2009

6 邢庆秀.支持QoS全局优化的动态Web服务组合问题研究.中国海洋大学硕士学位论文,2008

7 范小芹,蒋昌俊,方贤文等.基于离散微粒群算法的动态Web服务选择.计算机研究与发展,2010(1):147～156

8 刘书雷,刘云翔,张帆等.一种服务聚合中 QoS全局最优服务动态选择算法.软件学报,2007,18(3):646～656

9 Storn R,Price K.Minimizing the real functions of the ICEC'96 contest by differential evolution.In：Proceedings of the IEEE Conference on Evolutionary Computation.Nagoya,Japan,1996

10 Storn R,Price K.Differential evolutionc¨a simple and efficient heuristic for global optimization over continuous spaces.Journal of Global Optimization,1997,11(4):341～359

11 武志峰.差异演化算法及其应用研究.北京交通大学博士学位论文,2009