烟花粒子群优化算法在Web服务组合上的应用

郭 星，陈姗姗，张以文，李 炜

1(安徽大学 计算智能与信号处理教育部重点实验室，合肥 230039)

2(安徽大学 计算机科学与技术学院，合肥 230601)

1 引 言

随着大数据与云计算技术的发展，越来越多的企业与组织机构以服务的形式发布他们的应用资源[1]，Big service[2]应运而生.单一的Web服务往往不能满足复杂的用户需求，服务组合变得相当重要[3].服务组合过程中存在大量功能相同而QoS不同的候选服务，QoS感知的服务组合已成为研究热点.QoS通常包括：响应时间、可用性、吞吐量等[4].

针对QoS感知的Web服务组合优化问题，目前的解决方法可分为三种[5]：

1)局部搜索方法，不同的QoS属性值通过一个聚合函数被映射为单一指标，在多指标决策过程中，从每个候选服务集中选择一个具体的服务来构成一个组合服务.这种方法对于有少量QoS限制条件的服务组合有效果，但对于大规模的有QoS属性限制的服务组合效率很低.

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

3)智能优化算法，解决了全局优化算法的缺点，常被用来解决服务组合问题.文献[6]给出有关联关系的服务模型，使用遗传算法来进行服务组合查找，提出了一种云制造中有关联意识的服务组合选择方法.

文献[7]使用粒子群算法来解决Web服务组合优化问题.作为解决服务优化问题的两种典型算法，与遗传算法相比，粒子群算法具有参数少、收敛速度快的特点，在很多优化问题上表现出良好的搜索能力，但粒子群算法也会出现早熟现象，容易产生陷入局部最优问题[8].文献基于适应性并行与串行小生境技术提出了一种子种群粒子群优化算法[9]，在子种群的网格搜索单元中，根据可行解的密度来寻找最优解，在增加种群的搜索能力的同时，种群多样性会降低.文献[10]提出了一种将候选服务分类的方法，来解决大规模的Web服务组合问题.本文针对全局服务质量的Web服务组合优化问题，提出了一种改进的粒子群算法FWPSO，在增加种群多样性的同时，进行了防早熟处理，并提高了种群的搜索能力.理论分析和实验结果表明，在Web服务组合优化问题上，FWPSO有更好的综合性能.

2 Web服务组合问题模型

2.1 组合服务生成过程

组合服务的生成过程是一个根据用户提交的任务信息，来寻找满足用户要求的组合服务过程.其过程主要分两步进行，即服务寻找过程与服务组合过程.在服务寻找过程中，将用户提交的任务抽象为多个子任务，各个子任务间有不同的执行关系.在基于工作流方法的Web服务组合中，对于子任务的执行关系，工作流管理联盟(WFMC)定义了4种基本模型，即顺序(Sequence)、并行(Parallel)、选择(Selective)，循环(Circular)等.在定义的基本模型中，循环、并行与选择模型均可转化为顺序模型，本文选取顺序模型作为研究对象.每个子任务对应一个候选服务集，候选服务集由多个有着功能性相同而非功能性属性不同的服务构成，这些服务的每个属性都满足用户的需求.每个子任务根据用户提交的QoS属性要求，从相应的候选服务集中选择一个候选服务.

2.2 QoS预处理

在组合服务的生成过程中，为了评估每个组合服务，需要计算组合服务的适应度值.由于Web服务的QoS每个属性取值范围有较大差别，不在同一个计算等级上，在进行Web服务评估之前，必须先将QoS属性值进行预处理.属性值预处理方法有多种，本文使用文献[7]中方法对Web服务的属性进行与处理，将属性值区间限定为[0，1].

3 基于FWPSO算法的服务组合

3.1 标准粒子群算法

(1)

(2)

其中，c1和c2为学习因子，决定全局最优位置和历史最优位置对粒子的影响程度，r1和r2为[0，1]区间上均匀分布的随机变量.w为惯性权重，衡量着迁移时刻的速度对下次移动的影响，w值越大，表明此刻的速度对粒子下次移动的影响较大.

3.2 FWPSO算法的改进机制

3.2.1 粒子活跃度检测

在种群粒子寻找最优解的过程中，粒子的多样性对种群寻找最优粒子有较大影响，也决定了使用粒子群算法能否找到最优的组合服务.根据搜索策略，经过多次搜索，若粒子活动范围小，则寻优效果对整个种群影响不大.在本文中，引入粒子活跃度检测机制，通过粒子的活跃度检测，来替换不活跃粒子，增加种群多样性.机制具体思想：在迭代过程中，记录每个粒子的历史最优位置未更新次数，若粒子不是种群最优粒子，且粒子的历史最优位置未更新次数达到一定的阈值，则认为此粒子的活动范围较小，活跃度不高，多次迭代未能逃离粒子局部搜索区域，找到的历史最优解决方案不变.通过重新初始化此粒子，随机获取粒子的位置，增加种群多样性.

3.2.2 粒子烟花学习机制

在种群粒子寻找Web组合服务的最优解决方案过程中，每个粒子的历史最优位置对粒子的移动有较大影响.本文中，采用一种新的粒子学习机制，在粒子的历史最优位置周围寻找更优的粒子，增强种群粒子的搜索能力.我们采用烟花算法[12]中的基于烟花爆炸半径计算原理寻找最优解的思想来指导粒子学习.对于一个多目标求解问题，每个烟花被看作一个可行解，采取烟花爆炸学习机制，在粒子历史最优位置周边进行搜索.根据烟花爆炸半径的公式计算粒子在历史最优位置的搜索半径.烟花爆炸半径如公式(3)所示：

(3)

粒子进行烟花学习的算法流程如下：

Algorithm1粒子烟花学习机制

For each i

If(the ith particle is not best particle)

Gengrate Ai

For(j

End for

End if

End for

3.2.3 粒子自反向学习

在种群粒子搜索过程中，全局最优粒子对于种群粒子位置的迁移具有牵引作用.经过多次迭代，种群大量粒子会围绕在局部最优粒子周围，种群粒子寻找组合服务最优解决方案的范围逐渐缩小.为解决这一问题，引入粒子反向学习机制[13]，牵引种群粒子离开局部范围.具体方法如下：

1)构建学习对象：为了在种群陷入局部最优情况下使粒子迅速逃离局部最优区域，需要构建粒子的学习对象：粒子历史最差位置和初始全局较差粒子位置.种群粒子在搜索过程中记录历史最差位置，在进行反向学习时，每个粒子根据历史最差位置进行更新.种群在后期搜索过程中逐渐陷入局部最优区域，构造初始全局较差粒子，可以有效牵引种群移动.为增加种群反向学习的多样性，在初始时构造m个较差粒子，当种群需要反向学习时，从这些m个较差粒子中随机选出一个作为学习对象.

m个较差粒子应该满足以下两个条件：第一，粒子应有较差的适应度值，可以保证粒子在种群陷入局部最优时沿着运动的反方向逃出局部最优区域；第二，这些粒子应均匀分布在搜索区域中，可以保证种群粒子反向学习的多样性.使用欧氏距离来计算这些粒子两两间的距离，只有大于给定的阈值，才是理想的学习对象.选取的阈值计算公式(4)：

(4)

其中ximax和ximin分别为粒子第i维的取值上限和下限，即代表在候选服务集WSi中可选择的服务个数，n为粒子搜索维度，代表组合服务中的子任务个数.在初始种群时，选出达到要求的粒子不足m个，则再随机生成新的粒子，检测是否满足要求，直至选出m个粒子.

2)反向学习：当检测到种群全局最优位置在一定迭代次数内未更新，则认为整个种群陷入缓慢移动状态，开始执行反向学习策略.反向学习第i个粒子的速度更新公式为：

(5)

3.3 服务组合算法

针对服务组合问题，使用改进的粒子群算法FWPSO来寻找最优的组合服务.我们先对种群粒子编码处理，根据适应度值函数对种群粒子选出的组合服务解决方案进行评估，选出种群中最优的服务组合方案.

3.3.1 粒子编码

在进行组合服务的选择时将一个粒子看作一个组合服务的解决方案，寻找最优组合服务.分解的抽象子任务T=(T1，T2，…，Ti，…，Tn)代表粒子的各维搜索空间，n代表分解的抽象子任务个数，同时也表示粒子的搜索空间有n维.每个抽象子任务所对应的候选服务集WSi中Web服务的个数设为m个，即表示粒子在这一维搜索空间中的最大向量长度.具体编码模式如图1所示：

图1 组合服务的编码Fig.1 Theencoding of composition service

粒子选出各维的向量值后就完成了Web服务组合解决方案的选择.通过适应度值评估函数对每个粒子所对应的组合方案进行评估，来寻找最优解的服务组合方案.使用这种编码方式，Web服务的组合选择问题即可转化为n元向量的求解问题，即寻找最优向量(x1，x2，…，xi，…，xn)的过程.

3.3.2 适应度函数设计

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

(6)

3.3.3 算法描述

基于以上分析和设计，下面给出服务组合优化算法描述.

Algorithm2：FWPSO

Input：N，m，Vmax，Vremax，Ltimes，N1，RLs，T

Output：Pgbest

Initialization N particles

Compute fitness

Generate the m worst particles

t=0

For i

Update position and speed

Compute fitness

If( activeness is slow)

Initlization the ith particle

End if

End for

Perform the explosion learning strategy

If(the standard of reserve learning )

While(j

For each i

Updateparticle

End for

For each N1

Update particle

End for

End while

End if

t=t+1

Generate the best particle

4 实验设计与结果分析

4.1 实验数据与环境

在本文中，我们将改进的粒子群算法与IDPSO[10]、ZPSO[14]算法进行对比，来验证我们提出的改进算法的优化效率.实验数据采用Zeng等的QWS公用有效数据集[15，16].在本文实验中，我们分别测试了不同的子任务数，并将QWS数据集中的服务分别分配到这些子任务中，用来作为子任务的候选服务集.我们选择数据集其中的4个属性作为本文QoS评价指标，即响应时间(RT)，可用性(A)，吞吐量(T)，可靠性(Rel)，weight(RT，A，T，Rel)=(0.2，0.3，0.2，0.3) 为用户偏好.实验环境为Windows 7 OS，Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz，16GB RAM，64位操作系统.

4.2 实验参数设置

实验具体参数设定如表1所示.本文中每组实验均进行50次，实验最终结果为50次实验的平均值.

表1 参数设置Table 1 Parameter setting

其中，反向学习阈值是指全局最优粒子的位置的连续未变化的迭代次数，当达到反向学习阈值时，种群粒子开始进行反向学习.在反向学习阶段，整个种群中有N1个反向学习的粒子，速度不会超过最大反向学习速度；剩下的粒子仍然以正向速度进行正向学习，速度会小于最大正向学习速度.在对粒子活跃度检测时，若粒子的历史最优位置达到检测阈值时，将此粒子废弃，重新初始化新粒子.

4.3 可行性

为验证本文提出的算法在Web服务组合选择领域的可行性，在迭代次数为500次，每个子任务可选择的候选服务数为100个，考察不同的子任务数下，三种算法寻找最优解决方案的能力，具体的实验结果如表2所示.

表2 适应度值对比Table 2 Comparison results of fitness values

从表2中可以看出，在测试的不同的子任务数实验中，FWPSO算法所找到的组合服务的适应度值较优.

4.4 收敛性

本组实验主要分析FWPSO算法应用在Web服务组合选择的收敛度问题上，在本组实验中，我们将每个子任务对应的候选服务集设置为100个服务，在不同的子任务数下分别进行实验，在每组实验中，考察迭代次数对组合服务选择的影响.实验结果如图2至图5所示.

图2 5个子任务数下,迭代次数对平均适应度值的影响Fig.2 Influence of the iteration number on the average fitness of 5 subtasks图3 10个子任务数下,迭代次数对平均适应度值的影响Fig.3 Influence of the iteration number on the average fitness under10 subtasks图4 15个子任务数下,迭代次数对平均适应度值的影响Fig.4 Influence of the iteration number on the ave-rage fitness under 15 subtasks图5 20个子任务数下,迭代次数对平均适应度值的影响Fig.5 Influence of the iteration number on the average fitness under 20 subtasks

从图中可以看出，在不同的子任务数下，各种算法所找到的平均最优适应度值随着迭代次数的增加呈现不同的变化趋势.IDPSO算法的收敛虽然也较快，但其最终收敛的适应度值劣于FWPSO算法.相比之下，无论子任务数为多少，FWPSO算法的收敛速度较快.

5 结 论

本文研究了改进的粒子群算法在Web服务组合优化问题中的应用，提出FWPSO算法，解决了传统粒子群算法在服务组合优化领域中的一些问题.在改进的FWPSO算法中，我们通过粒子活跃度检测机制，剔除不活跃粒子，增加种群粒子的多样性，引入烟花算法中烟花爆炸搜索的理论，改进了粒子的学习策略，增强种群的搜索能力，使用粒子的反向学习，有效解决了种群陷入局部最优问题.在仿真实验中，我们对改进的算法的可行性、收敛性等方面进行了研究，实验结果表明，本文提出的改进粒子群算法FWPSO在Web服务组合优化问题上的综合性能更高，在下一步工作中，我们将研究服务组合优化领域中，服务组合关联度对服务选择问题的影响.

：

[1] Yao Y，Cao J，Jiang Y，et al.An optimal engine component placement strategy for cloud workflow service[C].IEEE International Conference on Web Services，2016：380-387.

[2] Xu X，Sheng Q Z，Zhang L J，et al.From big data to big service[J].IEEE Computer，2015，48(7)：80-83.

[3] Klai K，Ochi H.Model checking of composite cloud services[C].IEEE International Conference on Web Services，2016：356-363.

[4] Barakat L，Miles S，Poernomo I，et al.Efficient multi-granularity service composition[C].IEEE International Conference on Web Services，2011：227-234.

[5] Huo Y，Zhuang Y，Gu J，et al.Discrete gbest-guided artificial bee colony algorithm for cloud service composition[J].Applied Intelligence，2015，42(4)：661-678.

[6] Jin H，Yao X，Chen Y.Correlation-aware QoS modeling and manufacturing cloud service composition[J].Journal of Intelligent Manufacturing，2015：1-14.

[7] Wen Tao，Sheng Guo-jun，Guo Quan，et al.Web service composition based on modified particle swarm optimization[J].Chinese Journal of Computers，2013，36(5)：1031-1046.

[8] Chen Y，Huang J，Lin C.Partial selection：an efficient approach for QoS-aware web service composition[C].IEEE International Conference on Web Services，2014：1-8.

[9] Liao J，Liu Y，Zhu X，et al.Accurate sub-swarms particle swarm optimization algorithm for service composition[J].Journal of Systems and Software，2014，90(1)：191-203.

[10] Zhang Y，Jing Z，Zhang Y.MR-IDPSO：a novel algorithm for large-scale dynamic service composition[J].Tsinghua Science and Technology，2015，20(6)：602-612.

[11] Eberhart R，Kennedy J.A new optimizer using particle swarm theory[C].Proceedings of the Sixth International Symposiumon Micro Machine and Human Science，1995：39-43.

[12] Tan Y,Zhu Y.Fireworks algorithm for optimization[C].International Conference in Swarm Intelligence,Springer，Berlin,Heidelberg,2010:355-364.

[13] Xia X，Liu J，Li Y.Particle swarm optimization algorithm with reverse-learning and local-learning behavior[J].Journal of Software，2014，9(2)：350-357.

[14] Zhang T.QoS-aware Web service selection based on particle swarm optimization[J].Journal of Networks，2014，9(3)：565-570.

[15] Zeng L，Benatallah B，Dumas M，et al.Quality driven web services composition[C].Proceedings of the 12th International Conference on World Wide Web，2003：411-421.

[16] Zeng L，Benatallah B，Ngu A H H，et al.Qos-aware middleware for web services composition[J].IEEE Transactions on Software Engineering，2004，30(5)：311-327.

[17] Seghir F，Khababa A.A hybrid approach using genetic and fruit fly optimization algorithms for QoS-aware cloud service composition[J].Journal of Intelligent Manufacturing，2017：1-20.

附中文参考文献：

[7] 温 涛，盛国军，郭 权，等.基于改进粒子群算法的Web服务组合[J].计算机学报，2013，36(5)：1031-1046.