混沌蟻群算法的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