2019, Vol. 40
2. 东北大学 计算机科学与工程学院, 辽宁 沈阳 110169
2. School of Computer Science and Engineering, Northeastern University, Shenyang 110169, China
Web服务组合是服务计算研究的热点问题之一, 其基本思想是按照一定的条件将运行在互联网上的Web服务提供者所提供的服务进行组合, 产生满足用户需求的高质量的服务, 进而实现服务的增值[1].当前, 互联网上有很多功能相同但QoS不同的Web服务, 这样会形成很大的搜索空间, 使得服务组合更为复杂.基于QoS的Web服务组合的局部优化研究比全局优化研究要成熟, 但是全局优化更具有实际作用.解决全局优化的方法大致可以分为两类[2]:一类是穷举法, 即穷举出所有可能的结果, 然后选择最优的一个, 这种方法的时间复杂度很大; 另一类是近似寻优算法, 如GA，PSO，ACO等算法.这类算法的时间复杂度远小于穷举法, 而且在用于Web服务组合中有很多优势.
2005年, Karaboga提出的人工蜂群(ABC)算法, 具有收敛速度快, 易于编程实现, 可以并行化等优点[3].该方法常被用来求解复杂的多目标优化问题, 文献[4]针对多目标服务组合优化问题求解中的搜索效率问题对人工蜂群算法中的搜索策略进行了改进; 文献[5]考虑了求解多目标作业调度组合优化问题的进化问题, 对初始种群的产生、进化策略作了改进; 文献[6]将人工蜂群算法应用到作业调度组合优化问题中, 对算法中的交叉算子和外部文档引入算法作了改进.目前, 人工蜂群算法可以有效地解决连续域上的优化问题, 在离散域上则研究较少.
本文设计了一种兼顾蜂群探索和开发行为的进化策略, 在算法流程中采用外部集合记录和Pareto最优解, 并将这些改进应用于Web服务组合领域.仿真实验结果表明, 改进后的多目标人工蜂群算法在算法收敛性和均匀性方面有提高, 在Web服务组合优化方面, 取得了较好的优化效果, 提高了寻优精度、解的质量和收敛速度.
1 Web服务组合问题设每一个复杂的任务T可以被分解为m个抽象子任务{T1, T2, …, Tm}, 每个抽象子任务代表一个抽象服务si, si为一组具有相同功能但QoS不同的服务[7].每个抽象服务又包括n个候选服务, si={wsi1, wsi2, …, wsin}.在服务组合过程中, 每个候选服务wsij是一个特定子任务的服务实体.
Web服务组合中QoS指标数量较多, 可以包括功能参数和非功能性参数, 且没有统一的计算标准.本文选取6种典型的Web服务指标[8], 主要包括:可用性a(服务可以被访问, 即可用的概率)、响应时间rt(发送服务请求到接收到服务结果所经历的时间), 吞吐量t(给定时间内调用总次数)、可靠性rel(服务请求被成功响应的概率)、声誉re(调用服务后用户的反馈率)、代价c(调用服务所必须支付的费用).则单个服务的属性集可以记为
|
在Web服务组合中, 组合模型有顺序模型、平行模型、条件模型和循环模型, 由于其他模型都可转化为顺序模型, 为了简化, 只考虑顺序模型[8].设组合服务QoS属性集记为Q(cs)={Qrt, Qa, Qt, Qrel, Qre, Qc}, 且由单个服务QoS值聚合而成, m表示抽象服务总数, n表示每个抽象服务中包含的候选服务总数, 则满足:
|
(1) |
根据不同的语义, 服务属性可被分为积极属性和消极属性，且不同QoS指标在量纲和数量级之间存在较大差异, 对上述指标进行分类和归一化.对于可用性a，吞吐量t，可靠性rel和声誉re这些积极属性, 数值越大质量越好，采用如下所示的归一化方式:
|
消极属性表现为数值越小质量越好, 比如代价c，响应时间rt, 归一化方式如下所示:
|
Ql是服务组合的聚合值, maxQl(minQl)是所有组合路径第l维的最大值(最小值).通过简单加权来计算最终质量评估值, 可以根据不同重要性分配权重, 然后计算权重与相应属性乘积之和.则其偏好函数fpre和代价函数fc分别为
|
则服务组合的质量演变成需要满足最大化fpre和最小化fc.借助多目标优化理论, 若目标存在相互冲突, 即无法得到所有目标函数同时达到理想状态下的最优解, 因此需要各个目标函数之间进行权衡, 即需要寻找Pareto最优解集[6].
2 基于改进的多目标人工蜂群算法 2.1 多目标人工蜂群算法的改进ABC算法是一种群智能优化算法, 算法通过在候选解上进行随机的, 且有目标的进化来寻找最优解[3].影响ABC算法性能的主要因素包括探索蜜源和开发蜜源两个过程.算法的探索能力表明在全局范围内搜索未知区域的能力, 即全局寻优能力; 开发能力则是个体在局部范围内搜索更优解的能力, 即局部求精的能力.因此, 要提高ABC算法解的质量, 就需要在探索能力和开发能力上协调和平衡.
优化问题、服务组合优化问题与人工蜂群算法中主要概念的对应关系如表 1所示.
|
表 1 概念对比 Table 1 Conceptual comparison |
基本ABC算法中, 由n维向量表示的蜜源位置是优化问题的可行解, 而蜜源质量则表示相关解的适应度值.将其应用于服务组合时, 一个可行的服务组合可以表示为蜂群算法的一个候选解, 候选解的每一个维度都必须是满足边界条件的整数.整数数组编码方案应用于编码解决方案[9], 编码采用整数数组编码方案表示.假设蜜源数为SN, 蜜源集合P={x1, x2, …, xSN}, 蜜源xd是一个m维数组, xd=[xd1, xd2, …, xdm], 其中m是抽象服务个数, 数组中每一个元素xdi是相应抽象服务Si对应下标为j的候选服务wsij, xdi是[LB, UB]之间的整数, 下边界(LB)是1, 上边界(UB)为n, 表示候选服务的个数.假设有抽象服务的数量为m, 每个抽象服务包含n个具体服务, 则编码方案共有nm种.
基本ABC中, 通过计算适应度函数值来对解的优劣进行评估, 而多目标优化中, 需要对适应度函数值的计算方法进行改进, 即需要采用Pareto支配概念计算多目标优化算法的适应度值, 如果Food1≻Food2, 则认为Food1优于Food2, 则该解在种群中的支配解数dom(i)加1, 该解的适应度值计算如式(2)所示:
|
(2) |
现实条件下, 如果组合中的单个服务出现问题或服务组合不可用, 则该服务组合将失效, 用户需要新的组合方案来替代.为了解决这一问题, 本文采用Pareto占优机制完成多目标问题.因此, 最终结果将是一组解决方案, 用户可以根据需求从最优解集中选择最优解完成服务组合.本文采用快速非支配排序法构造Pareto集.
为了使初始种群尽可能利用搜索空间的信息, 引入反向学习算子来初始化种群[10].具体步骤如下:
Step1 首先随机初始化SN个蜜源, 即
|
(3) |
Step2 为每个蜜源产生相对应的反向蜜源：
|
(4) |
Step3 从两类蜜源中选择适应度好的SN个解作为初始种群.
为保证效率, 受PSO进化算法思想的影响[11], 改进搜索方程, 引入精英档案学习思想, 精英档案学习策略如式(5)所示:
|
(5) |
其中, Rpop是从外部精英档案中随机选择一个精英解(Pareto解).
优化过程中获得的即时信息对后续的优化过程是有帮助的, 而传统ABC算法并没有有效地利用这些信息来提高搜索效率.受差分思想[12]的启发, 提出一个改进的搜索方程, 即在最优解附近产生新的候选位置以便提高算法的开发能力.提出一种组合变异策略, 即以一定的概率选择不同的搜索方程.组合变异策略所使用邻域搜索算子和差分变异算子分别如下所示:
|
(6) |
|
(7) |
在全局搜索过程中使用随机搜索的方式可以丰富蜜源的种类, 即可以保证组合服务的多样性, 但也会带来算法收敛速度慢、搜索效率不高的问题.为解决这一问题, 在改进的算法中引入全局最优解对搜索进行指导, 改进了侦察蜂策略，如下所示:
|
(8) |
本文给出一个改进的多目标人工蜂群算法(ImMOABC).
2.2 基于ImMOABC算法的Web服务组合优化算法改进的Web服务组合优化流程如下.
Step1 初始化阶段:设置参数SN(服务组合的数量=采蜜蜂数量=观察蜂数量), Limit(蜜源不被更新的最大迭代次数)，MCN(最大迭代次数).
完成种群初始化, 使用式(3)随机产生SN个解, 并根据式(4)计算该初始种群中每个解的反向解, 基于快速非支配排序方法对2×SN个解进行排序, 并计算每个解的拥挤距离, 选出较优的SN个解作为初始种群, 并将rank=1的解(即精英解/非劣解)存放到外部档案中, 完成初始化.
Step2 采蜜蜂阶段:根据式(5), 在外部档案的引导下进行邻域搜索, 通过Pareto支配原则判断新产生的邻域解和原有解之间的关系, 如果新解支配原有解, 则保存新解, trial置0;否则, 放弃新解, trial加1.
Step3 计算所有解相应的跟随概率:
|
Step4 观察蜂阶段:观察蜂通过轮盘赌方式选择一个解, 随机产生一个随机数r, 当r小于设定的参数cr时, 执行基本人工蜂群算子, 否则执行差分变异算子.计算新解目标函数值, 通过Pareto支配关系判断当前解与新解之间的关系, 如果新解支配原有解, 则保存新解, trial置0;否则, 放弃新解, trial加1.
Step5 侦察蜂阶段:舍弃达到Limit限定的解, 根据式(8)产生一个新解, 替代舍弃的解.
Step6 外部档案管理策略:将当前种群中的Pareto最优解加入到外部档案.采用拥挤度距离计算对外部档案进行裁剪, 以保证档案不会退化, 且保证了档案中个体的分布性.
Step7 满足最大迭代次数, 输出外部档案, 完成优化.
3 仿真实验与结果分析为了验证所提方法的有效性, 对上述算法分别在随机数据集和QWS数据集上进行验证.实验环境为Intel(R)Core(TM)i7-2600 CPU @ 3.40 GHz, 8 GB RAM, Windows10(64 bit), MATLAB2016b.
3.1 评估指标为了评价算法的有效性, 引入多目标优化评价指标对改进算法的性能进行评价.Pareto最优解的多样性用多样性指标Δ评价; 算法的收敛性用世代距离(GD)评价[12].
1) 多样性指标Δ反映的是非劣解能否均匀地分布在整个均衡面上, 即表示解在空间上的分布.Δ值越小，表明最优解的多样性越强.具体计算如下[5-6]:
|
式中:hi为相邻两点之间的距离; h为hi的均值; hf为算法所获取的边界值；hl为边界值与相应极端值间的距离; n为非劣解的个数.
2) 世代距离(GD)用来描述算法所获得的非劣解与Pareto最优解之间的距离.世代距离体现了算法的收敛性.计算公式如下[5-6]:
|
式中:disti表示第i个非劣解与真实Pareto最优解之间的最短距离; n为非劣解数量.
3) 执行时间.算法的执行时间(T)是一个反映算法性能的指标, T越小, 算法的性能越好.
真实Pareto-front(PF)也需要参与上述指标的计算, 但是对于服务组合问题而言, PF不能直接获取.应该按照如下方式计算PF, 步骤如下:
Step1 新种群由MOABC和ImMOABC两种算法获取的非支配集的并集产生;
Step2 对Step1得到的新种群进行快速非支配排序, 得到非支配解集, 即为PF.
3.2 Web服务组合优化结果分析1) 随机数据集验证.为了模拟大规模服务组合, 使用MATLAB随机产生100 000个仿真服务, 其属性评价值在区间[0, 1]的均匀分布下随机生成, 所有属性的权重设置为0.2.选取抽象服务数为10, 候选服务为10 000.则组合结果如图 1所示, 横轴代表组合服务的QoS(fpre), 纵轴代表代价函数(fc).
|
图 1 随机数据集的优化结果图 Fig.1 Optimal result of random datasets |
将10次运行得到的指标绘制成盒图, 如图 2所示, 其中点(·)代表10次运行结果的平均值.
|
图 2 随机数据集优化评估指标盒图 Fig.2 Box diagram of optimization evaluation of random datasets |
从优化结果图 1可看出, 在求解Web服务组合优化问题上, ImMOABC算法得出的非支配解数量多于MOABC, 其在一定程度上表现了解的多样性, 从非支配解的分布趋势看, ImMOABC算法在解的均匀性上也有一定的优越性.进一步结合表 2所示的多样性和世代距离这两个指标, 验证了改进后算法求解的多样性和均匀性.结合图 2可以看出, 在求解组合优化问题时, 改进后的算法的多样性、世代距离的平均值和标准差明显小于基本多目标蜂群算法, 即表明了在收敛性和多样性上都有较大的改进.在运行时间上稍有增加, 主要原因为算法初始化时, 使用了反向学习策略, 类似作了两次初始化.
|
|
表 2 随机数据集优化性能评估指标汇总表 Table 2 Explanatory views of performance evaluation index of random datasets |
2) QWS数据集验证.QWS数据集是Guelph大学的Eyhab Al-Masri使用Web Service Crawler Engine(WSCE)从互联网收集的Web Service数据集, 并对服务的QoS属性进行了度量.
该数据集包括了2 507个Web服务的信息, 每个Web服务都有9个质量参数:响应时间、可用性、吞吐量、成功率、可靠性、遵从性、最佳实践、时延和文档[13].在验证中, 由于该数据集的Web服务质量属性与第1节中的并不一致, 本文作了调整:(a)代价函数fc, 最小化响应时间和时延, 其权重都设为0.5;(b)对于偏好函数fpre, 最大化QoS, 其中可用性、成功率和可靠性的权重设为0.2;(c)其他属性权重设置为0.1.设抽象服务数为10, 候选服务为250, 实验结果如图 3所示, 横轴代表组合服务的QoS(fpre), 纵轴代表代价函数(fc).
|
图 3 QWS数据集上的优化结果图 Fig.3 Optimal result of QWS datasets |
将10次运行得到的指标, 绘制成盒图, 如图 4所示, 图中点(·)代表10次运行结果的平均值.
|
图 4 QWS数据集优化评估指标盒图 Fig.4 Box diagram of optimization evaluation of QWS datasets |
在QWS数据集上模拟服务组合, 对提出的算法进行验证, 从优化结果分布图 3可看出, 在求解Web服务组合优化问题上, ImMOABC算法得出的非支配解数量多于MOABC, 其在一定程度上表现了解的多样性, 从非支配解的分布趋势看, ImMOABC算法在解的均匀性上也有一定的优越性.进一步结合表 3和图 4所示的多样性和世代距离这两个指标, 验证了改进后算法求解的多样性和均匀性.
|
|
表 3 性能评估指标汇总表 Table 3 Explanatory views of performance evaluation index of QWS datasets |
上述结果证明, 基于ImMOABC算法中的精英引导策略使可行解在局部搜索过程中更有方向性, 使得优化结果向精英解靠近, 加速了算法的收敛.另外, 改进算法所使用的搜索机制在局部搜索和全局搜索取得一定的平衡, 因此在求解质量上更有优势.
4 结论Web服务的组合优化问题是当前研究的热点问题之一, 本文在已有的多目标人工蜂群的基础上进行改进, 引入反向学习算子、精英引导策略和组合变异策略等操作, 有效解决了Web服务组合当中优化组合问题, 在保证组合多样性的前提下, 提高了搜索效率.结果表明, 基于改进的多目标人工蜂群优化的Web服务组合方法, 提高了寻优精度、解的质量以及算法的收敛性.
| [1] |
倪晚成, 刘连臣, 吴澄.
Web服务组合方法综述[J]. 计算机工程, 2008, 34(4): 78–81.
( Ni Wan-cheng, Liu Lian-chen, Wu Cheng. Survey on Web services composition methods[J]. Computer Engineering, 2008, 34(4): 78–81. ) |
| [2] |
Jaeger M C, Muhl G, Golze S.QoS-aware composition of Web services: a look at selection algorithms[C]// Proceedings of International Conference of Web Services.Orlando, 2005: 646-661.
|
| [3] |
Karaboga D.An idea based on honey bee swarm for numerical optimization[R]. Technical Report-TR06. Kayseri: Erciyes University, 2005.
|
| [4] |
周清雷, 陈明昭, 张兵.
多目标人工蜂群算法在服务组合优化中的应用[J]. 计算机应用研究, 2012, 29(10): 3625–3628.
( Zhou Qing-lei, Chen Ming-zhao, Zhang Bing. Multi-objective artificial bee colony algorithm applied in QoS-aware service composition optimization[J]. Application Research of Computers, 2012, 29(10): 3625–3628. DOI:10.3969/j.issn.1001-3695.2012.10.006 ) |
| [5] |
Wang L, Zhou G, Xu Y, et al.
An enhanced Pareto-based artificial bee colony algorithm for the multi-objective flexible job-shop scheduling[J]. International Journal of Advanced Manufacturing Technology, 2012, 60: 1111–1123.
DOI:10.1007/s00170-011-3665-z |
| [6] |
Li J Q, Pan Q K, Gao K Z.
Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology, 2011, 55: 1159–1169.
DOI:10.1007/s00170-010-3140-2 |
| [7] |
Ardagna D, Pernici B.
Adaptive service composition in flexible processes[M]. London: IEEE Press, 2007.
|
| [8] |
Cardoso J, Sheth A, Miller J, et al.
Quality of service for workflows and Web service processes[J]. Journal of Web Semantics, 2004, 1(3): 281–308.
DOI:10.1016/j.websem.2004.03.001 |
| [9] |
Huo Y, Zhuang Y, Gu J J, et al.
Discrete Gbest-guided artificial bee colony algorithm for cloud service composition[J]. Applied Intelligence, 2015, 42(4): 661–678.
DOI:10.1007/s10489-014-0617-y |
| [10] |
Zhu G, Kwong S.
Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics & Computation, 2010, 217(7): 3166–3173.
|
| [11] |
Yi W, Gao L, Zhou Y, et al.Differential evolution algorithm with variable neighborhood search for hybrid flow shop scheduling problem[C]//International Conference on Computer Supported Cooperative Work in Design.Chengdu, 2016: 233-238.
|
| [12] |
Storn R, Price K.
Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4): 341–359.
DOI:10.1023/A:1008202821328 |
| [13] |
Al-Masri E, Mahmoud Q H.QoS-based discovery and ranking of web services[C]//International Conference on Computer Communications and Networks.Honolulu, 2007: 529-534.
|