改进杜娟鸟搜索算法的Web服务组合优化

狄婧

摘 要： 传统的Web服务组合优化方法均基于Web服务的功能进行规划，获取的Web服务组合的服务性能较低，为了解决该问题，提出基于改进杜鹃鸟搜索算法的Web服务组合优化方法。首先从数据集中采集相似服务塑造Web服务组合集，然后采用杜鹃鸟搜索算法获取Web服务组合QoS最优化方案，并对杜鹃鸟搜索算法中莱维飞行时的路径和位置随机数进行改进，增强杜鹃鸟搜索算法在Web服务组合优化问题中的适应度，避免算法出现局部最佳解问题，得到优化的Web服务组合。实验结果表明该方法具有较高的运算效率和服务质量。

关键词： 杜鹃鸟搜索算法； Web服务； 组合优化； 最优方案

中图分类号： TN911?34； TP391 文献标识码： A 文章编号： 1004?373X（2017）15?0087?03

Abstract： Since the traditional Web service combination optimization method can plan on the basis of the function of Web service， and the obtained service performance of Web service composition is low， a Web service combination optimization method based on improved cuckoo search algorithm is put forward. The similar service is collected in dataset to shape the Web service group. The cuckoo search algorithm is used to acquire the QoS optimization scheme of Web service composition， improve the path of Levy flight and position random number in cuckoo search algorithm， strengthen the fitness of cuckoo search algorithm in Web service combination optimization problem， and avoid the problem of local optimal solution of the algorithm. The optimized Web service composition is obtained. The experimental results indicate that the method has high computing efficiency and service quality.

Keywords： cuckoo search algorithm； Web service； composition optimization； optimal scheme

0 引 言

随着当前云计算技术的快速发展，Web服务的应用领域也逐渐扩张，Web服务数量呈现海量增长趋势。为了增强Web服务的质量，Web服务组合的优化问题受到学者的广泛关注。以往研究出的Web服务组合优化方法大都基于Web服务的功能进行规划，未对服务质量进行全面的分析，获取的Web服务组合优化方法的服务性能大大降低[1]。因此，大量学者着手寻求高质量的Web服务组合优化方法。

在Web服务组合优化过程中采用杜鹃鸟搜索算法进行分析，通过杜鹃鸟搜索算法得到Web服务组合QoS最优化方案，不断改进杜鹃鸟搜索算法中Levy（莱维）飞行时的路径和位置随机数[2]，提高杜鹃鸟搜索算法在Web服务组合优化问题中的适应度。

1 QoS的Web服务组合问题

采用Web服务分析的数据集QWS对Web服务组合问题进行建模，通过Web服务爬虫引擎采集6 000个Web服务，各Web服务具有9个QoS特征。QWS数据集是一种全面的数据集，广泛应用于Web服务组合的QoS分析过程中。因此，通过QWS数据集獲取相似服务塑造Web服务组合集，采用杜鹃鸟搜索算法求解最优化的QoS组合问题，针对QoS组合问题中的服务响应时间（T）、执行成本（C）、服务价值度（A）以及服务稳定性（R）四种QoS参数进行分析，则QoS服务组合问题的表达式为：

式中：是对应的服务组合内的QoS运算公式，式（1）是目标函数，对和实施极小化处理。

在理想点的原理下，将多目标问题变换成单目标问题[3]，将全部Web服务中的服务响应时间以及执行成本的最低值当成理想点以及则获取的目标函数为：

式（2）是将QoS的服务组合问题从多目标问题变换成单目标问题的数学模型，基于目标系统的实际应用情况设置以及的值。

进行Web服务组合时，应在大量特定功能的小粒度Web服务内，采集满足用户要求的服务[4]，并将这些服务基于合理的组合方式塑造成功能完整的Web服务。通常状态下Web服务组合的目标以及原始规范都是已知的，也就是输入以及输出Web服务都已知，对Web服务组合进行优化时的Web服务数量以及组合方案都未知。一般在服务组合方案明确的状态下[5]，也就是提供候选服务集，并且候选服务集的组合方案已知，各候选服务集内存在不同的具体服务，从各候选服务集内获取最佳的Web服务方案，如图1所示。其反映的是构建在已知服务组合方案Plan下的Web服务组合流程。

图1描述的Web服务组合方案，在一个Web服务组合的工作流内，不同步骤的Web服务采集包含较多的有价值目标服务组件，获取所有有价值Web服务组合方案后[6]，采用式（2）的目标函数运算各策略的QoS值，可获取最佳的Web服务组合。当候选服务集存在海量的Web服务数量时，将大大降低Web服务组合优化效率，因此采用杜鹃鸟搜索算法降低目标函数的运算量，获取最佳的Web服务组合方案。

2 改进杜鹃鸟搜索算法的Web服务组合优化

2.1 改进杜鹃鸟搜索算法

杜鹃鸟搜索算法是在模拟杜鹃鸟的孵蛋行为以及Levy飞行的基础上产生的，原始杜鹃鸟搜索算法中存在如下前提条件[7]：

（1） 各杜鹃鸟一次仅下一个蛋，将蛋任意存储到一个鸟巢内。

（2） 对主巢内最优品种的杜鹃鸟蛋进行孵化，生成后续杜鹃鸟。

（3） 杜鹃鸟选择孵蛋的鸟巢数量固定，设置发现杜鹃鸟蛋的概率。

设置杜鹃鸟搜索算法的初始解为目标函数是采用运算解的适应度值；算法采用Levy飞行模式搜索鸟巢，是一种获取新解的过程；搜索算法此刻的最优适应度为如果新解的适应度同一致，则用新适应度值替换。

基于上文分析的三种前提条件，杜鹃鸟搜索鸟巢的位置也就是产生新解的修正公式为：

式中：分别用于描述第个鸟巢在第代以及第代条件下，第维的位置；是莱维飞行的跳跃路径，其是一种随机检索的路径，通过调控量对路径大小进行合理调控[8]。

对以及使用服从正态分布的随机数，可确保以及值正负交叉，增强Levy飞行方向的差异性，提高杜鹃鸟在不同区域间的飞行效率[9]，避免算法出现局部最佳解问题。

2.2 改进杜鹃鸟搜索算法的Web服务优化流程

改进算法的Web服务优化流程具体如下：

（1） 采用基于QoS的Web服务组合问题建模方法，将多目标的Web服务组合问题变换成单目标问题；

（2） 设置个杜鹃鸟巢，也就是个Web服务组合方案；

（3） 将不同杜鹃鸟巢中的解看成服务组合方案的解，分析服务组合是否符合式（1）描述的限制规范，如果符合，则运算目标函数的值[10]，并将获取的值当成解的适应度，如式（2）；

（4） 采用式（5）描述位置修正过程，对随机数以及采用改进后的选取方法产生个新解，分析新解是否符合式（1）描述的限制规范，同时记录原始最佳解；

（5） 基于被发现概率将产生新解；

（6） 采用式（2）运算各解的适应度，获取最小适应度对应的解，用该解替换最优解集；

（7） 分析是否达到最高迭代次数，达到则终止运算；否则，返回过程（4）。

具体流程如图2所示。

3 实验结果与分析

实验将改进杜鹃鸟搜索算法应用在基于QoS的Web服务最优化模型中，分析改进杜鹃鸟搜索算法的Web服务优化性能。实验采用数据集QWS中选择的Web服务构成服务组合，设置6个服务组，各服务组合中含有80个服务，设置不同的循环次数，对比分析两种方法获取的适应度值。基于改进杜鹃鸟搜索算法和标准杜鹃鸟搜索算法的Web服务组合的适应度值，见表1。

对比分析表1中的数据可得，相同循环次数条件下，相对于原始杜鹃鸟搜索算法的Web服务组合，采用本文提出的改进杜鹃鸟搜索算法的Web服务组合的适应度均值以及最小值都较优。

不同迭代次数下本文方法和原始方法的运算时间以及服务满意度分别如图3和图4所示。

分析图3可得，本文方法的运算时间低于原始方法，并且在1 000次迭代条件下，本文方法的运算时间低于1.8 s，说明本文方法可在短时间内获取符合用户要求的Web服务组合，运算性能强。分析图4可得，本文方法获取的Web服务组合的服务满意度远远高于原始方法，并且随着迭代次数的增加，服务满意度呈现平稳上升趋势，说明本文方法具有较高的服务质量。

4 结 语

为了提高Web服务组合优化过程中的服务质量，本文提出了基于改进杜鹃鸟搜索算法的Web服务组合优化方法，并通过实验检测该种方法的性能，能够看出本文方法获取的Web服务组合适应度较优，并具有较高的运算效率和服务质量。

参考文献

[1] 张以文，吴金涛，赵姝，等.基于改进烟花算法的Web服务组合优化[J].计算机集成制造系统，2016，22（2）：422?432.

[2] 倪志伟，方清华，李蓉蓉，等.改进蚁群算法在基于服务质量的Web服务组合优化中的应用[J].计算机应用，2015，35（8）：2238?2243.

[3] 徐甜，刘凌霞.基于改进遗传算法的Web服务优化组合研究[J].计算机应用与软件，2016，33（5）：24?27.

[4] 段立，侯兴哲，陈俐冰，等.基于改进DAG的Web服务组合优化[J].计算机系统应用，2015，24（2）：22?27.

[5] 高叶军，连志刚，曹宇.基于改进杜鹃鸟搜索算法的火电厂机组组合优化[J].电气自动化，2015，37（4）：64?66.

[6] 王野，周井泉，常瑞云.基于知识的人工蜂群服务组合优化算法[J].計算机技术与发展，2016，26（5）：46?50.

[7] 张晶，吴虎胜.改进二进制杜鹃鸟搜索算法求解多维背包问题[J].计算机应用，2015，35（1）：183?188.

[8] 方清华，倪丽萍，李一鸣.求解物流Web服务组合问题的两阶段多目标蚁群算法[J].中国机械工程，2016，27（10）：1327?1336.

[9] 冯艳，陈富赞.基于QoS多属性决策的Web服务组合优化方法[J].计算机工程，2015，41（6）：33?37.

[10] 张燕平，荆紫慧，张以文，等.基于离散粒子群算法的动态Web服务组合[J].计算机科学，2015，42（6）：71?75.