基于量子粒子群优化算法的Web服务组合问题

王创伟，汤克明

(盐城师范学院信息科学与技术学院，江苏盐城 224002)

基于量子粒子群优化算法的Web服务组合问题

王创伟，汤克明

(盐城师范学院信息科学与技术学院，江苏盐城 224002)

使用量子粒子群优化算法(QPSO)，将可能的Web服务工作流执行路径看作粒子，按照QPSO算法进行进化，从而解决了基于服务质量(Quality of Service，QoS)约束的Web服务组合问题，此为解决Web服务组合问题提出了一种新的思路.实验表明，使用QPSO算法求解复杂Web服务组合问题在组合时间上具有一定的优越性.

Web服务组合问题；量子粒子群优化算法；服务质量

0 引 言

随着Web服务技术的日益成熟，Web服务已经成为下一代分布式处理系统的核心，越来越多的稳定易用的Web服务共享在网络上.但单个Web服务提供的功能有限，不能适应开放的、动态的Web环境，为了更加充分地利用共享的Web服务，有必要将共享的Web服务组合起来，提供更为强大的服务功能，从而加快系统开发的速度，满足用户的需求.如何从众多服务中选择子服务，组成符合用户要求的复杂的服务组合?目前，该问题是Web服务应用集成的核心问题[1-5].对此，本研究采用智能优化算法—量子粒子群优化(Quantum-behavior Particle Swarm Optimization，QPSO)算法，提出对该问题的解决思路和方法，给出了求解过程，并与其他算法进行比较.实验表明，采用QPSO算法求解此类问题具有一定的优越性.

1 Web服务组合问题模型

图1 服务组合(CS)问题模型

设有一服务组合CS[4]，其由m个服务类组成(见图 1)，表示为，CS={SC1，SC2，…，SCm}，其中，SCi表示组成服务组合的第i个服务类(1≤i≤m)，而SCi={ES1，ES2，…，ESj}，其中，j≥1，即每个服务类又由j个候选的原子服务构成.该服务组合问题模型可以进一步细化为如图2所示模型.

图2 服务组合问题细化模型

假设一个合成服务由m个服务类组成，每个服务类有n个具有候选关系的原子服务，现要从每个服务类中选择一个原子服务，则会产生nm个可选方案，如何从这些方案中选择，以使合成服务满足用户的需求?对此，本研究利用QPSO算法的原理，寻求Web服务组合中最优解，从而得到构成服务组合的最佳原子服务.

2 量子粒子群优化算法(QPSO)

2004年，Sun等[2]提出QPSO算法，该算法是对整个PSO算法进化搜索策略的改变，进化方程不需要速度向量，而且进化方程的形式更简单，参数更少且更容易控制.

QPSO算法利用波函数 Ψ(x，t)来描述粒子的状态，并通过求解薛定谔方程得到粒子在空间某一点出现的概率密度函数，再通过Monte-Carlo随机模拟得到粒子的位置方程为，

式中，u为在[0，1]上服从均匀分布的随机数.

在此基础上，本研究在粒子群中引入一个全局点mbest来计算粒子的下一迭代步的变量L，它定义为所有粒子的个体最好位置的平均值，其计算公式为，

式中，M为种群中粒子的数目，Pi为粒子i的个体最好位置.

则，L的值可由下式确定，

为了保证算法的收敛性，每一个粒子必须收敛于各自的p点，p=(p1，p2，…，pD)，第i个粒子的p点的第d维坐标为，

式中，φ是在[0，1]上均匀分布的随机数，D为粒子的维数，Pi和Pg分别表示粒子i的个体最好位置和种群的全局最好位置.

最后，得到QPSO算法的进化方程为，

式中，β称为收缩扩张系数，是QPSO算法唯一的参数，一般取，

QPSO算法具体描述如下:

3 QPSO算法求解服务组合问题思路

基于QPSO算法求解Web服务组合问题的基本思路是:首先，产生一定数目的粒子群，每一个服务组合路径编码为一个粒子；然后，每一个粒子依据自身信息、局部较优信息(pbest)和全局较优信息(gbest)，产生具有更高目标准则值的新粒子，这一过程循环进行，在解空间中进行全局搜索；最后，算法停止时，得到一组粒子集合，即获得较优路径的组合集.

算法具体流程描述如下:

①初始化种群，根据调度规则设定各粒子的随机位置，并初始化Pi和Pg；

②根据当前迭代次数动态调整收缩扩张系数，从而实现算法搜索空间由全局逐步过渡到局部；

③计算每一粒子的适应度值，并确定是否更新Pi和Pg；

④按种群的进化方程生成新的粒子；

⑤判断是否满足算法的终止条件，若满足则转到步骤⑥，不满足则转到步骤②；

⑥输出构成服务组合的最佳原子服务ID，算法结束.

4 编码方案与实验分析

4.1 编码方案

编码方案的具体步骤为:

1)定义m个粒子，代表m种可能的服务组合路径.本方案采用一个3维数组Particle[i][j，k]表示每一个进化后的当前粒子所选择的服务和其QoS属性值，其中，i代表第i个粒子(0≤i≤m-1)，j代表可执行路径上第j个服务，k代表第k维QoS属性，当k=0时，代表第j个任务当前所选择的服务.

2)通过服务名称发现所有可选择的服务并读取每个服务的QoS值.从各个服务类的候选服务中随机选择一个服务，完成对用户提出请求的Web服务组合的初始化.

3)依据服务质量的量化方法，计算出当前粒子(组合路径)的QoS值，并把当前路径作为局部最优路径，再在整个解空间获得QoS最大的服务组合，并把该路径作为全局最优路径，完成最优粒子初始化.

4)对每个粒子进行进化，即对构成服务组合的路径进行更新.依据用户自定义的QoS约束条件和进化次数，进行循环.循环结束后，便得到全局最优组合路径.

4.2 实验结果与分析

在实验时，分别考虑服务类数量为10，每类服务中分别具有10、15、20个功能相同、服务质量不同的候选服务，也就是粒子服务群规模分别为100、150和200，迭代次数分别取 200、300、400、500和 600的情况下CPU的时间开销，并对于每一种情况，算法分别运行15次求其平均值，结果如图3所示.

图3 算法的执行时间比较

由图3可以看出，随着服务实例数目的增加，在不同的迭代次数下，CPU运行时间并没有大量增加.

同时，本实验采用线性规划算法、PSO算法和QPSO算法，分别对它们取得最优服务组合时所需要时间进行分析，结果如图4所示.

图4 不同算法执行时间的比较

由图4可看出，采用QPSO算法对求解规模较大的服务组合问题在计算时间上具有较大的优越性.

5 结 语

在Web服务技术日益发展的今天，为了满足用户对复杂Web服务请求的需求，就需要把多个原子服务组合起来实现更强大的服务功能.而在服务类中如何选择原子服务并把它们组合起来就成为解决该问题的关键.QPSO算法作为一种新兴的模拟进化算法，具有群体协作、正反馈和分布式并行计算等特点，在空间复杂度上与传统的算法相比具有较大的优越性.利用QPSO算法来解决Web服务组合问题有一定的理论参考价值和实际意义.

:

[1]陈彦萍，李增智.Web服务组合中基于服务质量的服务选择算法[J].西安交通大学学报，2006，40(8):897-900.

[2]Sun J，Feng B，XuW B.ParticleSwarmOptimization withParticles Having Quantum Behavior[C]//Proceedings of2004Congresson Evolutionary Computation.New York:IEEE Conference Publications，2004:325-331.

[3]王创伟，钱雪忠.蚁群算法在Web服务组合问题中的应用研究[J].计算机工程与设计，2007，28(24):5912-591.

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

[5]Zeng L ，Benatallah B ，Ngu A HH ，et al.QoS-awareMiddle ware for Web ServicesComposition[J].IEEE Transactions on Software Engineering，2004，30(5):311-327.

Quantum-behavior Particle Swarm Optimization Algorithm for Solving Problem of Web Service Composition

WANGChuangwei，TANGKeming

(College of Information Science and Technology，Yancheng Teachers University，Yancheng 224002，China)

QPSO(Quantum-behavior Particle Swarm Optimization)algorithm was attempted to solve the problem of web services composition in this paper，which took web services workflow path as particles and was optimized according to QPSO algorithm，so as to solve the problems of web services composition based on QoS constraints.The experimental results indicate that QPSO algorithm for solving complex composition problems has some advantage at composition time.

web services composition problem ；quantum-behavior particle swarm optimization ；QoS

TP301.6；TP393.0

A

1004-5422(2012)04-0354-03

2012-09-12.

王创伟(1974—)，男，硕士，副教授，从事计算机Web服务技术研究.