基于改良蜂群算法的Web服务组合优化方法

张志鹏,周井泉

(南京邮电大学 电子与光学工程学院、柔性电子(未来技术)学院,江苏 南京 210003)

0 引 言

时代飞速发展,Web服务已经成为软件行业的新技术融合点。由于用户的需求日益复杂,通过单一的Web服务几乎不可能满足用户的需求。因此,要以适当的顺序组成一组基本服务,以满足用户的要求。组合现有Web服务以创建新Web服务的过程称为Web服务组合[1],但Web服务组合往往是多种多样的,这就需要考虑如何处理此类复杂Web服务组合。

为了为用户的任务设计复合Web服务(Composite Web Service,CWS),首先将任务划分为n个子任务。然后,从有m个候选服务的候选池挑选一个基本的Web服务根据其功能属性映射到一个子任务中。最后,将映射的Web服务集成到组合Web服务中,子任务的执行顺序与服务组合顺序相同。Web服务候选池中存在许多具有相同功能属性的基本服务,从候选Web服务集中选择最优CWS称为Web服务选择。

每个Web服务都有一个核心功能,称为该Web服务的功能属性。除了功能属性外,每个Web服务还拥有一些非功能属性,这些属性也被称为QoS属性。最优选择定义为：既能满足用户的功能性需求,又能满足QoS属性的CWS称为最优选择。因此,如何挑选出最优选择是解决Web服务组合问题的重点。

对于此类最优选择问题,没有哪种特定的元启发式算法一定是最好的。因此,新的算法在Web服务选择领域一直广受欢迎。Wang Hei-Chia等人结合用户对Web服务的主观评价数据和服务本身的客观数据,通过模糊专家系统建立服务的QoS评测模型。随后基于评测后的QoS属性值,利用遗传算法(Genetic Algorithm,GA)进行服务组合方案的求解[2]。范小琴等人根据自然界中的物种协同进化的思想,提出了一种协同进化的元启发算法来求解全局Web服务选择问题[3]。Klein和Adrian等人利用遗传算法来解决包含多个子任务的Web服务选择问题。赵欣超等人利用粒子群优化算法对人工免疫算法进行改良,把其应用到全局Web服务选择中[4]。黄碧晴等人利用混沌的思想提出了一个新的元启发算法来解决Web服务组合问题,并取得了比传统遗传算法更好的结果。Huo,Yin等人利用单维度小扰动的思想改进了人工蜂群算法(Artificial Bee Colony,ABC)并应用于Web服务选择中[5]。

可见,QoS评价模型和群体智能算法经常被用于处理Web服务组合问题。QoS模型能使处理结果更加符合客户非功能需求,而群体智能算法中的蜂群算法具有设置参数少、实现简单、工程适用性强等优点,近年来一直被用于处理Web服务组合问题。但上述研究对于种群初始化、求解策略未做过多改进,并且算法适应度、稳定性有待进一步提高,于是该文在这两个方面展开进一步研究。

为提高算法的适应度和稳定性,该文提出了一种新的改良人工蜂群算法用于Web服务的选择。它使用基于混沌的初始化技术将初始解分散在搜索空间,采用改良的蜜源搜索方程对搜索空间进行优化,并改良了围观蜂相位的搜索方程,获得了良好的性能。

1 Web服务组合与QoS评价模型

1.1 Web服务组合的概念

Web Services Architecture组织给Web服务组合的定义是：一个支持网络节点交互的应用程序,每个Web服务都存在明确的、机器可识别的通用标准描述来说明节点如何以特定的方式彼此交互。

Web服务是一种可以构建分布式系统的新的网络开发技术。它同时兼备低耦合性、可复用性,独立于编程语言和操作平台性。Web服务还有三大协议：SOAP(Simple Object Access Protocol),WSDL(Web Services Description Language),UDDI(Universal Description Discovery and Integration)。SOAP是一种轻量级的交换数据的规范,指可以在分布式系统中交换标准化的信息;WSDL用于描述一个Web服务及如何与Web服务通信;UDDI是服务提供者和用户之间的一个链接,使用户更加容易搜索和找到目标服务[6]。

1.2 Web服务组合的形式

Web服务组合是通过调用相互连接的其他服务来构造的。服务的组合允许不同应用程序之间在Internet上进行协作、协调和合作。并且服务组合可用于构建一些智能化定制的应用程序,以交付给用户新的服务和功能。在日常使用越来越多的复杂系统中,已经出现了这种便于用户实现其需求的组合技术系统。

Web服务组合通常经历很多步骤,图1展示了Web服务组合的一般生命周期,主要分为4个步骤：

图1 Web服务组合生命周期

第一步：定义。用户提出其个人服务需求,先根据其需求提取关键信息,并对其进行拆解,分成多个子步骤去完成,每个子步骤按一定的拓扑相连接组合,定义为一个新的抽象流程。

第二步：服务选择。不同的供应者向注册服务中心提供各种候选Web服务以形成候选Web服务集合。这时根据第一步得到的抽象流程,向每一个子步骤中挑选多个符合其要求的Web服务。

第三步：服务调度。对第二步得到的服务组合中每一个子步骤进行排列组合,每一种不同的排列方法都会生成一个新的服务组合,经过筛选比对后从中挑选出最优的Web服务组合。

第四步：服务执行。面向客户执行满足其服务需求的最优Web服务组合。

当知道其任务具体分解形式时,便可以采用上述方法向用户提供最优的Web服务,当不知道任务具体需求时,即非功能需求,便可通过QoS模型进行处理。

1.3 Web服务组合的QoS评价模型

QoS属性是Web服务里非常重要的综合指标,可以将用户对某项服务非功能属性的满意度用数值表示,是客户的非功能需求的直观体现。常用的QoS属性包括可用性、可靠性、响应时间、延迟,它们的具体定义为：

(1)可用性：成功调用的数量与总调用数量的比率。

(2)可靠性：正确消息与总消息的比率。

(3)响应时间：发送请求到接收响应之间的时间跨度。

(4)延迟：执行请求所花费的时间。

可靠性与可用性属于积极的QoS属性,越高越好。响应时间与延迟属于消极的QoS属性,越低越好。

QoS评价模型将CWS的聚合QoS值映射为实数,即效用值,以便后续计算使用,需要执行以下两个步骤：

(1)归一化：将不同Web服务的QoS属性值归一化为0到1之间的实数。

(2)加权：将每个归一化的QoS值与相应的权重相乘并相加,得到该CWS的效用值。

CWS各个QoS属性归一化处理如下：

如果qk为积极属性,则qk的归一化处理结果如式1所示。

(1)

如果qk为消极属性,则qk的归一化处理结果如式2所示。

(2)

服务组合执行有4种基本结构：顺序、并行、选择和循环,本次采用顺序结构。顺序结构下CWS的第k个QoS属性的聚合值如式3所示。

(3)

利用上述QoS属性归一化处理和QoS聚合值计算公式,将寻找满足全局约束的最优CWS的问题表述为：

最大化

(4)

约束,

2 基于改良蜂群算法的QoS-Web组合优化

近年来,多种智能算法用于处理Web组合优化问题,其中蜂群算法在解决问题过程中具有设置参数少、实现简单、工程适用性强等优点,近年来一直是热门算法。针对蜂群算法中的群体初始化、相位搜索方程、围观搜索策略进行改良,该文提出一种改良的蜂群算法(modified Artificial Bee Colony,mABC)来解决Web组合优化问题。

2.1 改良蜂群算法

ABC(Artificial Bee Colony)算法由Karaboga和Basturk提出,是一种基于蜂群的元启发式算法,基于蜜蜂的觅食行为。一群蜜蜂一起生活在一个蜂箱被称为蜂群。蜂群由三种不同类型的蜜蜂组成：(i)雇佣蜂;(ii)围观蜂;(iii)侦察蜂。不同的蜂种执行各自的任务,蜂群的觅食任务是由雇佣蜂发起的。每只雇佣蜂都瞄准食物来源的位置,并收集有关该食物来源中可用花蜜量的信息。之后,它们与巢友分享关于花蜜量的信息。在收集了食物来源的信息后,围观蜂会选择更好的食物来源。当一只雇佣蜂发现食物来源被遗弃时,会恢复它作为侦察蜂的角色。这样,开发的责任由雇佣蜂和围观蜂共同承担,而探索的责任则由侦查蜜蜂独自承担[7]。

对传统蜂群算法的初始化策略、雇佣蜂和围观蜂的方程进行修改。

(1)初始化策略。

为了选择更好的初始种群,提出了一种基于混沌映射的对立学习方法,如式5所示。

chk+1=μ×chk(1-chk)

(5)

其中,chk为0到1之间的随机数,μ设置为4。

基于对立学习(Opposition Based Learning,OBL),同时考虑估计解X及其对应的相反估计值,以覆盖整个搜索空间。每个解的相反估计值的计算方法如式6所示。

(6)

蜂群算法的种群初始化中有两个循环：第一个循环中,使用基于混沌映射原理的式5来进一步生成估计解X。第二个循环中,使用基于OBL原理的式6得到另一个解的集合Xo,对所有解进行求值,形成组合集,利用精英主义原理得到更好的初始化种群。

(2)雇佣蜂方程。

被雇佣的蜜蜂首先寻找新的潜在候选解,为了充分挖掘每一种可能,需要对各个维度信息进行交换,提出一个新的相位搜索方程,见式7。

Vi=φijXi+(1-φij)Xk

(7)

其中,i,k∈(1,SN),k≠i,φij～U(-1,1)为-1和1之间的随机分布数。

(3)围观蜂方程。

围观蜜蜂的功能很大程度上取决于雇佣蜜蜂,因为它们需要从雇佣蜂那里得到有用信息再进行下一步判断处理。为了提高搜索强度,对传统ABC算法中围观蜂的搜索方程进行了改良。在文献[8-9]的研究中都可以明显看出,涉及最优解并探索其周围的搜索空间可以提高开发性能。新的围观搜索方程如式8。

xij=xij+φij(xbest,j-xr1,j)+(1-φij)(xr2,j-xr3,j)

(8)

其中,r1,r2,r3是互斥随机数,且i,r1,r2,r3∈(1,SN),r1≠r2≠r3,j∈(1,D)是随机选择的指标。类似地,xbest是当前种群中具有最佳适应度的最佳解向量。

2.2 QoS-Web组合优化

由QoS的Web服务组合模型得到的QoS效用函数U如式4所示,作为适应度值。

改良蜂群算法应用于Web服务组合问题的具体步骤描述如下：

步骤1：参数设置阶段,种群大小为m,维数为n,限制为mn/2,最大迭代次数为Max。

步骤3：雇佣蜂阶段,雇佣蜂根据邻域搜索方程(式7)产生新解,计算其适应度值,并进行贪婪选择。

步骤4：围观蜂阶段,围观蜂进行轮盘选择,从雇佣蜂产生的解中选择一个更合适的解,解决方案的质量取决于适应度值,在评估适应度后,围观蜂更新解决方案的位置,即围观搜索策略(式8)。

步骤5：侦察蜂阶段,如果搜索了预定义的实验次数即限制次数后,某个解决方案的位置没有更新,则该解决方案将被放弃,与该解决方案相关的雇佣蜂将变为侦察蜂。侦察蜂将会生成新的解决方案。

步骤6：记录目前获得的最优解。

步骤7：若当前没有达到迭代次数则回到步骤3,否则输出最优解。

通过U的值来判断得出解的质量,即顾客对于Web服务组合的满意度,U越高表示结果越符合客户需求,U越低表示结果不满足客户需求,U的值越高越好。

3 实验结果与讨论

此次实验采用Web服务的QWS数据集[10]。该数据集包含2 507行和9列。一行代表一个基本的Web服务,一列代表一个QoS属性。因此此次实验使用2 500行,4列,即Web服务数量为2 500,QoS属性数量为4。

为了分析算法性能,将mABC与5种现有的元启发式算法(人工蜂群算法[11](ABC)、差分进化算法[12](DE)、改良灰狼算法[13](MGWO)、最优导向人工蜂群算法[14](GABC)和改进人工蜂群算法[15](IABC))进行了比较。

QoS的4个属性是：响应时间(ms)、延迟(ms)、可用性(%)和可靠性(%)。所有的实验都是在64位3.40 GHz Intel(R)酷睿(TM) i7-3770 PC上的窗口环境中实现的,具有8 GB RAM。在实验中对mABC进行了以下参数设置。在引言中提到的n个子任务和每个子任务中的m个候选Web服务,对应算法中的维数(n)和种群大小(m),分别设置为10和250,限制设置为(mn/2)。所有算法的停止条件是最大迭代次数(Max),设置为500,所有算法迭代次数为Max=500。

图2显示了mABC算法与其它算法的适应度比较。可以看出,当迭代次数达到25次时,mABC算法适应度为5.69,开始始终优于其他算法。当迭代次数达到50次时,适应度为5.72,已经高于当他算法的最优值。迭代次数100时,其余算法适应度趋于稳定不再增加,而改良蜂群算法仍在逐步提升直至200次时达到最优值5.8,其余算法在迭代50到75次之间逐渐趋于稳定,但探索的不够充分,无法达到更高的适应度,而mABC算法虽然收敛的慢,但仍在探索解,并在不断提高最大适应度。在整个迭代过程中可以看出,从第25次迭代开始mABC的适应度都比其余算法的高。并且mABC算法能在保证收敛的情况下取得更高的适应度,更适合解决Web服务组合问题,与理论上的预期相同。

图2 随迭代次数变化的适应度

为对比不同算法适应度标准差的情况,分析了数据的最大值、最小值、中间值、平均值,如表1所示,其中mABC算法适应度的最大值5.8、最小值5.69、中间值5.78、平均值5.76,与其余几种算法的数据对比可见mABC算法的最大值、最小值、中间值、平均值都比其他几种算法的优。并且mABC算法相较原始ABC算法在适应度最大值提升了11.9%,适应度平均值提升了12.5%。

表1 适应度4种数据

标准差是衡量一个数据稳定状况的值,标准差越低表示该数据越稳定,越高则表示越不稳定。通过表1数据计算几种算法适应度的标准差,如图3所示,mABC的标准差为0.043,明显低于其余几种算法,说明mABC算法相较于其余几种算法具有较好的稳定性,更适合解决Web服务组合问题,与理论上的预期相同。

图3 算法的适应度标准差

执行时间指的是算法完成一次实验需要的时间,通过将实验运行100次记录算法的平均时间使结果更加可靠。图4为6种算法执行时间统计图,其中mABC的执行时间为1.81 s,高于其余几种算法,这是由于在算法的种群初始化阶段加入了混沌映射,同时这也使得算法更加复杂,执行时间增加,但增加了算法的探索性。从图2中也可以看出,mABC的最大适应度在其余算法都已经收敛时仍在增加,说明初始化策略的改动使得算法牺牲一定的执行时间去换取更大的适应度[16-19]。

图4 算法执行时间

4 结束语

文中给出了Web服务组合的QoS数学模型,通过使用基于混沌的对立学习方法生成初始种群提高传统ABC算法的开发能力,再修改雇佣蜂和围观蜂的搜索方程,改良了ABC算法并用来解决Web服务组合优化问题。实验数据表明,mABC算法在执行时间方面比其余算法略微都要长一些,但在适应度、稳定性方面有较好表现,优于其余参照算法,在处理Web服务组合问题上具有可行性和有效性。

该文的研究空间还很大,在后续的工作中,笔者将会对ABC算法的寻优过程进行进一步优化并投入到Web服务组合优化研究。