基于改进粒子群算法的组合服务优化

邓春玲

（重庆师范大学 计算机与信息科学学院，重庆 401331）

摘要：针对Web组合服务的选择问题，本文提出了一种基于遗传算法的粒子群算法来寻找最优组合服务。首先，设计了 Web 服务组合模型对组合服务进行形式化描述，考虑了服务执行代价、时间、可用性和可靠度四个因素；接着，针对基于服务质量的Web服务组合特点，借鉴运动学速度分解原理对粒子每维的速度进行相应分解，采用目标向量指导粒子的飞行；然后针对组合服务数量庞大问题，提出了候选服务筛选的思想；最后针对粒子容易陷入停滞状态的问题，引入了遗传算法的交叉策略，同时针对粒子群容易陷入局部最优的问题，采用了调整参数来改善。实验结果表明，基于改进粒子群优化的组合服务算法可靠、有效，能够获得综合较好的解。

关键字：服务质量  粒子群优化算法  web服务  组合服务优化

中图法分类号：TP393   文献标识码：A    

  Optimization of Composition Service Based on Modified Particle Swarm Optimization

 Deng Chun-ling

(College of Computer and Information Science,Chongqing Normal University,Chongqing 401331)

Abstract:For the selection of Web composition service,This paper proposes a Particle Swarm Algorithm based on Agenetic Algorithm to find the optimal combination of service. First, the design of Web service composition model to formally describe a combination of service, taking four factors which includes the service execution cost, time, availability and reliability into account.Second , a combination of features for Web services based on , leaming the principles of kinematics speed decomposition, the rate of each dimension of a particle are decomposed correspondingly. Using  target vector to guide particles flying. Third,for the huge number combinations of service problem, proposed the screening idea of candidate services. Finally, for the particle easily stalled issues, The paper introduced crossover strategy of Genetic Algorithm, while particle swarm easy to fall into local optimum, used the adjusted parameter to improve. Experimental results show that the algorithm-Optimization of Composition Service Based on Modified Particle Swarm Optimization is reliable and effective, it is able to get a better solution which integrated .

Key words:; particle swarm optimization; web services; combination service optimization

1引言

近几年来，web服务得到了快速的发展。Web服务是一种基于网络的具有完全开放、分布式、松散耦合、自描述和高度可集成能力等特征的模块化应用。它能够被Internet上的其他软件组件调用。

随着网络技术的快速发展，web服务的需求也越来越高，但由于单个web服务的功能有限，在一些功能方面很难满足用户或企业应用集成的需求，而两个或者多个web服务可以组合为满足用户特定需求的多功能web服务。因此一种新兴的web应用模式即web服务组合被兴起。而每个web服务组合是由多个抽象服务组成，一个抽象服务可能有多个web候选服务提供者，这样就造就了服务组合数相当庞大。那么，如何从海量的web服务组合数中快速地选择能够满足不同用户需求的、增值的复杂服务组合，已经成为服务计算领域当前的一个新的应用需求和研究热点。本文在文献[6]的基础上，引入遗传算法的交叉思想，提出了一种基于改进粒子群算法的web服务组合优化。该算法以本文所提到的所有属性和作为目标向量,并根据运动学原理，把速度进行分解，每一分速度代表一种属性，则可以利用分速度来计算下一次迭代该维对应的属性，从而获得相应的web服务，最终获得满足用户需求的web服务组合。本文总体设计思想如图1所示：

图1  本文总体设计图

2 Web服务组合建模及属性处理

    Web服务组合是将多个web服务组合在一起而形成的一种多功能、增值的、复杂的服务。它能完成复杂的业务，满足用户的多需求。

定义1  Web服务质量是评价web服务的一个重要指标。可以将web服务质量描述成为一个四元组，即。

time为服务的执行时间；

执行费用cost：表示调用服务一次所需要花费的费用；

可用性available：表示web服务在某个时期内可用的概率，其值为：

T_a表示服务能执行的时间，T_b表示服务总的被占用的时间；

     可靠度reliable：指服务被成功调用的概率，其值表示为：

N_a指服务被成功调用的次数，N_s为服务总的被调用的次数。

2.1 服务组合建模

     Web服务组合模型可用如下二元组进行表示：,S为组合任务的集合即该组合服务所需的抽象服务的集合，可表示为，而对于每个任务，，可以由k个候选服务即中的任意一个来完成，如图2所示：

                     图2  web服务组合模型

为每个候选服务的质量。

2.2 Web服务组合属性分析

    如图1所示的服务组合模型，其组合服务的属性与其组合成员的属性是是密切相关的，组合成员的属性决定了组合服务的属性，如组合服务的执行时间由成员服务的执行时间之和决定。如图1所示 ，假设一个组合服务中需要个成员服务，则定义组合属性与成员属性的关系如表1所示：  

表1  组合服务的属性值

2.3 基于属性的web服务筛选

Web服务的属性分为正负两类，正属性的值越大，服务质量越好，如可靠性和可靠度，而负属性则相反，如执行时间和服务代价。基于此，在此设置一个阈值作为候选服务的筛选标准，阈值的设置由如下公式所得：

                                                               （1）

                                                                 （2）

其中为第i个抽象服务的k个候选服务的属性之和，为第个抽象服务的候选服务数，为第个抽象服务的第个属性的平均值，为第个抽象服务的第个候选服务的第个属性，为每个候选服务的第个属性值与相应的抽象服务的第个属性平均值的比值，在此它有三种情况：大于1，等于1，小于1。基于此，对于正属性来说：当时，将该服务继续作为候选服务，当时，将此类服务从候选服务中删除；对于负属性来说：当时，将此类服务从候选服务中删除，当时，将该服务继续作为候选服务。

2.4 属性的预处理

     基于3.3节，将剩下的候选服务的正负属性进行预处理。基本思想为：结合用户性能需求，对每个属性设置一个权重。这里为了满足目标函数值越大，服务性能越好的要求，在此设置负属性的权重为负，正属性的权重为正，这样就满足属性值越大，服务性能越好，且用户对服务的相应性能要求越高，权重的绝对值设置越大。

3基于测试数据的服务评价

    web服务性能是评价web服务的重要指标，本文采用WSTest^[13]方法对服务的各个性能进行测试。WSTest测试程序包括六个部分：（1）、输入WSDL地址，解析WSDL文档，得到web服务信息。（2）、初始化被测web服务需要输入的参数值即生成测试数据^[14]。（3）、发送web服务请求。（4）、传输soap请求，返回结果。（5）、解析soap消息。（6）、得到服务各性能指标值。

4算法改进

4.1 基本粒子群算法

粒子群算法是于1995年由Kennedy和Eberhart根据鸟群寻食过程的启发而提出的一种群智能优化算法，其核心思想是根据群体间的信息共享和单粒子个体的自身经验来驱动粒子朝着有利于自己优化的方向运动，经过多次迭代，反复更新粒子的速度和位置，最终找到粒子的最优位置。设有个粒子，为第粒子的维位置矢量；为粒子的飞行速度，即粒子的移动距离。则粒子的速度、位置更新公式分别为：

            (3)

。                     (4)

其中，为迭代次数；表示第个粒子在维中第次迭代的速度，它由当前迭代的速度，粒子在i维空间中第次迭代的位置，粒子的个体极值以及群体最优值共同决定；为惯性权重，其具有平衡局部搜索和全局搜索的能力；，为加速因子，它使粒子具有自我总结和向群体中优秀个体学习的能力，从而向自己的历史最优点和群体最优点靠近；，为之间的随机数，用来保证种群的多样性。

4.2求解web服务组合优化的粒子群优化算法

4.2.1基于遗传算法的粒子群优化算法

在本文中采用遗传算法中交叉算子的思想，将粒子进行交叉，获得更优良的粒子。主要思想为：将粒子初始化后，计算每个粒子的适应度值，按适应度值从小到大排序编号，并随机产生一个位置，然后按第个粒子与第个粒子的到维的相应属性值进行交叉，第2个粒子与第个粒子的到维的相应属性值交叉，依次类推，直到粒子交叉完成，获得N个子粒子，计算子粒子的适应度，若子粒子的适应度大于父粒子的适应度，则用子粒子代替父粒子，获得新的粒子种群。

4.2.2算法参数的改进

因为可以影响粒子的局部和全局搜索能力，当较大时，粒子的全局搜索能力较强，而较小时，粒子的局部搜索能力优于全局搜索能力。在早期，我们需要粒子具有范围较广阔的搜索能力，以使粒子不过早陷入局部最优解，而获得更好的解。而在后期则需粒子具有较强的局部搜索能力，从而获得较精确的解，因此，在此将进行非线性变化，使其按正弦函数先增后减的改进粒子群。

                    (5)

式中t为当前迭代次数，T为粒子最大迭代次数。

4.2.3粒子编码规则

组合服务由n个web服务组成，而粒子群算法中每个粒子都代表着一个潜在的解，因此可用一个具有n维（每一维具有个属性，）的粒子表示服务组合的一个解。而粒子的每一维对应组合中某一服务实例属性，通过每个属性值即可对应一个候选web服务，就相当于一个粒子代表一个组合，粒子的每一维则对应每个组合服务成员。并将粒子的速度分解为4个分量，分别代表服务的四个属性，因为速度表示粒子的移动距离，则速度的每一个分量表示服务对应的每个属性的改变量，最后通过每维粒子相应的属性值来定位服务位置。那么粒子的速度、位置更新公式则应表示为：

                             (6)

                                  (7)

4.2.4粒子的适应度计算

服务组合中，一个粒子代表一个服务组合的解，则把粒子的每一维服务属性参数值代入式，，，，即可得到服务组合对应的聚合属性值，因此可以将 Web 服务组合问题模型描述为以下组合优化问题：粒子的适应度可结合用户偏好表示为：,即

。

,,,为用户对服务性能要求而相应设置的目标权重。要求如3.4节所描述，且。

4.3  算法步骤

输入：种群规模N，最大迭代次数T，空间维数n（即组合服务中抽象服务数）

输出：空间最优位置

step1、设置当前迭代次数，随机初始化粒子群及每个粒子的速度和位置。

step2、计算每个粒子的适应度向量。

step3、按粒子适应度的大小将粒子从小到大排序编号。

step4、用基于遗传算法的粒子群算法进行粒子交叉，并选择较优的N个粒子进

      入下一代，获得新的粒子群。

step5、计算当前粒子的个体极值，为粒子从历史到当前最好的位置。

      全局极值为种群中最好的粒子位置。

step6、根据式(6)、(7)更新每个粒子的速度和位置。

step7、判断是否达到或满足迭代终止条件，若满足，则输出最优解。否则返回步骤2。

5实验及结果分析

     实验环境部署在一台CPU为Intel(R) Core(TM)i3  2.40GHz， 内存为4G 的PC机上， 操作系统使用Windows7， 采用 Matlab实现， 鉴于目前没有相关的标准平台和标准测试数据集， 实验数据（服务组合的任务数、Web服务组合数）均采用模拟的方式生成。假设一个组合服务由5个子服务组合而成，而每个子服务有4个属性，各个组合服务采用随机方法组合，则将目标函数可以定义为：

。

，，，为用户对服务性能要求而相应设置的目标权重，参数取值分别为：，，，；，;粒子群规模N=20；粒子群繁殖的代数MaxDT=300。在此本文针对三种情况进行实验:只进行处理时适应度值的变化情况；只进行遗传交叉时算法优化情况以及同时进行与交叉处理时适应度值变化情况，测试情分别如图3、图4和图5所示:

图a  进行处理后算法进化代数与适应度值关系曲线图

图b  未进行处理时算法进化代数与适应度值关系曲线图

图3  参数对适应度值曲线影响图

     图3为对参数进行处理和未进行处理时的适应度变化曲线图，a图为进行处理的情况，b图为未进行处理的情况。从图中可以看出，进行处理后，算法的收敛速度更快，a图迭代次数只用了230次，而从b图可以看出，当迭代300次时，算法仍未收敛。而且进行处理后，找到的最优值更好，a图为1.689282694028007e+020，b图为5.292880033000011e+013。可知进行处理比未进行处理时，找到的组合服务更快更优。

图a  进行交叉处理时进化代数与适应度值关系曲线图

图b  未进行交叉处理时进化代数与适应度值关系曲线图

图4 交叉处理对适应度值曲线影响图

     图4为进行交叉处理和未进行交叉处理时的适应度变化曲线图，a图为进行交叉处理的情况，b图为未进行交叉处理的情况。从两图的寻优情况来，进行交叉处理后，算法的寻优效果更好，a图找到的最优解为5.018609490470971e+036，b图找到的最优解为5.292880033000011e+013。但两种情况的收敛性都不如图3中a图的收敛性好。

图5 同时进行和交叉处理时进化代数与适应度值关系曲线图

     图5为同时进行参数调整和交叉处理后的算法进化代数与适应度值的关系曲线变化图。该算法迭代次数用了280次时，适应度值趋于稳定，找到的最优解为1.289569846198982e+038。

     现用如下表格进行几组实验结果对比：

表2 实验结果

    从实验结果可以得出，在迭代次数为300次时，同时进行与交叉处理后的PSO比基本PSO、只进行处理或交叉处理的PSO寻优能力更强，但是由于加入了交叉步骤，其收敛速度没有只进行处理的PSO收敛速度快。

6总结

Web 组合服务优化是近年来一个研究的热点和重点，本文提出的采用的基于遗传算法的粒子群算法可以有效解决组合服务优化问题。并通过参数的改进，提高了最优值的搜索精度。在本文的基础上，可以进一步对基于遗传算法的粒子群算法进行改进，也可将粒子群算法与其他智能算法结合，以进一步提高算法的搜索速度及搜索精度。

参考文献：

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

[2]柴雪霞, 马学森, 周雷, 唐昊. 基于SMDP模型的web服务组合优化方法[J],合肥工业大学学报(自然科学版), 2011, 34(10): 1496-1500.

[3]于明远, 朱艺华, 梁荣华. 基于混合微粒群算法的网格服务工作流调度[J]．华中科技大学学报(自然科学版), 2008, 36(4):45-47.

[4]何骏, 陈亮, 李永刚, 王晓龙. 基于改进蜂群算法的Web服务组合优化[J]. 装备学院学报, 2013, 24(5): 87-92.

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

[6]徐涛, 王新环. 基于多目标粒子群优化算法的web服务组合[J]. 计算机工程与设计, 2010, 31(18): 4076-4081.

[7]周文勇, 郭颂, 张继军. 基于服务质量的Web 服务组合模型[J]. 信阳师范学院学报(自然科学版), 2013, 26(3): 450-452.

[8]刘彬, 张仁津. 基于 QoS多目标优化的Web服务组合方法[J]. 计算机工程与设计, 2012, 33(3): 885-889.

[9] Zou G, Lu Q, Chen Y, et al. QoS-aware dynamic composition of Web services using numerical temporal planning[J]. 2012.

[10]秦锋, 李乔, 郑啸. web服务测试的一种实现[J]. 计算机技术与发展，2007, 17(8): 239-242.

[11]蒋乃乾. 一种基于扩展WSDL的web服务测试数据自动生成方法[D]. 硕士学位论文, 合肥工业大学, 2012.

[12]李胜刚, 丁晓明, 西南大学. 一种基于扩展WSDL的web服务测试数据自动生成方法[J]. 西南师范大学学报，2011, 36(1): 188-192.

[13]马超, 邓超, 熊尧, 吴军. 一种基于混合遗传和粒子群的智能优化算法[J]. 计算机研究与发展, 2013, 50(11): 2278-2286.

[14]秦毅, 彭力. 带过滤机制非线性惯性权重粒子群算法[J]. 计算机工程与应用, 2012.

[15]陈绍新. 多目标优化的粒子群算法及其应用研究[D]. 硕士学位论文, 大连理工大学, 2007.