应用于服务组合的改良粒子群算法

Improved Particle Swarm Optimization for Service Composition

摘要: 当今社会，互联网、物联网、云计算以及大数据的快速发展和普及使得网络应用越来越广，越来越多的行业和相应的网络进行越来越深地融合。许多原本属于线下的服务经过封装后被搬上了网络上，同类型的服务也越来越多。如何在互联网大数据环境下快速找到满足用户个性化需求的服务组合已经成为亟需解决的问题。为了解决这个问题，本论文提出了一种改良粒子群服务组合方法，此改良粒子群算法根据服务组合问题的特点分别从四个方面加入了逃出局部最优的机制，根据用户的服务组合请求去快速组合出更优的服务组合方案。本文通过实验与其他相关的服务组合优化算法在最优性、时间复杂度以及收敛性三个指标进行了对比。根据实验结果分析，本文所提出的方法在最优性、时间复杂度以及收敛性三个方面整体上表现出来良好的性能。

Abstract: In today’s society, the rapid development and popularization of the Internet, Internet of Things, cloud computing, and big data make network applications increasingly widely used. And increasing industries and corresponding networks are integrated increasing deeply. Many services that originally belonged to the line have been packaged and put on the Internet, and there are increasing services of the same type. How to quickly find a service combination that meets the personalized needs of users in the Internet big data environment has become an urgent problem to be solved. In order to solve this problem, this paper proposes an improved particle swarm service composition method. According to the characteristics of the service composition problem, the improved particle swarm algorithm adds a mechanism of escaping from the local optimum from four aspects. According to a user’s service composition request, quickly compose a better service composition solution. This paper compares the optimality, time complexity and convergence with other related service composition optimization algorithms through experiments. According to the analysis of the experimental results, the method proposed in this paper shows good performance on the whole in terms of optimality, time complexity and convergence.

1. 引言

随着云计算 [1]、IoT [2] 以及IoD [3] 等技术的发展，越来越多的线下服务通过虚拟化技术加入到线上，同线上服务一起协同为用户提供服务。这些线上服务越来越多，需求越来越复杂，逐渐构成了IoS [4] 或Big service [5] 以及跨界服务 [6]；为了满足用户的复杂需求，需要进行服务组合。其中面临的挑战就是面对复杂的需求和海量的可用服务，如何通过服务组合技术快速高效地构建服务组合方案。单一的Web服务往往不能很好地满足复杂的客户需求，服务组合变得相当重要 [7]。在进行服务组合的过程中，每一种类型的服务存在大量功能相同而QoS (Quality of Service)不同的候选服务，这些候选服务就构成了对应服务类型的候选服务集。QoS感知的服务组合已经成为研究的热点。另外，互联网上的服务对应存在着大量的服务历史记录，若能利用这些服务历史记录作为服务组合的先验知识去指导服务组合，这将大大提高服务组合的效率。目前的Web组合方法一般都是基于QoS感知的Web服务组合方法，针对基于QoS感知的Web服务组合优化问题，目前的解决方法很多，大致可以分为三大类 [8]：

1) 局部搜索方法 [9] [10]，不同的QoS属性值通过一个聚合函数被映射为单一指标，参照多指标从每个候选服务集中选择一个具体的服务来构成一个服务组合方案。这种方法对于有少量QoS属性限制条件的服务组合有效果，但对于大量的有QoS属性限制的服务组合效率较低。

2) 全局优化方法 [11] [12] [13]，这种方法将整个服务组合问题转化为混合线性规划问题，通过一个线性函数寻找解决方案。这种方法对选择最优组合服务的算法有一定的限制，所求的目标函数必须是线性的，不能完全用于解决Web服务组合问题。

3) 智能优化算法 [14] [15] [16] [17]，该方法解决了全局优化算法的缺点，这也是目前用来解决Web服务组合问题的主流方法。

以上服务组合方法在面对海量需求和可用服务场景下，效率和性能不能满足用户的需求；本文的解决思路是根据服务组合问题和服务数据集的特点设计出具有逃出局部最优即预防早熟机制的改良离散粒子群服务组合算法IDPSO (Improved Discrete Particle Swarm Optimization)，该算法分别从对候选服务集进行排序、一定迭代次数后重置粒子位置、合理设置算法控制参数、设置参照最优性四个方面来预防粒子群算法早熟。改进后的粒子群算法有效克服了容易陷入局部最优的窘境，其组合效率得到了很大的提高。

2. 相关工作

基于QoS感知的服务组合问题有两个重要的衡量指标，时间复杂度Time Complexity和最优性Optimality。时间复杂度反映的是算法的时间性能，简单的来说是算法所执行的时间，最优性反映的是算法的寻优能力。一般情况下，时间复杂度和最优性是相互矛盾的，寻求高的时间效率会牺牲算法的最优性，反之亦然。所以，如何在时间复杂度和最优性之间找到一个平衡点去满足客户的需求是服务组合的一个关键问题。服务组合就是从候选集合中选择相应的具体服务去组合成满足客户所提的QoS限制的方案，这是一个NP-hard问题 [18]。目前的群智能优化算法对于连续型的问题寻优效果相当好，但是对于Web服务组合这一类离散型问题就显得捉襟见肘了。所有的群智能优化算法都存在陷入局部最优的问题，因为群智能优化算法在寻找最优解的过程中遵循一定的方向和顺序性，所以群智能优化算法对于连续型的问题表现出优良的效果。文献 [19] 给出有关联关系的服务模型，使用遗传算法进行服务组合方案的查找，提出了一种云制造中有关联意识的服务组合方案选择方法。文献 [20] 使用粒子群优化算法来解决Web服务组合优化问题。作为解决Web服务组合优化问题的典型算法，与遗传算法相比，粒子群优化算法具有参数少、收敛快的特点，在很多寻优问题上表现出良好的性能，但粒子群算法也会出现早熟现象，容易陷入局部最优问题 [21]。文献 [22] 提出了一种将候选服务分类的方法来解决大规模Web服务组合问题，此方法提出了一个缩减模型来减少服务候选集的规模，以企图降低问题的搜索空间来提高寻优效率，此方法需要每次根据新的服务组合问题对新的候选服务集进行缩减，这样就降低了算法的整体效率。文献 [16] 提出了利用人工蜂群算法来解决Web服务组合问题，人工蜂群算法相对于粒子群算法其参数更少，但是其寻优性能略低一些。文献 [23] 提出了任务粒化的质量约束感知的服务组合方法，该方法把服务组合模型分为4个层，最下层为基本层，对应的是服务组合的候选服务集；最上层为任务粒层对应的是服务组合中分割出的任务；任务粒化的分层方法一定程度上提高了组合效率，但是割裂了服务组合方案的整体约束，因此寻找出的服务组合方案未必是最优的。

本文中提出的改良粒子群优化算法引入了逃出局部最优的相关机制，可以很好的避免陷入局部最优以实现寻找到全局最优解。理论分析和实验表明，在Web服务组合优化问题上，本文所提出的方法有更好的综合性能。

3. Web服务组合问题描述

本部分主要阐述Web服务组合中QoS的定义以及Web服务组合问题的定义。

3.1. QoS的定义

Web服务质量QoS是一个6元组 $QoS=\left(p,r,a,rep,t,rel\right)$，其中：p是服务价格price，指调用一次服务所需要的费用，r是响应时间response time，a是可用性availability，指服务执行成功的次数与总执行次数的比率，rep是信誉度reputation， $rep=\left({\displaystyle {\sum }_{i=1}^{n}s{c}_i}\right)/n$ 是用户对当前服务n次评价得分 $\left(s{c}_1,s{c}_2,\cdots ,s{c}_i,\cdots ,s{c}_n\right)$ 的平均值 [20]，t是吞吐量throughput，rel是可靠性reliability，指服务能运行的时间与总时间的比率。

3.2. 服务组合问题的定义

服务组合的目的是在满足用户功能需求和QoS总体约束下，针对特定的优化目标，得到一组最优的服务集合，构成组合服务。组合服务是一个6元组 $cs=\left(T,R,QoS,QC,W,EF\right)$，其中： $T=\left\{t_1,t_2,\cdots ,t_j,\cdots ,t_n\right\}$ 表示构成组合服务的任务集合，关系 $R\subset T\ast T$ 表示任务之间时序关系集合，QoS是组合服务的总体质量， $QC=\left\{C\left(p\right),C\left(r\right),C\left(a\right),C\left(re\right),C\left(t\right),C\left(rel\right)\right\}$ 表示组合服务必须满足的质量约束， $w=\left\{w_1,w_2,\cdots ,w_6\right\}$ 是集合QoS中各子属性对应的权重并且满足 ${\displaystyle {\sum }_{i=1}^6{w}_i}=1$，EF是组合服务质量评价函数即最优性函数。任务集T中的任务 $t_j$ 是抽象服务，在组合服务CS执行前，从 $t_j$ 的候选服务集 $CS{S}_j$ 中选择一个具体的Web服务 $a{s}_k^j$ 代替抽象服务 $CS{S}_j$， $a{s}_k^j$ 表示 $CS{S}_j$ 中第k个候选服务， $k\in \left\{1,2,\cdots ,\left|CS{S}_j\right|\right\}$。组合服务的生成过程是根据客户提交的任务信息来寻找满足客户需求的组合服务过程。组合服务生成的过程主要分为两个步骤进行，即服务选择与服务组合。在服务寻找过程中，将客户提交的任务T抽象为多个子任务 $\left\{t_1,t_2,\cdots ,t_j,\cdots ,t_n\right\}$，各个子任务间有不同的执行关系，工作流管理联盟(WFMC)定义了4种基本执行关系模型，即顺序(Sequence)、并行(Parallel)、选择(Selective)、循环(Circular)等。在定义的基本关系模型中，并行、选择与循环模型均可以转换为顺序模型，本文选取顺序模型作为研究对象。

由于客户对于QoS属性有个性化的要求，在对组合服务进行评估时，根据客户的偏好以及这个组合服务的整体QoS值，使用组合评价函数EF去评估这个组合服务的解决方案，选出最佳的组合服务。由于Web服务的QoS每个属性取值范围有较大的差别，不在同一计算等级上，在进行Web服务评估之前必须先将QoS属性值进行预处理。本文使用被广泛采纳的文献 [20] 中的方法对Web服务的属性值进行预处理，将属性值区间限定为[0, 1]，经过预处理后的QoS各子属性值越小代表服务越优。

4. 离散粒子群改良算法IDPSO

当客户提交服务组合请求时，需要采用合适的算法进行服务组合，现有的粒子群算法普遍具有陷入局部最优的问题，其寻优性能不太理想，为此，本文根据Web服务问题的特点进行了深入的分析和研究，设计出了针对Web服务问题具有很好性能的离散粒子群改良算法IDPSO，下面给出了粒子的相关概念以及IDPSO算法的具体分析和设计过程。

4.1. 标准粒子群算法

粒子是存在于n维欧氏空间中无体积、无质量的对象，粒子群是是空间中m个粒子的集合 [20]。粒子群算法是一种启发式进化计算技术，来源于对简化社会群体智能行为模型的模拟，由Eberhart和Kennedy于1995年提出 [24] 在标准粒子群算法SPSO(Standard Particle Swarm Optimization)下，在第t + 1代时，第i个粒子的第j维速度和位置迭代更新公式如公式(1)、(2)表示：

$V_{i,j}^{t+1}=w\ast V_{i,j}^t+c_1{r}_1\left(p_{i,j}-X_{i,j}^t\right)+c_2{r}_2\left(p_{g,j}-X_{i,j}^t\right)$ (1)

$X_{i,j}^{t+1}=X_{i,j}^t+V_{i,j}^{t+1}$ (2)

其中非负常数 $C_1$， $C_2$ 是学习因子，决定 $p_{i,j}$ 和 $p_{g,j}$ 对新速度的影响程度， $r_1$ 和 $r_2$ 是区间[0, 1]上均匀分布的随机变量。w值越大，全局寻优能力越强。目前采用较多的是Shi建议的线性递减惯性权重值 [24]，如公式(3)所示：

$w=w_{\min }+\left(w_{\max }-w_{\min }\right)/\left(T_{\max }-t\right)/T_{\max }$ (3)

其中 $w_{\max }$ 为初始惯性权重值， $w_{\min }$ 为最大迭代次数对应的惯性权重值，一般取 $w_{\max }=0.9$， $w_{\min }=0.4$。

在进行服务组合的选择时本文将一个粒子看作一个服务组合解决方案，然后去寻找最优组合服务方案。本文分解的抽象子任务 $T=\left\{t_1,t_2,\cdots ,t_i,\cdots ,t_n\right\}$ 代表粒子的各维搜索空间，n代表分解的抽象子任务的个数，同时n也表示粒子的搜索空间有n维。每个抽象子任务 $t_i$ 对应的候选服务集 $CS{S}_i$ 中Web服务个数设为 $m_i$ 个，即表示粒子在这一维搜索空间中的最大向量长度， $i\in \left[1,n\right]\wedge i\in N^{+}$， $CS{S}_i$ 中的每一个元素为单元服务 $a{s}_j^i$， $j\in \left[1,m_i\right]\wedge j\in N^{+}$，具体编码模式如图1所示：

Figure 1. Particle coding in service composition

图1. 服务组合中粒子编码

粒子选出对应的各个维的向量值后就完成了Web服务组合解决方案的选择。通过适应度值评估函数对每一个粒子所对应的Web服务组合解决方案进行评估，来寻找最优解的服务组合解决方案。使用这种编码方式，Web服务组合选择问题被转化为n元向量的求解问题，即寻找最优向量 $\left(X_1,X_2,\cdots ,X_i,\cdots ,X_n\right)$ 过程。任务 $T=\left\{t_1,t_2,\cdots ,t_i,\cdots ,t_n\right\}$ 为组合服务CS的任务集合，T中各抽象服务对应的候选数量分别为 $m_1,m_2,\cdots ,m_i,\cdots ,m_n$ 且 $m_i\in N^{+}\wedge i\in \left[1,n\right]$，则组合服务解空间大小为 ${\displaystyle {\prod }_{i=1}^n{m}_i}$，这也是是采用穷举法求最优解的时间复杂度，当任务T中子任务数量以及每一个子任务 $t_i$ 对应的候选服务 $m_i$ 的值非常大时，其时间复杂度是非常庞大的，这也是服务组合不能采用穷举法的直接原因。IDPSO算法将粒子在其所有维度上的运动区间设置为连续的圆周轨道，当采用适应度函数评价粒子位置的优劣时，用约数函数将粒子的具体位置映射到离散区间上。

4.2. IDPSO算法

针对服务组合问题，使用改良的粒子群算法IDPSO来寻找最优的组合服务方案。本文首先采用如图1所示的编码方式对种群粒子进行编码处理。本算法设置相应的预防早熟机制，在必要的时机进行操作以便使粒子逃出局部最优位置，根据适应度函数 $f\left(X\right)$ 对种群粒子选出的组合服务方案进行评估，选出种群中最优的服务组合方案。

4.2.1. 适应度函数设计

在Web服务组合方案的选择中，服务组合方案的整体QoS对服务评估有较大影响，根据服务组合方案中单个节点服务的QoS属性值进行聚合计算，得出服务组合方案的整体QoS指标。适应度函数作为Web服务组合方案的评估函数，计算方法有多种，本文中聚合函数和适应度值计算函数为：

$Q_{cs}^r=Aggregation\left(c{s}_r\right)$ (4)

$fitness={\displaystyle \sum w_r}*Q_{cs}^r$ (5)

其中， $c{s}_r$ 是当前服务组合方案的第r个属性， $Aggregation\left(c{s}_r\right)$ 是对服务组合方案cs中每一个原子服务的第r个属性进行聚合， $w_r$ 表示客户对于Web服务组合方案的第r个QoS属性的偏好即权重值，n为服务组合方案的QoS属性总个数。本文使用文献 [20] 提出的组合服务属性值的计算方法，在对服务组合方案QoS属性值进行预处理，得出顺序模型下的组合服务方案整体 $Q_{cs}^r$ 属性值，本文中的适应度值fitness越小代表最优性越优。

4.2.2. 预防早熟机制

1) 对候选服务集进行排序

通过本文对粒子群算法进行分析后发现，粒子群算法运行时粒子群中的每一个粒子首先会随机初始化一个位置，然后每一个粒子会在各种的运行轨道上沿着特定的方向上进行运动，因此粒子群算法对于最优解有一定方向秩序的问题表现出很好的性能，如图2所示的利用粒子群算法求抛物线函数 $y=f\left(x\right)$ 最小函数值的位置，粒子群中某一个粒子的位置当前在 $x_0$ 的位置，此时这个粒子只有继续不断的向右移动就可以逼近最低点 $x_1$ 的位置，进而就可以寻找到最小函数值的位置。对于这种有秩序的问题，粒子群中至少有一个粒子的方向恰好与解的方向一致，此时寻优问题就迎刃而解。

Figure 2. An example of finding the optimal solution

图2. 求最优解示例

基于上述发现的粒子群算法的一个特点，本文试图对使用IDPSO算法的服务组合问题中的某个对象或者某些对象进行排序，IDPSO算法操纵的基本对象为候选服务集，因此本文需要对候选服务集 $CS{S}_i$ 进行排序，对服务候选集 $CS{S}_i$ 怎么排序是一个问题，经过本文深入分析发现，IDPSO算法对候选服务集的操纵最终体现在 $CS{S}_i$ 中的每一个原子服务 $a{s}_j^i$ 的每一个QoS属性，因此本文进一步想到根据 $a{s}_j^i$ 中的某一个或某几个QoS属性对 $CS{S}_i$ 进行排序，究竟根据 $a{s}_j^i$ 中哪一个或哪几个QoS属性对 $CS{S}_i$ 进行排序呢， $a{s}_j^i$ 中的每一个QoS属性对应着权重w，哪一个QoS对应的权重越大，表明这个QoS对服务组合方案的影响即最优性的影响越大，因此本文根据具有最大权重的QoS属性对 $CS{S}_i$ 中的 $a{s}_j^i$ 进行排序。根据前面的定义可知， $QoS=\left(p,r,a,re,t,rel\right)$，对应的权重为 $w=\left(w_1,w_2,w_3,w_4,w_5,w_6\right)$，即属性p的权重为 $w_1$，属性r的权重为 $w_2$，属性a的权重为 $w_3$，属性re的权重为 $w_4$，属性t的权重为 $w_5$，属性rel的权重为 $w_6$，假如 $w=\left(0.4,0.1,0.1,0.2,0.1,0.1\right)$，那么本文就根据第1个属性p对候选服务集 $CS{S}_i$ 进行升序排序，假如 $w=\left(0.1,0.2,0.3,0.1,0.2,0.1\right)$，那么本文根据第3个属性a对候选服务集 $CS{S}_i$ 进行降序排序。QoS的前2个属性为反向属性即属性值越大越不优，后4个属性为正向属性即属性值越大越优，所以若根据前2个属性中的任一个属性对 $CS{S}_i$ 进行排序，那么就需要进行升序排序，若根据后4个属性的任意属性对 $CS{S}_i$ 进行排序，那么就需要进行降序排序。最后，本文通过相关试验表明，本文采用以上的策略对候选服务集 $CS{S}_i$ 的排序方法对预防IDPSO早熟的问题起到了一定的作用。

2) 一定迭代次数后重置粒子位置

粒子早熟意味着粒子陷入局部最优长时间无法逃离，粒子群算法开始运行时，首先会给每一个粒子随机生成一个位置，然后每一个粒子会在各自的运行轨道上扫描查找最优位置，假如当前所有粒子各自的运行轨道恰好绕过了全局最优或更优位置，那么整个粒子群算法就陷入了局部最优，即粒子算群法出现了早熟。如图3所示，此粒子群有三个粒子组成，分别为 $p_1$， $p_2$， $p_3$， $X_{op}$ 为整个空间中最优位置或者更优位置， $X_{op}$ 在粒子 $p_1$ 的运行轨道和粒子 $p_2$ 的运行轨道之间的某一位置，三个粒子 $p_1$， $p_2$， $p_3$ 各自的运行轨道上运行，三个粒子的运行轨道恰恰绕过了 $X_{op}$ 的位置，没有一个粒子的运行轨道扫过 $X_{op}$ 的位置。此时，这种情况意味着粒子陷入了局部最优，无论此后多久粒子都不会找到全局最优或者更优位置的 $X_{op}$。因此当粒子群陷入局部最优时，本文需要检测出或预测出粒子陷入局部最优，然后使其逃出局部最优的情况。为此，本文需要分两步走来促使粒子逃出局部最优位置，第一步，检测出或者预测出粒子陷入了局部最优的时刻，直接检测出粒子陷入了局部最优位置是非常困难的，因此本文采用预测粒子陷入局部最优的策略，当然直接预测粒子陷入局部情况也是有困难的，本文采用间接的预测，本文知道当粒子圈算法运行足够长的时间其最优性值仍没有发生变化，此时意味着大概率陷入了局部最优，因此当粒子群算法经过足够长的迭代次数后其最优性值没有改变，本文就判定为陷入局部最优，其这个经过的足够长的迭代次数设为 $t_{pre}$， $t_{pre}$ 满足 $t_{pre}\in \left[\left(1/5\right)T_{\max },\left(1/3\right)T_{\max }\right]\wedge t_{pre}\in N^{+}$，第二步，当预测出粒子群算法陷入局部最优时，立刻进行干预使其逃出局部最优位置，显而易见，事先本文并不知道全局最优位置到底在什么地方，对于本文来说最优位置或者更优位置具有一定的盲目性，从概率上来讲就是随机性，所以当粒子群算法陷入局部最优时，本文采用随机重置的方法来重置每一个粒子的位置，尽可能的使某一个或某些粒子的运动轨道恰好扫过最优位置或更优位置。

Figure 3. Particle trap into local optimum example

图3. 粒子陷入局部最优示例

3) 合理设置IDPSO的控制参数值

IDPSO算法的控制参数控制着IDPSO算法的执行，因此IDPSO算法的某个参数或者某些参数可能影响着算法的收敛情况，即影响着时间复杂度Time Complexity和最优性Optimality。IDPSO的五个控制参数分别为PS、 $T_{\max }$ 、 $c_1$ 、 $c_2$ 、w、 $v_{ini}$，PS代表粒子群的规模即粒子个数， $T_{\max }$ 为IDPSO算法的最大迭代次数即算法的最大迭代次数， $c_1$ 、 $c_2$ 两个参数为非负常数是学习因子，决定全局粒子最优位置和当前粒子历史最优位置对粒子速度的影响，w是惯性权重， $v_{ini}$ 为粒子的初始化速度。显而易见，参数PS和 $T_{\max }$ 直接影响着时间复杂度和算法的最优性，即 $PS\ast T_{\max }$ 的值越大更有利于最优性，但同时会增加算法的时间复杂度，因此需要对 $PS\ast T_{\max }$ 值进行一个取舍，使其在客户可以容忍的时间内尽量保证算法的最优性即在客户可以容忍的时间内使 $PS\ast T_{\max }$ 足够大，本文知道IDPSO算法的所有组合服务方案解的空间大小为 ${\displaystyle {\prod }_{i=1}^n{m}_i}$，当 $PS\times T_{\max }={\displaystyle {\prod }_{i=1}^n{m}_i}$ 时，IDPSO算法穷尽了整个解的空间，此时是可以找到全局最优解，当 ${\displaystyle {\prod }_{i=1}^n{m}_i}$ 很大时， $PS\ast T_{\max }$ 是不可以等于 ${\displaystyle {\prod }_{i=1}^n{m}_i}$ 的，经过本文相关试验表明，当 $PS\ast T_{\max }$ 至少取值为 $\left(1/1000\right){\displaystyle {\prod }_{i=1}^n{m}_i}$ 时，IDPSO算法可以取得很好的最优性，因此本文设置 $PS\ast T_{\max }\approx \left(1/1000\right){\displaystyle {\prod }_{i=1}^n{m}_i}$，此时IDPSOS算法只要穷尽整个解空间的大约千分之一就可以取得很好的最优性，当客户对 $PS\ast T_{\max }\approx \left(1/1000\right){\displaystyle {\prod }_{i=1}^n{m}_i}$ 的值仍然不可容忍时可以根据客户的需求适当下调。另外，当 $PS\ast T_{\max }$ 设定后，PS与 $T_{\max }$ 值如何分配也是一个问题，若PS值分配比值过多，意味着迭代次数 $T_{\max }$ 过少，此时不利于IDPSO算法随机重置粒子位置，可能会影响算法的最优性，若 $T_{\max }$ 分配比值过大，意味着IDPSO算法随机重置粒子位置的次数会多，如果先前某个粒子或某些粒子的轨道会覆盖全局最优解，但还没来得及扫描到这个最优解就被重置了，这样也不利于IDPSO算法的寻优能力，因此本文按照1:1的方式去分配PS和 $T_{\max }$ 的值。关于c₁、c₂值的设置，c₁、c₂是学习因子，决定历史全局最优位置和当前粒子历史最优位置对新速度的影响，若c₁、c₂的值较大，则意味着粒子群历史全局最优位置和当前粒子历史最优位置对新速度的影响就较大，反之亦然，c₁、c₂的值目前没有很好的设定标准，本文的建议是首先为c₁、c₂设置很大的值，如果此时IDPSO算法的最优性值频繁的改变，意味着历史全局最优位置和当前粒子历史最优位置实际上对算法搜寻新的最优性值的帮助很大，因此，此时本算法需要保持或增加历史全局最优位置和当前粒子历史最优位置对算法寻优的影响力，所以本文可以选择不改变c₁、c₂的值或适当增加c₁、c₂的值，如果IDPSO算法的最优性值很多迭代次数后仍未改变，意味着历史全局最优置和当前粒子历史最优位置实际上对算法搜寻新的最优性值的帮助不大或无帮助，因此，此时本文需要减小历史全局最优位置和当前粒子历史最优位置对算法寻优的影响力，所以本文可以适当减小c₁、c₂的值。关于参数w值的设定，参数w值可以根据公式(3)进行设定。参数 $V_{ini}$ 为粒子初始化速度，由于全局最优位置对于本文来说具有一定的盲目性，因此本文采用随机策略为参数 $V_{ini}$ 设置一个值，随机策略就是随机生成一组整数来作为 $V_{ini}$ 的值。

4) 设置参照最优性

在整体与组成部分的关系中，本文知道组成部分最优并不意味着整体的最优，但是最优的组成部分组合而成的整体是比较优的，所以最优的组成部分对于整体最优具有一定的参考价值，本文把这种理念应用到IDPSO算法中，前面本文提到任务 $T=\left\{t_1,t_2,\cdots ,t_i,\cdots ,t_n\right\}$，其对应的候选服务集为 $CSS=\left\{CS{S}_1,CS{S}_2,\cdots ,CS{S}_i,\cdots ,CS{S}_n\right\}$，即子任务 $t_i$ 对应的候选服务集为 $CS{S}_i$，首先本文对每一个子任务 $CS{S}_i$ 的候选服务集 $t_i$ 中的单元服务 $a{s}_j^i$ 计算单元适应度值，其计算公式如下：

$fitnes{s}_{as}={\displaystyle {\sum }_{r=1}^n{w}_r\ast Q_{as}^r}$ (6)

其中 $w_r$ 为单元服务as的第r个属性的权重， $Q_{as}^r$ 为单元服务as第r个属性，然后选出每一个候选服务集 $CS{S}_i$ 中单元适应度值最小的单元服务 $a{s}_{MF}$，组成参照最优服务组合方案 $C{S}_{ref}$，把方案 $C{S}_{ref}$ 用公式(4)、(5)计算出适应度值，本文称为参照适应度值 $fitnes{s}_{ref}$。当IDPSO算法执行最后一次迭代后，用得到的全局最优粒子的适应度值fitness与参照适应度值 $fitnes{s}_{ref}$ 作比较，若 $fitness<fitnes{s}_{ref}$，则表明粒子群算法选出了全局最优或更优的解决方案，此时使用全局最优粒子对应的解决方案，若 $fitness>fitnes{s}_{ref}$，则表明粒子群算法实际上还是陷入了局部最优，且粒子群算法选出的最优方案并不是很好，如果此时客户不能接受粒子群算法继续寻优所导致的长时间的等待，则此时应选择参照最优服务组合方案 $C{S}_{ref}$ 作为服务组合的最优方案，若 $fitness=fitnes{s}_{ref}$，则表明粒子群算法选出的解决方案的最优性与参照最优服务组合方案 $C{S}_{ref}$ 的最优性相当，粒子群算法可能仍陷入局部最优，如果此时客户不能接受粒子群算法继续寻优所导致的长时间的等待，那么使用当前粒子群选出的最优方案或者使用参照最优服务组合方案 $C{S}_{ref}$ 都可以。

基于以上分析和设计，下面给出用于服务组合的IDPSO算法描述。

算法1. IDPOS算法

输入：PS, $T_{\max }$, $c_1$, $c_2$, w, V

输出： $P_{gbest}$ /*全局最优粒子的位置*/

1. /*初始化PS , $c_1$, $c_2$ */

2. /*为粒子群设置维度*/

3. /*根据最大权重的QoS属性对服务候选服务集CSS进行降序排序*/

4. :Randomly initialize V,X /*随机初始化V, X, X为粒子的位置矩阵*/

5. Compute fitness/*计算适应度值fitness*/

6. Set $P_{ibest}$, $P_{gbest}$ according to fitness/*根据fitness填充 $P_{ibest}$ 和 $P_{gbest}$ 的值， $P_{ibest}$, $P_{gbest}$ 分别为粒子个体历史最优位置和粒子全局历史最优位置*/

7. Set $t_{pre}=1$

8. While (iterations <= $T_{\max }$)

8.1. If ( $t_{pre}$ = set count)

8.1.1. Randomly initialize V, X

8.2. Else

8.2.1. Update $c_1$, $c_2$, w/*更新 $c_1$, $c_2$, w*/

8.2.3. Update V

8.2.4. Update X

8.3. Compute fitness

8.4. Update $P_{ibest}$, $P_{gbest}$ according to fitness

8.5. $t_{pre}++$

9. Compute $fitnes{s}_{ref}$ /*为参照最优方案的适应度*/

10. If ( $fitnes{s}_{ref}<fitnes{s}_g$)/*为循环语句给出的全局最优方案的适应度值*/

10.1. return $P_{ref}$ /*参照最优位置*/

11. Else

11.1. return $P_{gbest}$

5. 实验设计与结果分析

5.1. 实验数据与环境

本文实验中单元服务部分采用Zeng等的QWS公共数据集 [25] [26]。在本文实验中，本文分别测试不同的子任务数，并将QWS数据集上的服务分别分配到这些子任务上，用来作为子任务的候选服务集，本文设定每个子任务的候选集包含100条单元服务。本文选择数据集中的4个属性以及用仿真生成工具插入数据集中作为补充的2个属性总共6个属性作为本文QoS评价指标属性，即响应时间(r)，可用性(a)，吞吐量(t)，可靠性(rel)，服务价格(p)，信誉度(rep)，其中前面4个为QWS数据中原有的属性，最后2个属性是仿真生成插入QWS数据中的属性，数据集的特征如表1所示。设置 $weight\left(r,a,t,rel,p,rep\right)=\left(0.2,0.3,0.1,0.1,0.2,0.1\right)$ 为客户偏好。本文的实验环境为windows 7 OS, Intel(R) Core(TM) i5 3230 CPU @ 3.60 GHZ, 12 GB RAM, 64位操作系统，采用的实验工具为eclipse + pyDev2.7 + python 3.0。

Table 1. Characteristics of atomic services in the service

表1. 服务数据集中单元服务的特征

5.2. 实验参数设置

本文根据不同子任务数设置一些组实验，第一组实验的子任务数为2，其他组实验的子任务数逐次加2，最后一组实验的子任务数为20，共10组实验，每组实验均进行50次，实验最终结果为50次实验的平均值，10组实验的具体参数设定如表2所示。其中，学习因子的 $c_1$， $c_2$ 值根据4.2.2的相关概念由算法动态设定，此处给出了手动设置的初值，惯性权重w根据公式(3)由算法动态改变，此处根据公式(3)给出了初值，粒子速度V、粒子位置X根据公式(1)、(2)由算法动态改变，此处由随机生成器给出初值，符号ram代表随机值。另外，本实验的每一组实验中其他对照算法的粒子数或个体数以及迭代次数或循环次数都与本文提出的IDPSO算法完全一样。

Table 2. Parameter value setting under different number of subtasks

表2. 不同子任务数下参数值的设置

5.3. 实验结果分析

在本文中，本文将改良的离散型粒子群算法IDPSO与OPSO [20]、FWPSO [27]、ZP-PSO [28]、S-ABC [16] 等算法进行对比，来验证本文提出算法的性能，本文将从算法的最优性(Optimality)、收敛性(Convergence)以及时间复杂度(Time Complexity)去衡量各个算法的性能，其中FWPSO、ZP-PSO是目前性能比较优良的粒子群算法，S-ABC算法是性能优良的人工蜂群算法，本实验中相同子任务数下的各个算法的迭代次数和个体数相等，具体分析情况如下。

5.3.1. 最优性

最优性Optimality反映算法的寻优能力的高低，即算法给出的服务组合方案在满足用户QoS限制的前提下其满足服务组合的质量有多高，本文中算法选择出的服务方案的适应度值fitness越小代表其最优性越优，最优性公式如公式(7)所示。其中同一子任务数下，最优算法适应度值保留最大有效位后的数，显然Optimality的值越小，其最优性越高。为验证本文提出的算法在Web服务组合选择领域的最优性，每个子任务可选择的候选单元服务数为100个，考察不同的子任务下，五种算法寻找最优解决方案的能力。具体实验结果如表3以及图4所示。

$Optimality=fitness$ (7)

Table 3. Comparison of optimality values of different algorithms under different number of tasks

表3. 不同任务数下不同算法的最优性值对比

Figure 4. Comparison of optimality values of different algorithms under different number of tasks

图4. 不同任务数下不同算法的最优性值对比

从表3和图4中可以看出，在测试的不同的子任务实验中，IDPSO算法所找到的服务组合方案的适应度值最小，即适应度值最优，这是因为本文设置的预防早熟机制对最优性起到了很大的作用，是本文实验中所有算法寻优性能中最高的。

5.3.2. 收敛性

收敛性Convergence反映算法寻优的速度快慢，本实验主要分析对比各个算法在不同子任务数下，迭代次数对服务组合的影响。相同子任务数下的各个算法的迭代次数和个体数相等，实验结果如图5所示。

(a) Influence of the number of iterations on optimality under 2 subtasks (b) Influence of the number of iterations on optimality under 8 subtasks (c) Influence of the number of iterations on optimality under 14 subtasks(d) Influence of the number of iterations on optimality under 20 subtasks

Figure 5. Influence of the number of iterations on optimality under different number of subtasks

图5. 不同子任务数下，迭代次数对最优性的影响

从图5中可以看出，在不同的子任务数下，各种算法所找到的平均最优适应度值随着迭代次数的增加呈现出不同的变化趋势。无论子任务数为多少，IDPSO算法收敛速度最快，这是因为本文设置的预防早熟机制对收敛性起到了很大的作用，因此IDPSO算法是本文实验中所有算法收敛速度中最高的。

5.3.3. 时间复杂度

时间复杂度Time Complexity为优化算法在相关参数设置一定的情况下，其算法的执行时间，时间复杂度反映算法在时间上的性能，本文将每个子任务对应的候选集设置为100个单元服务，在不同的子任务数下分别进行实验，在每组实验中，考察不同算法的时间复杂度即执行时间的多少。实验结果如表4和图6所示，其中执行时间单位为秒(s)。

Table 4. Comparison of time complexity of different algorithms under different number of subtasks

表4. 不同子任务数下不同算法的时间复杂度对比

Figure 6. Comparison of time complexity of different algorithms under different number of subtasks

图6. 不同子任务数下不同算法的时间复杂度对比

从表4和图6可以看出OPSO算法的时间性能是最好的，这是因为OPSO算法是最普通的粒子群算法，没有加入防止陷入局部最优机制，所以OPSO算法时间性能最高。但是在其他的几个算法中IDPSO算法的时间性能是最高的，这表明IDPSO算法的时间性能具有良好的表现。

6. 结论

本文针对服务组合问题提出了改良粒子群服务组合算法，该算法根据服务组合问题的特点从对候选服务集进行排序、合理设定控制参数、一定迭代次数后重置粒子位置、设置参照最优值四个方面来预防粒子早熟。实验表明本文所提出的算法在最优性、收敛性、时间复杂度三个方面都表现出良好的性能。但是，本文所提出算法的控制参数的设定并没有实现自动化的设定，此外，本文所提出的算法时间性能并没有明显的优势。未来，本研究打算使用机器学习的相关技术去实现算法控制参数的自动化设定，然后使用大数据的相关技术从历史服务方案中发掘先验知识去指导服务组合，企图降低算法的时间复杂度。

基金项目

国家重点研发计划资助“科技服务协同技术及平台研发”(编号2018YFB1402900)。

NOTES

^*通讯作者。