基于参数自适应差分进化算法的Web服务组合

李 强，周井泉，张严凯

(南京邮电大学 电子科学与工程学院，江苏 南京 210003)

0 引 言

近年来，随着Web服务相关标准的持续完善，越来越多的Web服务在网上共享，然而单个Web服务功能有限，很难满足实际需求，因此需要将共享的Web服务组合起来，增强Web服务的能力。因此，关于Web服务组合的研究被提出，并吸引了工商界和学术界的广泛关注[1]。

目前评价服务质量多采用QoS(quality of service)，但QoS只能从性能层面反映Web服务的质量，不能反映用户的满意程度。为了更加精确地反映用户对Web服务的满意程度，体验质量(quality of experience，QoE)便应运而生。目前解决Web服务组合问题的主流算法为智能优化算法[2-3]，文中应用的是参数自适应DE算法。DE算法具有高可靠性、强鲁棒性以及良好的优化性能，但同时也有早熟收敛和搜索停滞等缺点，于是在标准DE算法的基础上，引入混沌初始化[4-5]和参数自适应机制，不仅避免了DE算法本身的缺点，还能提高其性能和稳定性。

1 问题描述

1.1 Web服务组合

一般情况下，Web服务框架由Web服务提供者、中介和Web服务需求者三部分构成，其中Web服务需求者把自己的需求信息发送给中介，中介会根据Web服务需求者的需求从Web服务提供者提供的服务中选择一个最优的发送给需求者，Web服务提供者主要的任务是提供各种Web服务。

1.2 基于QoE的Web服务组合模型

QoE的Web服务组合模型框架如图1所示。文中选取响应时间、可用性、可靠性三个参数作为QoS的评价指标，并在Web服务组合模型中引入模糊理论与专家系统，通过隶属函数和推理规则确定QoE的值(见表1和表2)。一般情况下，模糊集可分为三角形模糊集和梯形模糊集，文中选取梯形模糊集。

图1 QoE评估系统

指标低中高响应时间TT≤0.20.2≤T≤0.6T>0.6可靠性RR≤0.250.25≤R≤0.8R>0.8可用性AA≤0.30.30.8

表2 满意程度

注：0表示非常不满意，1表示不满意，2表示较差，3表示一般，4表示良好，5表示满意，6表示非常满意。

文中选取的是串联Web服务模型，如图2所示。适应度函数如式(1)所示：

(1)

图2 串联的Web服务实例

2 算法描述

2.1 标准差分进化算法

差分进化算法(DE算法)是在解的可行域范围内产生一个随机种群，然后对该随机种群进行变异、交叉、选择操作，产生新一代种群[6]。DE算法基于实数编码，它首先在所要解决问题的可行解空间生成随机种群：xi=(xi,1,xi,2,…,xi,D),i=1,2,…,NP。其中,D为问题维数;NP为种群规模。

2.1.1 差分变异

在DE算法中，变异操作是把种群中的个体进行差分操作，把得到的差分向量乘以缩放因子后再加上种群中另一个体得到一个新的变异个体。根据不同的变异操作形成了不同的变异策略。其中一种最常见的变异策略DE/rand/1的方程为：

vi,g=xr1,g+F·(xr2,g-xr3,g)

(2)

其中,r1≠r2≠r3≠i;F为缩放因子。

2.1.2 交 叉

交叉操作生成实验向量，DE算法有两种交叉方式，即二项式交叉和指数交叉(文中只介绍二项式交叉)。二项式交叉操作的方程为：

(3)

其中，j=1,2,…,D;jrand为[1,D]随机产生的整数；CR∈(0,1)为交叉率。

2.1.3 选 择

DE算法是利用“贪婪”策略[7]，根据适应值函数f(·)在目标向量xi,g和试验向量ui,g中进行筛选，选择优秀个体，淘汰劣质个体。对于最小化问题，选择操作的方程为：

(4)

其中，xi,g+1为下一代目标向量。

DE算法经过差分变异、交叉、选择操作产生下一代种群，如此完成种群的进化，最终找到最优个体。

标准差分进化算法的基本步骤如下：

Step1:初始化种群参数，包括种群规模NP，缩放因子F，变异因子CR，进化代数t=0；

Step3：个体评价。计算每个个体的适应度值；

2.2 DE算法的改进

DE算法具有高可靠性、强鲁棒性以及良好的优化性能，因此成为进化计算领域的热点课题，但DE算法也存在早熟收敛和搜索停止的问题，除此之外DE算法还有以下缺点：标准DE算法的搜索性能对参数具有一定的依赖性[8]；算法在有限的情况下很难保证获得全局最优解，搜索能力需要进一步提高[9]。

为了克服上述DE算法的缺点，提出混沌初始化和参数自适应机制对标准DE算法进行改进。

2.2.1 混沌模型

由于混沌具有随机性、遍历行和规律性等特点[10]，利用混沌遍历性的特点有助于避免智能算法在搜索过程中陷入局部最优[11]。典型的混沌模型有Logistic混沌模型、Tent混沌模型，文中使用Logistic混沌模型。Logistic模型递推方程如下：

xn+1=λ(1-xn)xn

(5)

其中，0≤xn≤1,n=0,1,2…；λ在0～4中取值，当λ=4时，式(5)所表示的系统处于混沌状态。

式(5)中λx代表种群数的平均增长率，而-λx2体现环境资源对种群繁衍的制约作用。通过设定初始值x0并研究数值序列x1,x2,…,xn,…的变化规律，就能得到种群繁衍的规律。

2.2.2 参数自适应DE算法

由于DE算法的控制参数对整个算法的性能影响较大，所以对于控制参数值的选取至关重要[12]。文中提出一种自适应机制动态选取F和CR的值[13]。初始种群的缩放因子F和交叉率CR是随机数产生的，范围是0～1。子代种群中的F和CR通过下式得到。

(6)

(7)

利用式(6)、式(7)可以让每个子代种群中每个个体拥有各自的缩放因子F和交叉率CR，这样便可完成参数的自适应。

参数自适应DE算法的步骤如下：

Step1：初始化种群参数；

Step2：利用Logistic模型产生初始种群；

Step3：计算每个个体的适应度值；

Step4：对种群进行变异操作；

Step5:对种群进行交叉操作；

Step6：进行选择操作，选出下一代种群个体；

Step7：根据式(6)、(7)计算出下一代种群个体的缩放因子F和交叉率CR；

Step8：对算法进行终止检验，如果达到最大进化代数或满足误差要求，则停止进化并输出最优个体，否则转Step3。

3 实验分析

为了验证参数自适应DE算法的性能，选取了串联Web服务模型，如图2所示，其中设定m=10、n=10。参数设置：初始种群的缩放因子F和交叉率CR分别由Rand(0.1,1.0)和Rand(0.0,1.0)产生，种群规模NP=200，算法最大迭代次数G=100，实验次数为200。鉴于目前没有统一的实验平台和相关数据集，QoS的属性值均由随机函数产生，取值范围为0～1。表3中显示的数据是经过200次实验后所取的平均值。算法比较结果如图3所示。

表3 算法的对比结果

图3 算法平均适应度值

从图3和表3中可以看出，自适应DE算法的平均值、最劣解、最优解都大于其他算法，方差和运行时间较小，具有较好的收敛速度和稳定性。因此参数自适应DE算法具有良好的性能。

4 结束语

建立了QoE的模糊专家系统的评估模型，并将其转化为Web服务组合优化问题。在标准DE算法的基础上，引入混沌初始化和参数自适应机制对其进行改进，并应用于Web服务组合优化问题[14]。实验结果表明，改进DE算法具有很好的稳定性和可靠性。然而，由于QoE的Web服务模型还不够成熟，有待进一步研究。同时，DE算法中各种参数的具体取值并不能给出统一的标准，仍然需要研究，这也是以后研究的重点。

[1] 夏亚梅，程 渤，陈俊亮，等.基于改进蚁群算法的服务组合优化[J].计算机学报,2012,35(2):270-281.

[2] 梁艳春，吴春国，时小虎，等.智能优化算法理论及应用[M].北京：科学出版社，2009.

[3] 汪定伟.智能优化方法[M].北京：高等教育出版社，2007.

[4] LU Y,ZHOU J,QIN H,et al.Chaotic differential evolution methods for dynamic economic dispatch with valve-point effects[J].Engineering Applications of Artificial Intelligence,2011,24(2):378-387.

[5] GU P,XIU C,CHENG Y,et al.Adaptive ant colony optimization algorithm[C]//International conference on mechatronics and control.[s.l.]:IEEE,2014:95-98.

[6] 王 凌，钱 斌.混合差分进化与调度算法[M].北京：清华大学出版社，2012.

[7] 何 兵，车林仙，刘初升.一种蛙跳和差分进化混合算法[J].计算机工程与应用,2011,47(18):4-8.

[8] WEBER M,NERI F,TIRRONEN V.A study on scale factor in distributed differential evolution[J].Information Sciences,2011,181(12):2488-2511.

[9] NEKOVEE M.Epidemic algorithms for reliable and efficient information dissemination in vehicular[J].Intelligent Transport Systems,2009,3(2):104-110.

[10] ZHANG C,CHEN J,XIN B.Distributed memetic differential evolution with the synergy of Lamarckian and baldwinian learning[J].Applied Soft Computing,2013,13(5):2947-2959.

[11] MCGINLEY B,MAHER J,O’RIORDAN C,et al.Maintaining healthy population diversity using adaptive crossover,mutation and selection[J].IEEE Transactions on Evolutionary Computation,2011,15(5):692-714.

[12] CAPONIO A,NERI F,TIRRONERN V.Super-fit control adaption in memetic differential evolution frameworks[J].Soft Computing,2009,13(8):811-831.

[13] KAELO P,ALI M M.Differential evolution algorithms using hybrid mutation[J].Computational Optimization and Applications,2007,37(2):231-246.

[14] 刘荣辉.多阶段自适应差分进化算法及应用研究[D].上海：东华大学，2012.