基于Pareto解集的Web服务组合推优方案

万里 丁冲冲

南京财经大学信息工程学院 江苏 210046

0 引言

本文提出一种基于Pareto解集的多目标粒子群算法来解决多目标的Web服务组合全局优化问题，利用粒子群算法的寻优策略，对问题进行建模优化，并对已有算法本身存在的一些不足地方，进行分析和改进，最终产生满足用户需求的一组Pareto非劣解集，供用户来进行选择。

1 Web服务组合选择的多目标优化模型

1.1 Web服务组合的基本模型

一个 Web服务组合通常由提供不同的简单功能的多个Web服务构成，这些不同功能的子服务通常相互之间彼此独立。常用的Web服务组合的结构有四种，分别是顺序结构，并行结构，选择结构和循环结构。

在实际的应用中，提供功能相同或相似的Web服务数量较多，它们在功能上可以相互替代，但它们具有不同的非功能属性，例如服务的执行时间，执行价格，可信度以及可用性等。在Web服务进行组合的时候，需要按照指定的任务完成相应的功能，对于每个不同的任务，只包含相应的描述信息和接口信息，不指向具体的服务，我们称之为抽象服务。这样对复杂功能的Web服务，都有一定数量的抽象服务组合而成，在真正执行的时候，这些抽象服务将从候选服务里选出具体的服务来实现，通常抽象服务的候选服务有一个或者多个。以顺序结构为例，如图1中所示，S代表Web服务执行的起点，T代表终点，Wi为第i个抽象服务，Wi，j代表第i个抽象服务的第j个候选服务，其中(1≤i≤n，1≤j≤m)。

图1 Web服务组合选择

1.2 Web服务组合的多目标优化问题

考虑到Web服务的非功能属性通常具有多个评价参数。因此，很难找到一个全方位的最优解，使得组合的效果在各个属性方向上同时达到最优解，而且一些属性本身就具有互相偏离性，比如说时间短的服务与价格低的服务关系，或者价格低的服务与可信度高的服务的关系，通常这些服务的属性很难达到一致最优。所以只能对各个目标折中求解，使得各个目标尽可能符合用户需要。以往的处理方法往往是对各个目标进行线性加权，利用一个评价函数寻求多个目标的平衡，但这种方法会带来诸多问题。

本文采用的是利用多目标求解方法，将多个目标函数作为一个目标向量考虑，该目标向量的维数由属性的个数确定。求得目标向量通常会不止一个，所求得的这些向量之间，不存在一向量在任何一个目标上比另一个向量好，但同时其他目标也不差的更好解。这些解构成的集合称为Pareto最优解集，单个解称为Pareto最优解或者非劣解。多目标优化的几个基本概念如下：

定义1

(1) Pareto支配：解x0支配x1(x0≻ x1)当且仅当

(2) Pareto最优:如果解x0是Pareto最优的当且仅当┐∃x1：x1≻ x0。

(3) Pareto最优集：所有Pareto最优解的集合Ps={ x0|┐∃x1≻ x0}

(4) Pareto最优前端或均衡面或Pareto前端：所有Pareto最优解对应的目标函数值所形成的区域PF：

以两目标为例，图2描述了受支配解和非受支配解在目标空间的分布。

图2 受支配解与非受支配解的关系

2 基于粒子群算法的Web服务组合描述

2.1 标准粒子群算法

粒子群算法和其他进化算法类似，也是根据对环境的适应度将种群中的个体移动到好的区域，与其他进化算法不同，它不对个体使用进化算子，而将每个个体看成是搜索空间中的一个没有体积没有质量的粒子，在搜索空间中以一定的速度飞行，并根据个体和集体飞行的经验的综合分析来动态调整这个速度。

标准PSO中，粒子在搜索空间的速度和位置根据如下的公式确定：

式中，w为惯性权重；r1、r2为加速常数；rand()为区间[0,1]上均匀分布的随机数；Pt和Gt分别为t时刻粒子的自身最好位置pbest和全局最好位置gbest。pbest为粒子自身飞过的最好位置，而 gbest为粒子所对应的全局最好位置，它是整个群体所经历的最好位置。xt=(xt1,xt2,…,xm)与 vt=(vt1,vt2,…,vm)为时刻t的位置与速度。

标准粒子群算法流程如下：

(1) 初始化粒子群，随机产生所有粒子的位置和速度并确定粒子的pbest和gbest。

(2) 对每个粒子，将它的当前位置与它经历的最好位置pbest进行比较，如果当前位置更好，则将其作为当前的最好位置pbest，否则，pbest保持不变。

(3) 对每个粒子，将它的当前位置和群体中所有粒子所经历的最好位置 gbest作比价，如果这个粒子的位置更好，则将其设置为当前的gbest；否则gbest保持不变。

(4) 更新粒子的速度和位置。

(5) 如未达到结束条件(通常为预定的运算精度或迭代次数)，返回步骤(2)。

(6) 开始下一轮迭代计算；否则，取当前gbest为最优解。

2.2 离散粒子群算法

标准粒子群算法只要通过简单的变换就能够对连续空间求最优解取得很好的效果。但是在实际应用中，问题空间往往都在离散空间中，而标准粒子群算法往往较难处理。在标准粒子群基础上，一些研究者提出了离散粒子群算法(DPSO)，此类方法的研究大致有两个处理方向，一个是仍将离散空间中的组合优化问题转化成为连续空间中来处理，再按照标准粒子群的方法，对粒子的速度和位置进行更新和改变；而另一个方向是对粒子的速度、位置信息等进行重新的编码，其更新的机理也会随着具体问题的不同，而具有相对的灵活性和针对性。

基于连续空间的离散粒子群算法，以二进制编码的粒子群算法(BPSO)为代表，该算法首先由Kennedy和Eberhart提出，作者定义了一个sigmoid模糊函数：

相应的将位置更新公式变为：

其中rand为[0,1]之间均匀分布的随机数，在标准粒子群算法中，当前速度对下一时刻的粒子飞行方向和位置产生影响，使得搜索在一定的空间范围内变动。但是在BPSO中，速度的定义已经改变，通过sigmoid模糊函数，表示粒子位置取1的概率为S(vt),取0的概率为1-S(vt)。由于BPSO保留了标准粒子群算法中较多的更新方式，所以很多在处理连续空间上的方法都可以使用，但是由于BPSO二进制编码的局限性，所以该算法的应用领域并不是很广，对一些组合优化问题并不是很好的解决方法。

目前针对离散空间的DPSO研究较少，Clerc教授最先提出一种基于离散点位置交换的改进粒子群算法并成功求解了旅行商问题。在此算法中，位置标示为一个离散值向量，而速度则表示粒子的运动趋势，这样位置在交换前和交换后均为离散值。此算法在保持标准粒子群公式的条件下，改变了运算符号的意义，其新的符号分别为：

1，位置减操作Θ：例如xΘy，表示一个速度，即粒子由x朝y方向飞行。

2，速度加操作⊕：表示两个速度的叠加，先按照第一个速度移动，再按照第二个速度移动。

3，位置加速度操作⊕：位置加上某一个速度后，得到一个新的位置。

4，系数乘速度操作⊗：表示以这个系数为概率来按照这个速度移动位置。

基于离散空间的DPSO与标准粒子群算法的运动方式有很大不同，粒子不是通过在解空间内连续的运动方式来向最优解靠拢，而是采取跳动的方式来寻找，这种方式能够减小上一代粒子对下一代粒子的影响，从而能够更好的进行寻优。

2.3 改进的粒子群算法

上文中，Clerc提出的算法是针对特定的旅行商问题，粒子的运动方式也仅仅适用于存在值序概念的组合优化问题，而对Web服务组合问题并不好直接应用。通过分析发现，在Web服务组合问题上，可以对离散空间的DPSO算法做进一步的改进。由于Web服务的各个抽象服务之间具有相对的独立性，并且各个抽象服务的候选服务之间相互的关联度也很低，因此在此离散空间的寻优问题上，粒子由当前位置跳到下一位置的过程中，速度并不像标准粒子群算法那样有效的影响到寻优结果和收敛速度，因此位置的更新机理就成为考虑的重点。

为此，提出一种针对Web服务组合特点的基于离散空间的位置采取跳动方式的改进粒子群算法。该算法结合蚁群算法的思想和遗传算法的思想，并将三种算法结合起来，使得算法更加简单有效。在蚁群算法中，蚂蚁在寻找食物过程中选择路线会倾向于信息浓度较高的一条作为前进方向，在整个群体共同发挥作用下，能够一条发现最优解的路径。所以在粒子群算法中可以引进这种思想，使得粒子在更新过程中，也能够受到一定的因素影响。但是粒子群算法在搜索过程中，单个粒子只会保留下其最优信息，一旦多个粒子聚集在同一位置，将很难跳出此局部最优位置，最终无法找到全局最优解。针对粒子群算法收敛速度快但容易陷入局部最优的特点，可以借助遗传算法的变异策略，对部分粒子进行一定的扰动，从局部最优解跳出，使得搜索空间覆盖更广。本文采取的是对每一个粒子以一定的概率进行变异，并在每一代粒子中都进行变异，这样能有效防止局部最优解被保留下来。

以上通过对问题以及三种算法的简单分析，提出了一种新型的交换粒子群算法公式：

其中a1,a2均为0-1之间的数，Pkbest代表第k代粒子的最好位置，Pkgbest代表第k代所有粒子的最好位置，xk+1代表第k+1代粒子的位置。通过此公式进行更新时，第k+1代粒子将以概率a1取得第k代粒子的最好位置，以概率(1- a1)×a2取得第k代所有粒子的最好位置，以概率(1- a1)×(1-a2)来选取随机的位置。通过改变a1和a2的值，使得粒子既能够对自身的信息一定程度上的保留，又能够不断更新自身的信息，同时还可以给粒子带来类似遗传算法中变异的效果，此公式还精简了粒子群算法中的更新方式，从而使得该算法对整个问题的求解变得简单而有效。

2.4 利用改进的粒子群算法进行问题求解

利用粒子群算法对Web服务组合模型进行编码，其主要思想为：将一个Web服务组合方案看作是粒子群中一个飞行的粒子，粒子的维数代表一个Web服务组合的抽象服务的个数，而在每一维上的位置则代表了相应的候选服务。这样，一旦每一个粒子的维数以及粒子每一维上的位置确定下来，该粒子就表示了一个确定的Web服务组合方案，而粒子在每一维上的位置的变化，则代表Web服务组合过程中用来实现抽象服务的候选服务的变化，每一个粒子通过改变在各维上的位置来更新自身的最优解，而全局最优解集通过各个粒子的最优解的更新以及多次迭代来实现更新。

粒子的初始化。Web服务组合的维数为N，每一维上的候选服务为M个，先对每一维的Web抽象服务进行编号，在对这些抽象服务的候选服务进行编号，Wi，j代表第i个抽象服务的第 j个候选服务，其中(1≤i≤N，1≤j≤M)，再对每一个Web服务给定各个属性的初值，将Web服务的编号，位置和属性关联起来，通过编号即可以获得每一个Web服务相应的位置和属性。每一个粒子只包含 Web服务的位置信息，例如粒子信息如下(7,9,3)，表示Web服务组合中有3个抽象服务，第1个抽象服务选择其候选服务中的第7个，第2个抽象服务选择其候选服务中的第9个，第3个抽象服务选择其候选服务中的第3个。粒子的初始位置可以作为粒子的初始最好位置。

适应度的计算。每一个粒子代表一个 Web服务组合方案，可以将粒子在各维上的数据取出，按照相应的Web服务组合模型方案进行计算，在本文中，Web服务组合QoS中的时间和价格按照简单的叠加即可，而可信度和可用性按照叠乘即可，这样适用度的优劣，对于全局时间和价格越低越好，而全局的可信度和可用性则越高越好。

粒子群的初始化及更新，初始化一组粒子群，并将第一个粒子作为临时参考最优个体，对每一个粒子进行评价，如果有粒子可以支配临时参考最优个体，则用这个粒子替代临时参考最优个体，如果没有粒子可以支配临时参考最优个体，则不必更新，最后再将不被这个临时参考最优解支配的其他解记录下来。

最优解的保留，将上一步进行多次的迭代，将每次记录下来的解都放在一个外部的空间中，因为上一步中的临时参考最优解，具有很强的支配性，因此，不被它支配的解，也不容易被其他的解支配，而经过多次迭代后，这些解最终只会在这个外部档案中被支配，不会被外部档案以外的解支配，再将最后一次迭代的临时参考最优解放入这个档案中来。最后，对这个外部空间中的所有解，进行排劣操作，将被支配的解从这个空间中删除掉，从而外部空间中的解之间不再具备支配关系，此时得到的解的集合便是Pareto最优解集，从而得到Pareto最优组合方案，其他所有的Web服务组合方案都不会在服务质量上支配这些方案，从而可以将这些方案推荐给用户，供用户选择。

2.5 算法主要流程

根据上面分析，针对本文所述Web服务组合问题的求解流程图如图3所示。

图3 算法的主要流程

3 实验结果分析

本文实验的硬件环境为一台pc机，主要配置如下：intel CORE i3处理器，主频 2.4GHz，内存 4G。软件环境为windows7操作系统以及Myeclipse8.5，采用java实现。实验中的Web服务的任务数为10个，属性采用模拟方式实现，属性包括时间，价格，可信度以及可靠性，取值范围分别为：0

图4为在考虑两目标情况下，不同数量的候选服务，在不同的迭代次数下的程序运行时间的变化情况。通过图4可以看出，当候选服务数量相同时，随着迭代次数的增加，程序运行时间也随着增加，基本是线性的变化。相同的迭代次数，候选服务数量越大，运行时间越长，候选服务数量差值相同时，运行时间的差值变化也不大，可以近似认为运行时间与候选服务规模呈线性关系。

图4 不同迭代次数和不同规模候选下的运行时间

图5为在不同候选服务数量下，考虑不同的属性个数时，程序运行时间的变化情况。下图反应的是，考虑相同属性个数时，随着候选服务的增加，程序运行时间呈线性的增加，而相同的候选服务数量时，随着属性个数的不同则对运行时间有较大影响，随着属性个数的增加，程序运行时间急剧的增长，说明Web服务属相的个数对程序运行时间起主要作用。

图5 不同候选服务和不同属性个数的运行时间

图6 分别为本文方法与文献[4]中的方法，在考虑两目标情况下，不同的候选服务数量下程序运行的时间对比，通过图6可以看出，本文的方法程序运行时间与候选服务数量呈线性关系，且运行时间分布在一个不大的变化区间内。而普通的MOPSO算法则随着候选服务数量的增加，程序运行的时间快速的上升。在候选服务规模较小时，两方法的程序运行时间相差不大，但在候选服务数量较大时，本文方法的程序运行时间要远远小于文献[4]中提出的方法。

图6 两种方法对比

从以上的各个对比试验及分析，可总结出以下结论：Web服务组合的多目标优化问题，首要影响求解速度的因素是考虑问题属性的个数，即目标数量，其次是候选服务的规模。目标数量对求解速度起到主要作用，候选规模的大小对求解起到次要作用。

4 结束语

本文针对Web服务组合多目标优化问题的特点，简化了已有的PSO中对此类问题没有必要的步骤，改进了已有PSO算法，并结合了其他的进化算法的思想，使得提出的算法能够很好地解决Web服务组合多目标优化问题，尤其在规模较大问题上与已有的多目标粒子群求解 Web组合方法相比较具有明显的高效性。今后将在如何协调效率以及问题难度和精确度上做进一步的研究。

[1]Wan Shuchao, Wei Jun, Song Jingyu, et al. Developing a selection model for interactive Web services [C] //Proc of IEEE ICWS 06. Piscataway,NJ:IEEE.2006.

[2]雷德明,严新平.多目标智能优化算法及其应用[M].北京:科学出版社.

[3]夏虹,李增智.粒子群算法求解Web服务组合中基于QoS的服务选择[J].北京邮电大学学报.2009.

[4]徐涛,王新环.基于多目标粒子群优化算法的Web服务组合[J].计算机工程与设计.2010.

[5]孙学胜,曹玖新,刘波.基于多目标粒子群优化的服务选择算法[J].东南大学学报.2009.

[6]范小芹,蒋昌俊.基于离散微粒群算法的动态Web服务选择[J].计算机研究与发展.2010.