承 松，周井泉，常瑞云

(南京郵電大學 電子科學與工程學院，江蘇 南京 210003)

混沌蟻群算法的Web服務(wù)組合優(yōu)化研究

承 松，周井泉，常瑞云

(南京郵電大學 電子科學與工程學院，江蘇 南京 210003)

為保證Web服務(wù)組合滿足用戶對Web服務(wù)質(zhì)量日益增長的需求，提出了基于體驗質(zhì)量(Quality of Experience，QoE)的Web服務(wù)組合優(yōu)化方法，即建立模糊專家系統(tǒng)(Fuzzy Expert System)QoE評估模型，并轉(zhuǎn)化為Web服務(wù)組合優(yōu)化的數(shù)學模型，采用混沌蟻群算法(Chaos Ant Colony Optimization，CACO)進行Web服務(wù)組合優(yōu)化求解。該方法利用混沌算法的遍歷性、隨機性和規(guī)律性，通過引入混沌擾動來避免優(yōu)化過程中出現(xiàn)局部最優(yōu)解，以期獲得服務(wù)組合的全局最優(yōu)解。為驗證CACO算法的可行性和有效性，對其與人工蜂群算法(ABC)、粒子群算法(PSO)和原始蟻群算法(ACO)等進行了同步對比實驗。實驗結(jié)果表明，CACO算法相比其他算法具有運行時間短、收斂速度快且穩(wěn)定性高的優(yōu)點，具有較好的發(fā)展前景。

Web服務(wù)組合；模糊專家系統(tǒng)；用戶體驗質(zhì)量；混沌蟻群算法

0 引 言

隨著互聯(lián)網(wǎng)的快速發(fā)展，工商業(yè)領(lǐng)域到處都充滿著Web服務(wù)。因此，產(chǎn)生了許多功能相同的Web服務(wù)。此外，單個Web服務(wù)不能完全解決用戶提出的各方面請求。因此，把互聯(lián)網(wǎng)中各個功能單一的Web服務(wù)按照某種有效的方式組合起來，從而提高效率[1]。

目前廣泛采用的服務(wù)度量標準為QoS(Quality of Service)，QoS評價指標主要包括信譽度、可用性、成本費用、響應(yīng)時間等。但這僅僅反映了服務(wù)技術(shù)方面的特性，忽略了用戶的主觀方面，所以不能夠反映用戶對服務(wù)的滿意程度。體驗質(zhì)量(Quality of Experience，QoE)是憑借用戶滿意程度作為評價標準的。它結(jié)合了網(wǎng)絡(luò)性能、業(yè)務(wù)質(zhì)量、主觀評測等影響因素，直接反映了用戶對服務(wù)舒適度的滿意程度。文獻[2]對于QoS不能滿足服務(wù)體驗質(zhì)量的滿意程度，建立了評估QoE的模糊粗糙混合的專家系統(tǒng)模型。文獻[3]運用模糊專家系統(tǒng)解決了在視頻交通中的QoE評估。

Web服務(wù)組合實質(zhì)為NP難問題，目前主流算法是智能優(yōu)化算法。文獻[4]提出了基于PSO的優(yōu)化算法，主要是為了解決Web服務(wù)組合問題在QoS方面的服務(wù)選擇問題。文獻[5]提出了一種具有反射遷移的并行自適應(yīng)混沌優(yōu)化的并行算法，解決了云制造資源分配的問題。

綜上所述，智能優(yōu)化算法在解決Web服務(wù)組合方面是非常有價值的研究方向。文中建立了Web服務(wù)的QoE評價模型，提出了CACO算法。對比實驗結(jié)果表明，CACO算法由于加入了混沌初始化、擇優(yōu)策略和混沌擾動，展現(xiàn)出比原始ACO、ABC、PSO等算法更好的收斂性、穩(wěn)定性和運算效率。

1 問題描述

1.1 Web服務(wù)組合相關(guān)技術(shù)

Web服務(wù)供應(yīng)者、需求者和中介者是Web服務(wù)技術(shù)架構(gòu)里的三個主要角色，通過注冊、調(diào)用、綁定來調(diào)用互聯(lián)網(wǎng)中的Web服務(wù)[6]。服務(wù)需求者會將他們的需求信息反饋給服務(wù)中介者，服務(wù)中介者根據(jù)需求者的需求信息選擇一個最優(yōu)的服務(wù)發(fā)送給供應(yīng)者，服務(wù)中介者又從服務(wù)供應(yīng)者那里獲取服務(wù)。

1.2 基于QoE的Web服務(wù)組合模型

QoE的計算過程為將QoS參數(shù)通過模糊專家系統(tǒng)計算出QoE的值。與以往通過簡單的等式將QoE與QoS屬性串聯(lián)起來的客觀評價方法不同，文中融入了模糊理論與專家系統(tǒng)，選取了響應(yīng)時間(T)、可用性

(A)及成本(C)這些與Web服務(wù)QoE相關(guān)聯(lián)的QoS參數(shù)作為QoE的評價指標。模糊集可以用不同的形狀來表示，一般情況下三角形、四邊形就足以表達專家知識，而且還能簡化計算過程。文中創(chuàng)建了響應(yīng)時間、可用性和成本的模糊集。根據(jù)圖1的模糊集與表1、表2的決策表來計算精確的QoE值。

圖1 響應(yīng)時間、可用性和成本的模糊集

指標低中高響應(yīng)時間(T)T≤1．51．53．5可用性(A)A≤224成本(C)C≤224

表2 滿意程度表

注：表中用數(shù)字來表示滿意程度，0表示非常不滿意，1表示不滿意，2表示較差，3表示一般，4表示良好，5表示滿意，6表示非常滿意。

適應(yīng)度函數(shù)如式(1)所示：

(1)

式(1)表示蟻群算法中螞蟻走過路線上QoE信息的總和，其值越大，表明所求的解越優(yōu)。

2 算法描述

2.1 原始蟻群算法

原始蟻群算法[7-8]是通過運用人工螞蟻所行走的路線來表示求出的最優(yōu)解的一種方法。螞蟻通過走過的路線上留下的信息素尋找到最優(yōu)的路線。在路線上所留的信息素越多，表明這條路線越優(yōu)。

文中選用串聯(lián)的模型，如圖2所示。其中，WSCSm為第m個服務(wù)候選集；CSn為某個服務(wù)候選集中的第n個服務(wù)。

圖2 串聯(lián)的Web服務(wù)實例

(2)

其中，allowedk表示在t時刻第k只螞蟻接下來可以選擇的服務(wù)；α表示信息啟發(fā)式因子；β表示期望啟發(fā)式因子；ηij(t)表示由i移動到j(luò)的期望程度，取值如下：

ηij(t)=value(QoE)

(3)

為防止剩余在路線上信息素過多而完全掩蓋了啟發(fā)信息，在M只螞蟻從start走到end后，更新路線上剩余的信息素。t+n時刻在路線(i,j)上信息量可按照式(4)和式(5)進行更新。

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

(4)

(5)

根據(jù)信息素更新策略的不同，文中選擇蟻周模型，如式(6)所示。利用全局信息，當執(zhí)行完一次后才更新所有線路上的信息素。

(6)

原始蟻群算法的實現(xiàn)步驟如下：

Step1：初始化參數(shù)。

Step2：將M只螞蟻放于起始(start)位置，令k=0，k為第k只螞蟻。

Step3：迭代次數(shù)增加一次，Nc=Nc+1。

Step4：螞蟻數(shù)量加1，k=k+1。

Step5：根據(jù)轉(zhuǎn)移概率，運用輪盤選擇的方式選擇接下來的服務(wù)，直至尋找到終點。

Step6：如果螞蟻的數(shù)量大于M，則進入Step7；否則進入Step4。

Step7：根據(jù)式(4)更新每條線路上的信息素。

Step8：如果大于最大的迭代次數(shù)，則輸出最優(yōu)結(jié)果，結(jié)束程序；否則進入Step3。

2.2 混沌模型

典型的混沌模型[9]有Logistic混沌模型、Tent混沌模型等，多數(shù)文獻采用Logistic模型[10-11]。文中選用Tent混沌模型，Tent映射的形式如下：

(7)

其中，xn∈[0,1]，μ∈(0,2]。μ>1時，表示處于混沌狀態(tài)。

Tent映射經(jīng)過貝努利移位變換后變?yōu)槭?8)，這里μ=2。

(8)

由于計算機內(nèi)部字長的問題，Tent映射經(jīng)過多次迭代會變?yōu)?，即會趨向于固定點。(0,0.25,0.5,0.75)都將會迭代到固定點0，此外還存在(0.2,0.4,0.6,0.8)的小周期。為防止多次迭代后落入固定點和小周期，設(shè)計如下方法：當?shù)闹祒n落入固定點或小周期時，xn=xn+ξ。其中，ξ是很小的值。

2.3 混沌蟻群算法

原始蟻群算法初始化時，每條線路上采用的信息素值一樣，這樣能夠讓螞蟻選擇線路時保持各條路要走的概率一樣，但是，這樣讓螞蟻在短時間內(nèi)找到最優(yōu)的路線是比較困難的，因而收斂速度比較慢。因此，文中提出混沌蟻群算法[12-13](CACO)，信息素初始化時并不采用相同的值，而是利用混沌的特性，進行混沌初始化，這樣可以獲取較優(yōu)解。

算法中每一次迭代，不管螞蟻走過的路線是優(yōu)是劣都會留下信息素，當在比較劣的解下時，留下信息素后，就會對接下來的迭代造成干擾，引起許多無效的搜索。于是文中改進的方法是選擇較優(yōu)解的情況下才留下信息素，這樣能加快收斂速度，縮短運行時間。

原始蟻群算法利用了正反饋的原理，一定程度上加快了尋優(yōu)進程，但存在一些缺陷，如可能出現(xiàn)停滯現(xiàn)象，陷入局部最優(yōu)解[14]。文中改進的方法是加入混沌擾動的特性，當其陷入局優(yōu)解時能夠從中跳出，將信息素更新公式修改為：

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

(9)

其中，f(xn)為混沌變量，由式(8)層層迭代得到；q為系數(shù)。

CACO算法步驟如下：

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

Step2：將M只螞蟻放在起始(start)位置，令k=0。

Step3：迭代次數(shù)增加一次，Nc=Nc+1。

Step4：螞蟻數(shù)量加1，k=k+1。

Step6：如果螞蟻的數(shù)量大于M，則進入Step7；否則進入Step4。

Step7：根據(jù)式(9)更新每條路線的信息素。

Step8：如果大于最大的迭代次數(shù)，則輸出最優(yōu)結(jié)果，結(jié)束程序；否則進入Step3。

3 實驗對比及分析

為驗證CACO算法解決Web服務(wù)組合的有效性，采用圖2的Web服務(wù)組合的結(jié)構(gòu)模型。其中，m=10，n=10。參數(shù)設(shè)置為：螞蟻總數(shù)100，信息啟發(fā)因子1.5，期望啟發(fā)因子2.0，揮發(fā)度0.35，迭代次數(shù)300，總信息素100，實驗次數(shù)500，λ的取值可以自適應(yīng)選取，如想選出第一次迭代中的前30%的數(shù)據(jù)進行更新。鑒于目前沒有統(tǒng)一的實驗平臺和相關(guān)數(shù)據(jù)集，QoS的屬性值均是隨機產(chǎn)生的，范圍為[0,5]。實驗環(huán)境為華碩K42JC,Intel(R)Core(TM)i5-460M,CPU@ 2.53GHz,2GBRAM,Windows7,VisualStudio2013。最終計算的是500次解的平均值、最劣解、最優(yōu)解、方差和運行時間。

實驗數(shù)據(jù)如表3和圖3所示。

圖3 算法平均適應(yīng)度值演變趨勢

從數(shù)據(jù)的分析可以看出，CACO的平均值、最劣解值、最優(yōu)解值都大于其他算法，收斂速度也快于其他算

表3 算法的結(jié)果對比

法，方差和相應(yīng)時間均小于其他算法，因此，CACO的性能優(yōu)于其他算法。當在原始蟻群算法中加入混沌初始化后，平均值和最優(yōu)解都能得到較好的改進，但最劣解并未得到改善;當繼續(xù)加入混沌擾動后，能避免算法陷入局部最優(yōu)，進一步改善平均值，但因多次調(diào)用Tent映射算法，運行時間明顯變長;當加入擇優(yōu)方案后，運行時間明顯縮短，且平均值、最劣解、最優(yōu)解都較好，方差也小。所以文中提出的算法運行時間短、收斂速度快且穩(wěn)定性高。

4 結(jié)束語

文中建立了基于QoE的模糊專家系統(tǒng)的評估模型，并將其轉(zhuǎn)化成Web服務(wù)組合優(yōu)化的QoE數(shù)學模型。通過加入混沌初始化、擇優(yōu)策略和混沌擾動，改進了ACO算法來解決Web服務(wù)組合優(yōu)化問題。實驗分析證實了CACO算法的可行性與有效性。

但是，基于QoE的Web服務(wù)組合模型還不夠成熟，有必要進行進一步的研究與探討。同時，改進的蟻群算法中選取何種映射最優(yōu)以及能否適應(yīng)大規(guī)模的場景也有待研究。

[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服務(wù)組合中基于QoS的服務(wù)選擇[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] 汪定偉.智能優(yōu)化方法[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] 李麗香，彭海朋，楊義先.混沌蟻群算法及應(yīng)用[M].北京：中國科學技術(shù)出版社，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服務(wù)組合；周井泉，博士，教授，碩士生導師，研究方向為通信網(wǎng)絡(luò)的信息管理和控制。

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