承 松，周井泉，常瑞云

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

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

承 松，周井泉，常瑞云

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

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

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

0 引 言

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

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

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

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

1 問(wèn)題描述

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

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

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

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

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

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

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

表2 滿(mǎn)意程度表

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

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

(1)

式(1)表示蟻群算法中螞蟻?zhàn)哌^(guò)路線(xiàn)上QoE信息的總和，其值越大，表明所求的解越優(yōu)。

2 算法描述

2.1 原始蟻群算法

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

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

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

(2)

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

ηij(t)=value(QoE)

(3)

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

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

(4)

(5)

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

(6)

原始蟻群算法的實(shí)現(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)移概率，運(yùn)用輪盤(pán)選擇的方式選擇接下來(lái)的服務(wù)，直至尋找到終點(diǎn)。

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

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

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

2.2 混沌模型

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

(7)

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

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

(8)

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

2.3 混沌蟻群算法

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

算法中每一次迭代，不管螞蟻?zhàn)哌^(guò)的路線(xiàn)是優(yōu)是劣都會(huì)留下信息素，當(dāng)在比較劣的解下時(shí)，留下信息素后，就會(huì)對(duì)接下來(lái)的迭代造成干擾，引起許多無(wú)效的搜索。于是文中改進(jìn)的方法是選擇較優(yōu)解的情況下才留下信息素，這樣能加快收斂速度，縮短運(yùn)行時(shí)間。

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

τ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，則進(jìn)入Step7；否則進(jìn)入Step4。

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

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

3 實(shí)驗(yàn)對(duì)比及分析

為驗(yàn)證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í)驗(yàn)次數(shù)500，λ的取值可以自適應(yīng)選取，如想選出第一次迭代中的前30%的數(shù)據(jù)進(jìn)行更新。鑒于目前沒(méi)有統(tǒng)一的實(shí)驗(yàn)平臺(tái)和相關(guān)數(shù)據(jù)集，QoS的屬性值均是隨機(jī)產(chǎn)生的，范圍為[0,5]。實(shí)驗(yàn)環(huán)境為華碩K42JC,Intel(R)Core(TM)i5-460M,CPU@ 2.53GHz,2GBRAM,Windows7,VisualStudio2013。最終計(jì)算的是500次解的平均值、最劣解、最優(yōu)解、方差和運(yùn)行時(shí)間。

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

[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].北京郵電大學(xué)學(xué)報(bào)，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].北京：中國(guó)科學(xué)技術(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

時(shí)間：2017-01-10

國(guó)家自然科學(xué)基金資助項(xiàng)目(61401225);中國(guó)博士后科學(xué)基金資助項(xiàng)目(2015M571790)

承 松(1991-)，男，碩士研究生，研究方向?yàn)閃eb服務(wù)組合；周井泉，博士，教授，碩士生導(dǎo)師，研究方向?yàn)橥ㄐ啪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