0 概述

面向服务计算和面向服务体系架构的推广和应用^[1], 促进了Web服务的发展。Web服务具有完全开放、松散耦合、具备标准协议和高度可集成等特征^[2], 基于Web服务技术^[3]并采用开放的可扩展标记语言定义的服务, 能够摆脱对平台的依赖, 实现服务重组, 动态满足用户的服务需求, 并且节约资源和时间。随着大数据时代的到来, Web服务数量剧增, 涌现出很多功能相似但非功能属性即服务质量(Quality of Service, QoS)不同的服务。如何在不同QoS的候选服务集合中高效实现服务的选择和组合, 使得组合服务能够满足客户的功能和非功能需求, 是一个典型的NP难题^[4]。

近年来, 针对基于QoS感知的Web服务组合问题, 国内外学者提出了各种改进的启发式算法, 获得了近似最优解。文献[5-6]通过融合其他方法来改进遗传进化(Genetic Evolutionary, GA)算法。其中:文献[5]借助模拟退火以及和声搜索算法改进GA算法的交换策略; 文献[6]通过对候选服务集局部选优的方式缩小搜索空间, 提升GA算法性能。由于粒子群优化(Particle Swarm Optimization, PSO)算法参数少、收敛速度快, 因此文献[7-8]对其改进后用于解决服务组合问题:文献[7]通过迭代生成的余切序列扰乱粒子的运动速度和位置, 提升PSO算法的全局搜索能力; 文献[8]通过优化PSO算法的惯性权重和学习参数的方式提升算法的寻优能力, 但PSO算法普遍存在“早熟”现象, 易陷入局部最优解。文献[9-10]提出一种基于差分进化(Differential Evolution, DE)算法的服务组合方法:文献[9]通过一种新型的编码方式提高算法的寻优能力, 但算法在大规模组合服务情况下性能较差; 文献[10]通过引入结构知识, 提出基于知识的差分进化(Knowledge-based DE, KDE)算法, 加快了算法的收敛速度。针对大规模服务组合问题, 文献[11-12]将人工蜂群(Artificial Bee Colony, ABC)算法应用于Web服务组合优化:文献[11]通过精英策略增强搜索能力; 文献[12]采用一种受差分进化启发的搜索策略提高搜索效率。此外, 文献[13]提出一种扩展的花朵授粉(Extended Flower Pollination Algorithm, EFPA)算法, 在花朵授粉算法的基础上引入GA算法的变异和交换策略, 进一步提升了算法性能。

本文提出一种改进的花朵授粉(Improved FPA, IFPA)算法用于优化Web服务组合。将差分进化算法的变异和交换操作加入到花朵授粉算法中, 增强花朵的有效性和多样性, 并利用贪心策略选择适应度值高的花朵, 从而加快算法收敛速度, 增强算法寻优能力, 提高组合服务性能。

1 Web服务组合问题 1.1 QoS感知的Web服务组合

针对客户提出的服务需求, 可将需求抽象为n种功能不同的子任务T=(t₁, t₂, …, t_n)。在执行子任务t_i时, 可从相关候选服务集S_i=(s_i1, s_i2, …, s_im)中选择服务s_ij来完成相应子任务。服务s_ij包含k种QoS属性Q_ij=(q_ij¹, q_ij², …, q_ij^k), 最后生成组合服务CS=(s_1j1, s_2j2, …, s_njn), j_i∈{1, 2, …, m}, 其QoS属性满足客户所提出的要求。

工作流管理联盟(WFMC)提出的顺序(Sequence)、循环(Circular)、选择(Selective)和并行(Parallel)4种工作流管理模型结构, 可支持Web服务组合建模, 其中, 并行、选择和循环3种基本模型均可转化为顺序类型。为便于讨论, 本文只讨论顺序模型。

1.2 QoS属性值及其归一化

本文引入QoS属性计算组合服务的适应度值, 用于评价Web服务组合的非功能特性。具体可选取Web服务的可靠性(rel)和可用性(ava)这两种效益型属性和响应时间(rtm)、价格(cos)这两种成本型属性来描述服务质量^[14]。

Web服务不同的QoS属性具有不同的衡量方式, 因此, 在计算组合服务的适应度之前必须对QoS属性值进行预处理。本文借鉴文献[10]方法对QoS进行归一化操作, 计算公式如下:

$ q_{ij}^{k\prime } = \left\{ {\begin{array}{*{20}{l}} {\frac{{\max \left( {q_i^k} \right) - q_{ij}^k}}{{\max \left( {q_i^k} \right) - \min \left( {q_i^k} \right)}},k \in \{ {\rm{rtm}},\cos \} }\\ {\frac{{q_{ij}^k - \min \left( {q_i^k} \right)}}{{\max \left( {q_i^k} \right) - \min \left( {q_i^k} \right)}},k \in \{ {\rm{rel}},{\rm{ ava }}\} } \end{array}} \right. $

(1)

其中, q_ij^k表示第i个任务第j个候选服务的第k个QoS属性值, q_i^k表示完成第i个任务任一候选服务的第k个QoS属性值。

1.3 QoS聚合函数

不同服务的QoS属性具有不同的特性, 其对应的QoS聚合函数也有所不同, 本文借鉴文献[15], 采取累和及累积两种操作。

组合服务的响应时间和价格属性通过原子服务累和而成, 聚合函数如下:

$ {Q_k} = \sum\limits_{i = 1}^n {q_i^k} ,k \in \{ \cos ,{\rm{rtm}}\} $

(2)

组合服务的可用性和可靠性属性通过其原子服务累积而成, 聚合函数如下:

$ {Q_k} = \prod\limits_{i = 1}^n {q_i^k} ,k \in \{ {\rm{ava}},{\rm{ rel}}\} $

(3)

通过加权求和的方式计算组合服务CS的服务质量, 服务组合优化的数学模型可表示为:

$ \left\{ {\begin{array}{*{20}{l}} {y = \max \left( {{Q_{{\rm{cs}}}}} \right)}\\ {{Q_{{\rm{cs}}}} = \sum {{w_k}} {Q_k}}\\ {{Q_k} \le {C_k}} \end{array}} \right. $

(4)

其中, n为服务组合中任务的个数, Q_k为组合服务的某种QoS属性值, C_k为这种QoS属性的约束条件, w_k为第k种QoS属性在总服务质量中所占权重, $\sum\limits_{k \in \{ {\rm{rtm}}, {\rm{cos}}, {\rm{ava}}, {\rm{rel}}\} } {{w_k}} = 1$且0 < w_k < 1。由式(4)可以看出, Q_cs值越大, 组合服务质量越好。

2 基于IFPA算法的服务组合优化 2.1 花朵授粉算法

花朵授粉算法(FPA)由YANG等人于2012年提出, 其是一种新型的元启发式群智能优化算法。FPA模拟植物界中花朵授粉的方式, 主要有自花授粉和异花授粉两种方式^[16]。该算法通过转换概率实现局部搜索和全局搜索的动态转换, 平衡两者之间的关系。FPA按照以下规则进行设计:

1) 花朵的异花授粉被视为全局搜索, 传粉者飞行传粉服从Levy分布。

2) 花朵的自花授粉被视为局部搜索。

3) 花朵的常性是指两朵相近的花朵更易授粉, 可以认为是一种繁衍概率, 与两朵花之间的相似度成比例。

4) 局部授粉和全局授粉的动态转换由概率p控制。

在异花授粉(全局搜索)过程中, 传粉者通过Levy飞行机制进行传粉, 其寻优演化可表示为:

$ x_i^{t + 1} = x_i^t + L\left( {{\rm{gBest}} - x_i^t} \right) $

(5)

其中, x_i^t为第t代种群中第i朵花的位置, gBest为当前最优解, L为服从Levy分布的随机变量。L的计算公式如下:

$ L\sim\frac{{\lambda \Gamma (\lambda )\sin ({\rm{ \mathit{ π} }}\lambda /2)}}{{\rm{ \mathit{ π} }}} \times \frac{1}{{{s^{1 + \lambda }}}},0 < {s_0} < < s $

(6)

其中, λ=1.5, Γ(λ)为标准伽马函数。

自花授粉(局部搜索)在花朵附近区域进行搜索, 可表示为:

$ x_i^{t + 1} = x_i^t + \varepsilon \left( {x_j^t - x_k^t} \right),i \ne j \ne k $

(7)

其中, ε为[0, 1]之间的随机数。

2.2 IFPA算法的差分进化机制

差分进化(DE)算法是一种基于群体的进化方法^[17], 包括初始化、变异、交换、选择等步骤。DE算法流程简单, 易于实现^[18-19]。

研究表明, 标准的花朵授粉算法存在一些缺陷, 如收敛速度慢、在高维情况下易早熟、全局搜索能力差等。针对上述不足, 本文将差分进化算法的变异、交换操作加入到花朵授粉算法中, 以增强花朵的有效性和多样性, 并利用贪心策略选择适应度值高的花朵, 以加快算法收敛速度, 增强FPA算法的寻优能力。

2.2.1 变异操作

FPA基于种群X^t=(x₁^t, x₂^t, …, x_N^t)寻优, 通过差分变异操作引入种群全局信息和个体局部信息, 进一步提升搜索能力, 增加种群的多样性。在t代种群中, 第i个个体是x_i^t=(x_{i, 1}^t, x_{i, 2}^t, …, x_{i, n}^t), 其中, n是子任务的个数。通过式(8)处理x_i^t, 得到新个体v_i^t, 即:

$ \mathit{\boldsymbol{v}}_i^t = \mathit{\boldsymbol{x}}_{{r_1}}^t + \delta \left( {\mathit{\boldsymbol{x}}_{{r_2}}^t - \mathit{\boldsymbol{x}}_{{r_3}}^t} \right) $

(8)

其中, i≠r₁≠r₂≠r₃且i, r₁, r₂, r₃∈[1, N], δ为缩放因子, δ∈(0, 1)。

2.2.2 交换操作

为提高种群的多样性, 利用原向量x_i^t和变异个体v_i^t进行交叉操作, 生成新的个体u_i^t:

$ u_{i j}^{t}=\left\{\begin{array}{l} v_{i j}^{t}, C_{\mathrm{rand}}<\mathrm{CR} \text { 或 } j=\text { unidrand }(N) \\ x_{i j}^{t}, \text { 其他 } \end{array}\right. $

(9)

其中, u_ij^t、v_ij^t和x_ij^t为t代种群中第i个个体在j维上的值, C_rand为(0, 1)之间的随机数, CR为(0, 1)之间的交叉概率, unidrand(N)为[1, N]之间的随机整数。最后得到新种群U^t。

2.2.3 选择操作

为加快算法的收敛速度, 直接将种群X^t和变异、交换后的种群U^t混合, 依据贪心策略, 按适应度值选取N个花朵个体组合成新的种群X^t+1。

2.3 服务组合建模 2.3.1 编码方式

本文采用整数编码方式表示离散的服务, 利用一个整数数组S=(s₁, s₂, …, s_n)表示服务组合的一个解决方案(即一个花粉或花朵), 将寻找最优组合服务问题转化为向量S求最优解问题, 其中, 每个整数s_i都代表相应任务中选择的候选服务索引的序列号。计算每个花粉S的适应度值, 对该花粉所对应的服务组合方案进行评估, 判断组合服务的优劣。

2.3.2 适应度函数

适应度函数作为Web服务组合评估函数, 计算方法有很多, 为便于比较, 本文根据服务组合优化数学模型, 对于按式(2)累和的属性进行取平均数操作, 对于按式(3)累积的属性进行开方操作, 最终使适应度函数的值介于(0, 1)之间。同时, 借鉴文献[1]引入罚函数来构造适应度函数, 将约束优化问题转变为无约束优化问题, 实现全局最优化。综合考虑本文所选取的QoS属性, Web服务组合的适应度函数值fitness表示如下:

$ \begin{array}{l} {\rm{ fitness }} = {\sum\limits_{k \in \mid \cos ,{\rm{rtm}}\} }}{w_k}\frac{{{Q_k}}}{n} + \sum\limits_{k \in \left\{ {{\rm{ava}},{\rm{rel}}} \right\}} {{w_k}} \sqrt[n]{{{Q_k}}}{f_q} - \lambda \times \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\sum\limits_{k \in \{ \cos ,{\rm{rtm}},{\rm{ava}},{\rm{rel}}\} } {{{\left( {\frac{{\Delta {Q_k}}}{{Q_k^{\max } - Q_k^{{\rm{min}}}}}} \right)}^2}} \end{array} $

(10)

其中, λ为惩罚系数, Q_k^max为对k属性的最大约束值, Q_k^min为对k属性的最小约束值。

$ \Delta {Q_k} = \left\{ {\begin{array}{*{20}{l}} {Q_k^{\min } - {Q_k},{Q_k} \le Q_k^{\min }}\\ {0,Q_k^{\min } < {Q_k} < Q_k^{\max }}\\ {{Q_k} - Q_k^{\max },{Q_k} \ge Q_k^{\max }} \end{array}} \right. $

(11)

2.4 服务组合算法描述

本文将提出的IFPA算法应用于服务组合优化问题, 该算法的具体步骤如下:

步骤1  初始化参数, 初始化种群规模N、最大迭代次数t_max、转换概率p、最小缩放因子δ和交叉概率CR。

步骤2  初始化种群, 并根据适应度函数计算当前种群适应度值, 记录全局最优值及其对应的最优解。

步骤3  如果转化概率p < rand(0, 1)成立, 则进行全局搜索, 根据式(5)对解进行更新, 并做越界处理。

步骤4  如果转换概率p>rand(0, 1)成立, 则进行局部搜索, 根据式(7)对解进行更新, 并做越界处理。

步骤5  计算步骤3或步骤4新生成的花朵适应度值, 并与原花朵个体的适应度值进行比较, 如果新的个体适应度值更高, 则用新个体替换旧个体, 同时记录整个种群的最优值和最优解, 最终得到新种群X^t。

步骤6  利用DE算法中的式(8)对整个种群进行变异操作, 并对变异后的种群V^t做越界处理。

步骤7  利用DE算法中的式(9)对种群X^t和变异种群V^t进行交换操作, 得到最终的新种群U^t, 并计算新种群U^t中每个个体的适应度值。

步骤8  从种群X^t和种群U^t中按贪心策略选取适应度较高的N个花朵个体, 组成新的第(t+1)代种群X^t+1, 并更新全局最优值和最优解。

步骤9  判断结束条件, 如果满足, 则退出并输出最优值和对应的最优解, 否则转步骤3。

3 实验与结果分析 3.1 实验环境和数据

通过仿真实验, 验证IFPA算法对基于QoS感知的Web服务组合优化的有效性, 分别从可行性和收敛性2个方面对IFPA、KDE^[13]和EFPA^[14]3种服务组合优化算法, 以及DE和FPA 2种传统优化算法进行比较。实验环境为:Windows 10, 64位操作系统, 英特尔Core i7-7700HQ@2.80 GHz四核处理器, 8 GB内存。

实验选用2个不同的数据集D1和D2。数据集D1是由ZENG等人提供的QWS数据集^[20-21], 该数据集收录了互联网中2 507个Web服务, 包含9个非功能属性。本文从中选出响应时间、可用性, 可靠性这三大属性, 同时随机生成数据集中没有的价格属性, 并以这4个属性评价服务质量。数据集D2是随机生成的, 共收录13 000个Web服务, 包含本文实验所需的QoS属性。

为模拟真实情况下的Web服务组合优化过程, 本文实验设置4种不同子任务数{10, 15, 20, 25}, 并且设置4种不同数量{25, 50, 75, 100}的候选服务集。为保证实验的有效性和正确性, 将5种优化算法在同一数据集上进行实验, 并且每组实验重复40次。

3.2 实验参数设置

实验中种群大小均设为30, 最大迭代次数均设为200次, 4个不同的QoS属性权重分别设为:rtm=0.2, ava=0.2, rel=0.3, cos=0.3, 5种群体智能优化算法的参数如表 1所示。

3.3 可行性分析

以上文提出的适应度函数评价组合服务的服务质量, 适应度值越大代表服务质量越好, 组合服务的质量越好; 反之, 服务质量越差。为验证IFPA算法在Web服务组合领域的可行性, 在不同任务数与候选服务数的情况下, 比较5种优化算法的寻优性能。此时选取D1数据集, 实验结果如表 2所示。为验证IFPA在大规模服务组合情况下的可行性, 候选服务数均设为100, 此时选取D2数据集, 实验结果如图 1所示。

由表 1可以看出, 在不同任务数和不同候选服务数情况下, 相比于其他4种优化算法, IFPA的适应度值均为最高, 即组合服务的质量最好, 验证了IFPA算法的可行性。由图 1可以看出, 在大规模服务组合情况下, IFPA算法也始终优于其他算法。由于IFPA在D1、D2数据集上表现均比其他算法优秀, 因此其不仅可行, 而且寻优性能更好。

3.4 收敛性分析

为分析IFPA的收敛性, 比较不同任务数下5种算法的收敛情况, 即迭代次数和平均适应度之间的关系。在较少的迭代次数下获得较高的平均适应度值, 表示收敛能力较好; 反之, 表示收敛能力较差。实验选取D1数据集, 候选服务数设为100, 结果如图 2所示。

由图 2可以看出, 随着任务数的增加, 5种算法的收敛性能均有所下降。当任务数为10和15时, IFPA算法在迭代到50次时就基本已经收敛; 而当任务数为20和25时, IFPA算法在迭代50次时还未收敛。在4种不同任务数的情况下, IFPA、KDE和EFPA算法的收敛性能优于DE和FPA两种传统优化算法, 同时IFPA算法的平均适应度值都高于另外4种优化算法, 而KDE、EFPA则陷入局部最优解。相比之下, IFPA算法不仅收敛快, 而且寻优性能更好。

4 结束语

针对基于QoS感知的Web服务组合优化问题, 本文提出一种改进的花朵授粉算法, 以提高组合服务的服务质量。该算法具有较好的全局搜索能力, 其通过变异、交叉的方式提升种群多样性, 并借助贪心策略提高收敛速度。实验结果验证了该算法在寻优和收敛方面的优越性。本文主要基于静态QoS属性研究Web服务组合优化问题, 但在实际情况下, QoS属性值都是动态变化的, 并且不同属性之间可能存在某种关联关系。因此, 下一步将从动态变化的QoS值以及属性之间的关联这两方面着手, 对本文算法做进一步优化。