混沌蚁群算法的Web服务组合优化研究

承 松，周井泉，常瑞云

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

混沌蚁群算法的Web服务组合优化研究

承 松，周井泉，常瑞云

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

为保证Web服务组合满足用户对Web服务质量日益增长的需求，提出了基于体验质量(Quality of Experience，QoE)的Web服务组合优化方法，即建立模糊专家系统(Fuzzy Expert System)QoE评估模型，并转化为Web服务组合优化的数学模型，采用混沌蚁群算法(Chaos Ant Colony Optimization，CACO)进行Web服务组合优化求解。该方法利用混沌算法的遍历性、随机性和规律性，通过引入混沌扰动来避免优化过程中出现局部最优解，以期获得服务组合的全局最优解。为验证CACO算法的可行性和有效性，对其与人工蜂群算法(ABC)、粒子群算法(PSO)和原始蚁群算法(ACO)等进行了同步对比实验。实验结果表明，CACO算法相比其他算法具有运行时间短、收敛速度快且稳定性高的优点，具有较好的发展前景。

Web服务组合；模糊专家系统；用户体验质量；混沌蚁群算法

0 引 言

随着互联网的快速发展，工商业领域到处都充满着Web服务。因此，产生了许多功能相同的Web服务。此外，单个Web服务不能完全解决用户提出的各方面请求。因此，把互联网中各个功能单一的Web服务按照某种有效的方式组合起来，从而提高效率[1]。

目前广泛采用的服务度量标准为QoS(Quality of Service)，QoS评价指标主要包括信誉度、可用性、成本费用、响应时间等。但这仅仅反映了服务技术方面的特性，忽略了用户的主观方面，所以不能够反映用户对服务的满意程度。体验质量(Quality of Experience，QoE)是凭借用户满意程度作为评价标准的。它结合了网络性能、业务质量、主观评测等影响因素，直接反映了用户对服务舒适度的满意程度。文献[2]对于QoS不能满足服务体验质量的满意程度，建立了评估QoE的模糊粗糙混合的专家系统模型。文献[3]运用模糊专家系统解决了在视频交通中的QoE评估。

Web服务组合实质为NP难问题，目前主流算法是智能优化算法。文献[4]提出了基于PSO的优化算法，主要是为了解决Web服务组合问题在QoS方面的服务选择问题。文献[5]提出了一种具有反射迁移的并行自适应混沌优化的并行算法，解决了云制造资源分配的问题。

综上所述，智能优化算法在解决Web服务组合方面是非常有价值的研究方向。文中建立了Web服务的QoE评价模型，提出了CACO算法。对比实验结果表明，CACO算法由于加入了混沌初始化、择优策略和混沌扰动，展现出比原始ACO、ABC、PSO等算法更好的收敛性、稳定性和运算效率。

1 问题描述

1.1 Web服务组合相关技术

Web服务供应者、需求者和中介者是Web服务技术架构里的三个主要角色，通过注册、调用、绑定来调用互联网中的Web服务[6]。服务需求者会将他们的需求信息反馈给服务中介者，服务中介者根据需求者的需求信息选择一个最优的服务发送给供应者，服务中介者又从服务供应者那里获取服务。

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

QoE的计算过程为将QoS参数通过模糊专家系统计算出QoE的值。与以往通过简单的等式将QoE与QoS属性串联起来的客观评价方法不同，文中融入了模糊理论与专家系统，选取了响应时间(T)、可用性

(A)及成本(C)这些与Web服务QoE相关联的QoS参数作为QoE的评价指标。模糊集可以用不同的形状来表示，一般情况下三角形、四边形就足以表达专家知识，而且还能简化计算过程。文中创建了响应时间、可用性和成本的模糊集。根据图1的模糊集与表1、表2的决策表来计算精确的QoE值。

图1 响应时间、可用性和成本的模糊集

指标低中高响应时间(T)T≤1．51．53．5可用性(A)A≤224成本(C)C≤224

表2 满意程度表

注：表中用数字来表示满意程度，0表示非常不满意，1表示不满意，2表示较差，3表示一般，4表示良好，5表示满意，6表示非常满意。

适应度函数如式(1)所示：

(1)

式(1)表示蚁群算法中蚂蚁走过路线上QoE信息的总和，其值越大，表明所求的解越优。

2 算法描述

2.1 原始蚁群算法

原始蚁群算法[7-8]是通过运用人工蚂蚁所行走的路线来表示求出的最优解的一种方法。蚂蚁通过走过的路线上留下的信息素寻找到最优的路线。在路线上所留的信息素越多，表明这条路线越优。

文中选用串联的模型，如图2所示。其中，WSCSm为第m个服务候选集；CSn为某个服务候选集中的第n个服务。

图2 串联的Web服务实例

(2)

其中，allowedk表示在t时刻第k只蚂蚁接下来可以选择的服务；α表示信息启发式因子；β表示期望启发式因子；ηij(t)表示由i移动到j的期望程度，取值如下：

ηij(t)=value(QoE)

(3)

为防止剩余在路线上信息素过多而完全掩盖了启发信息，在M只蚂蚁从start走到end后，更新路线上剩余的信息素。t+n时刻在路线(i,j)上信息量可按照式(4)和式(5)进行更新。

τij(t+n)=(1-ρ)·τij(t)+Δτij(t)

(4)

(5)

根据信息素更新策略的不同，文中选择蚁周模型，如式(6)所示。利用全局信息，当执行完一次后才更新所有线路上的信息素。

(6)

原始蚁群算法的实现步骤如下：

Step1：初始化参数。

Step2：将M只蚂蚁放于起始(start)位置，令k=0，k为第k只蚂蚁。

Step3：迭代次数增加一次，Nc=Nc+1。

Step4：蚂蚁数量加1，k=k+1。

Step5：根据转移概率，运用轮盘选择的方式选择接下来的服务，直至寻找到终点。

Step6：如果蚂蚁的数量大于M，则进入Step7；否则进入Step4。

Step7：根据式(4)更新每条线路上的信息素。

Step8：如果大于最大的迭代次数，则输出最优结果，结束程序；否则进入Step3。

2.2 混沌模型

典型的混沌模型[9]有Logistic混沌模型、Tent混沌模型等，多数文献采用Logistic模型[10-11]。文中选用Tent混沌模型，Tent映射的形式如下：

(7)

其中，xn∈[0,1]，μ∈(0,2]。μ>1时，表示处于混沌状态。

Tent映射经过贝努利移位变换后变为式(8)，这里μ=2。

(8)

由于计算机内部字长的问题，Tent映射经过多次迭代会变为0，即会趋向于固定点。(0,0.25,0.5,0.75)都将会迭代到固定点0，此外还存在(0.2,0.4,0.6,0.8)的小周期。为防止多次迭代后落入固定点和小周期，设计如下方法：当迭代的值xn落入固定点或小周期时，xn=xn+ξ。其中，ξ是很小的值。

2.3 混沌蚁群算法

原始蚁群算法初始化时，每条线路上采用的信息素值一样，这样能够让蚂蚁选择线路时保持各条路要走的概率一样，但是，这样让蚂蚁在短时间内找到最优的路线是比较困难的，因而收敛速度比较慢。因此，文中提出混沌蚁群算法[12-13](CACO)，信息素初始化时并不采用相同的值，而是利用混沌的特性，进行混沌初始化，这样可以获取较优解。

算法中每一次迭代，不管蚂蚁走过的路线是优是劣都会留下信息素，当在比较劣的解下时，留下信息素后，就会对接下来的迭代造成干扰，引起许多无效的搜索。于是文中改进的方法是选择较优解的情况下才留下信息素，这样能加快收敛速度，缩短运行时间。

原始蚁群算法利用了正反馈的原理，一定程度上加快了寻优进程，但存在一些缺陷，如可能出现停滞现象，陷入局部最优解[14]。文中改进的方法是加入混沌扰动的特性，当其陷入局优解时能够从中跳出，将信息素更新公式修改为：

τij(t+n)=(1-ρ)·τij(t)+Δτij(t)+q·f(xn)

(9)

其中，f(xn)为混沌变量，由式(8)层层迭代得到；q为系数。

CACO算法步骤如下：

Step1：基于Tent映射的混沌初始化。

Step2：将M只蚂蚁放在起始(start)位置，令k=0。

Step3：迭代次数增加一次，Nc=Nc+1。

Step4：蚂蚁数量加1，k=k+1。

Step6：如果蚂蚁的数量大于M，则进入Step7；否则进入Step4。

Step7：根据式(9)更新每条路线的信息素。

Step8：如果大于最大的迭代次数，则输出最优结果，结束程序；否则进入Step3。

3 实验对比及分析

为验证CACO算法解决Web服务组合的有效性，采用图2的Web服务组合的结构模型。其中，m=10，n=10。参数设置为：蚂蚁总数100，信息启发因子1.5，期望启发因子2.0，挥发度0.35，迭代次数300，总信息素100，实验次数500，λ的取值可以自适应选取，如想选出第一次迭代中的前30%的数据进行更新。鉴于目前没有统一的实验平台和相关数据集，QoS的属性值均是随机产生的，范围为[0,5]。实验环境为华硕K42JC,Intel(R)Core(TM)i5-460M,CPU@ 2.53GHz,2GBRAM,Windows7,VisualStudio2013。最终计算的是500次解的平均值、最劣解、最优解、方差和运行时间。

实验数据如表3和图3所示。

图3 算法平均适应度值演变趋势

从数据的分析可以看出，CACO的平均值、最劣解值、最优解值都大于其他算法，收敛速度也快于其他算

表3 算法的结果对比

法，方差和相应时间均小于其他算法，因此，CACO的性能优于其他算法。当在原始蚁群算法中加入混沌初始化后，平均值和最优解都能得到较好的改进，但最劣解并未得到改善;当继续加入混沌扰动后，能避免算法陷入局部最优，进一步改善平均值，但因多次调用Tent映射算法，运行时间明显变长;当加入择优方案后，运行时间明显缩短，且平均值、最劣解、最优解都较好，方差也小。所以文中提出的算法运行时间短、收敛速度快且稳定性高。

4 结束语

文中建立了基于QoE的模糊专家系统的评估模型，并将其转化成Web服务组合优化的QoE数学模型。通过加入混沌初始化、择优策略和混沌扰动，改进了ACO算法来解决Web服务组合优化问题。实验分析证实了CACO算法的可行性与有效性。

但是，基于QoE的Web服务组合模型还不够成熟，有必要进行进一步的研究与探讨。同时，改进的蚁群算法中选取何种映射最优以及能否适应大规模的场景也有待研究。

[1]JulaA,SundararajanE,OthmanZ.Cloudcomputingservicecomposition:asystematicliteraturereview[J].ExpertSystemswithApplications,2014,41(8):3809-3824.

[2]PokhrelJ,LalanneF,CavalliaA,etal.QoEestimationforwebserviceselectionusingafuzzy-roughhybridexpertsystem[C]//IEEEinternationalconferenceonadvancedinformationnetworkingandapplication.[s.l.]:IEEE,2014:629-634.

[3]PokhrelJ,WehbiB,MoraisA,etal.EstimationofQoEofvideotrafficusingafuzzyexpertsystem[C]//Consumercommunicationsandnetworkingconference.[s.l.]:IEEE,2013:224-229.

[4] 夏 虹,李增智.粒子群算法求解Web服务组合中基于QoS的服务选择[J].北京邮电大学学报，2009,32(4):63-67.

[5]TaoF,LailiY,XuL,etal.FC-PACO-RM:aparallelmethod

forservicecompositionoptimal-selectionincloudmanufacturingsystem[J].IEEETransactionsonIndustrialInformatics,2013,9(4):2023-2033.

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

[7]MaXiaoping,WangYongdong,FanYang.Afurtherstudyonfuzzyevidencetheory[C]//Chinesecontrolconference.[s.l.]:[s.n.],2007:363-366.

[8]GuPing,XiuChunbo,ChengYi,etal.Adaptiveantcolonyoptimizationalgorithm[C]//Internationalconferenceonmechatronicsandcontrol.[s.l.]:[s.n.],2014:95-98.

[9]HeJ,ChenL,WangX,etal.Webservicecompositionoptimizationbasedonimprovedartificialbeecolonyalgorithm[J].JournalofNetworks,2013,8(9):2143-2149.

[10] 李丽香，彭海朋，杨义先.混沌蚁群算法及应用[M].北京：中国科学技术出版社，2013.

[11]GongWei,WangShoubin.Chaosantcolonyoptimizationandapplication[C]//Internetcomputingforscienceandengineering.[s.l.]:[s.n.],2009:301-303.

[12]ZhangDaqiao,XianYong,LiJie,etal.UAVpathplanningbasedonchaosantcolonyalgorithm[C]//Internationalconferenceoncomputerscienceandmechanicalautomation.[s.l.]:[s.n.],2015:23-25.

[13]ZhengZhongwu,QinYali.RemotesensingimageclassificationoffuzzyC-meansclusteringbasedonthechaosantcolonyalgorithm[C]//Internationalcongressonimageandsignalprocessing.[s.l.]:[s.n.],2015:14-16.

[14]ZhaoZ,HongX,WangS.Awebservicecompositionmethodbasedonmerginggeneticalgorithmandantcolonyalgorithm[C]//Internationalconferenceoncomputerandinformationtechnology.[s.l.]:[s.n.],2015:1007-1011.

Investigation on Optimization of Web Service Composition Employing Chaos Ant Colony Algorithm

CHENG Song,ZHOU Jing-quan,CHANG Rui-yun

(College of Electronic Science and Engineering,Nanjing University of Posts and Telecommunications, Nanjing 210003,China)

In order to satisfy the users’ increasing demands on Quality of Experience (QoE) of services,Web service composition based on QoE is proposed.On the basis of Fuzzy Expert System,the mathematical model of QoE applied to Web service composition optimizing problem is put forward.Chaos Ant Colony Optimization (CACO) is used to solve Web service composition.According to the ergodicity,randomness and regularity of chaos,the algorithm adds to the chaos disturbance to avoid falling into local optimal solution and the global optimal solution will be found.Compared with the original Artificial Bee Colony (ABC),Particle Swarm Optimazation (PSO) and Ant Colony Optimization (ACO),the experimental results show that CACO has shorter operating time,faster convergence and high stability in Web service composition problem and has a better developmental prospect.

Web service composition;Fuzzy Expert System;QoE;CACO

2016-04-06

2016-08-02

时间：2017-01-10

国家自然科学基金资助项目(61401225);中国博士后科学基金资助项目(2015M571790)

承 松(1991-)，男，硕士研究生，研究方向为Web服务组合；周井泉，博士，教授，硕士生导师，研究方向为通信网络的信息管理和控制。

http://www.cnki.net/kcms/detail/61.1450.TP.20170110.1028.062.html

TP301

A

1673-629X(2017)02-0178-04

10.3969/j.issn.1673-629X.2017.02.041