王妍，劉瑜嵐，荊紫慧，張以文

（安徽大學計算機科學與技術學院計算智能與信號處理教育部重點實驗室，安徽合肥230031）

基于混沌機制和改進粒子群算法的Web服務組合優(yōu)化

王妍，劉瑜嵐，荊紫慧，張以文*

（安徽大學計算機科學與技術學院計算智能與信號處理教育部重點實驗室，安徽合肥230031）

隨著互聯(lián)網(wǎng)和大數(shù)據(jù)的迅速發(fā)展，如何從大量Web服務中選擇合適服務及組合以滿足用戶需求已成為新的熱點。本文提出一種改進的混沌粒子群優(yōu)化（ICPSO）算法，應用到Web服務組合優(yōu)化問題。針對傳統(tǒng)PSO算法易陷入早熟收斂和局部最優(yōu)的缺點，該算法引入了混沌擾動機制使粒子易跳出局部極值，增強了種群多樣性，從而提高算法尋優(yōu)能力。最后通過仿真實驗驗證了ICPSO算法的可行性和有效性。

服務組合；ICPSO算法；混沌機制；服務質(zhì)量

隨著面向服務計算（service-oriented computing）技術的迅速發(fā)展，基于Web服務的分布式計算模式正成為技術發(fā)展的趨勢[1,2]。Web服務作為一種能夠自適應、自描述和模塊化的應用模式，吸收了分布式計算、網(wǎng)格計算和XML等各種技術的優(yōu)點，包括平臺無關性、松散耦合性、規(guī)范約束協(xié)議以及封裝性等，使其廣泛應用于基于Internet環(huán)境的異構系統(tǒng)的互操作與應用系統(tǒng)集成。

然而，越來越多的功能相同或相近而服務質(zhì)量不同的服務出現(xiàn)在網(wǎng)絡上。而單個Web服務所具有的功能一般都比較單一，無法滿足用戶服務質(zhì)量（Quality of Service,QoS）的復雜需求，因此如何從多個功能單一的Web候選服務中挑選出若干服務并形成一個滿足用戶復雜需求的組合服務已成為服務計算領域的研究重點[3,4]。為了能夠滿足用戶業(yè)務需求，提供更強大的服務功能，有必要根據(jù)特定的應用場景和需求對現(xiàn)有的服務進行有效的組合。因此Web服務組合問題也就成了典型的NP-hard問題。

為此，本文提出了一種基于混沌理論的改進的粒子群算法來解決Web服務組合優(yōu)化問題，其基本思想體現(xiàn)在以下幾個方面：

1 相關工作

近年來，工業(yè)界和學業(yè)界分別應用不同的方法對Web服務組合優(yōu)化問題進行了研究。在服務組合優(yōu)化問題研究中，服務組合模型是由多個服務節(jié)點按照一定的邏輯順序關系組成，每個服務節(jié)點是若干服務實例的抽象類，這些候選服務實例具有相同功能但不同非功能屬性（QoS），且QoS又是評價一個Web服務的重要指標。目前，基于QoS的服務組合優(yōu)化方法主要可分為兩大類，第一類是傳統(tǒng)計算方式的優(yōu)化方法，如窮舉法、動態(tài)規(guī)劃、線性規(guī)劃、和圖算法等。Alrifai等人[5]提出了一個把全局優(yōu)化和局部選擇技術結合在一起的混合方案去解決服務組合問題。范小芹等人[6]利用隨機型離散事件系統(tǒng)的馬爾科夫決策過程(MDP),提出了Web服務各隨機QoS指標的度量方法，設計出隨機QoS感知的可靠Web服務組合算法。第二類是智能優(yōu)化算法，如遺傳算法、蟻群算法、粒子群算法等。張成文等人[7]提出一種基于遺傳算法的QoS感知的Web服務選擇算法，可以有效的從全部組合方案中選出滿足用戶QoS需求的服務組合。Zhang等人[8]在服務組合優(yōu)化過程中應用蟻群算法提出了一個基于QoS的動態(tài)服務組合方法。與遺傳算法和蟻群算法相比，粒子群算法具有參數(shù)少、收斂速度快的特點，在很多優(yōu)化問題上表現(xiàn)出良好的搜索能力。劉莉平等人[9]針對現(xiàn)有服務組合中QoS優(yōu)化的不足，利用粒子群算法的智能優(yōu)化原理加快粒子群的搜索速度，提出了一種基于粒子群算法的QoS動態(tài)服務組合算法，不過該算法中種群的粒子容易陷入局部最優(yōu)值。范小芹等人[10]提出了一種面向動態(tài)Web服務選擇的離散粒子群算法，為了增強算法的全局搜索能力，定義相關的準則。胡旺等人[11]采用簡化粒子群優(yōu)化方程和添加極值擾動算子兩種策略，提出了簡化粒子群優(yōu)化算法，避免了由粒子速度引起的粒子發(fā)散而導致后期收斂慢和精度低的問題?；谝陨戏治觯琍SO算法較其他方法能更好的解決服務組合優(yōu)化問題，但在進行組合時種群的粒子易被當前全局最優(yōu)粒子吸引而快速收斂于局部最優(yōu)值。同時，候選服務的規(guī)模越來越大，傳統(tǒng)的優(yōu)化技術已無法有效地處理該問題。為此，本文提出了改進的混沌粒子群算法解決服務組合優(yōu)化問題，引入混沌優(yōu)化思想提高種群多樣性。

2 組合服務模型描述

定義1Web服務（WS）是一種具有跨平臺、低耦合、高度可集成、模塊化的軟件應用程序。用WSi=(Ii,Oi,QoSi)表示一個服務，其中Ii為第i個服務的輸入，Oi為第i個服務的輸出，QoSi為其對應的非功能屬性服務質(zhì)量。

定義2服務質(zhì)量（QoS）是服務的非功能屬性，本文中服務QoS用一個四元組表示QoS=(T,C,A,R)，其中T表示響應時間，C表示調(diào)用一次服務的費用，A表示可用性，R表示可靠性。

定義3候選服務集（SS）是由一組具體Web服務組成的集合，這些服務具有一樣的功能但QoS不同。組合服務模型中每個服務都有一個相對應的候選服務集，用SSj表示第j個服務對應的候選服務集。

定義4組合服務（CS）是由候選服務集中服務依據(jù)服務模型，形成的一個具體的Web服務序列。用一個五元組表示CS=(QoS,L,S,W,F)，其中本文服務包含四個QoS屬性，L是服務直接關系的集合，W是屬性權重W={w1,w2,w3,w4}且w1+w2+w3+w4=1，S是組合模型中的所有服務集S={S1,S2,...,Sj,...,Sn}，F(xiàn)是組合服務評價函數(shù)。

Web組合服務有多個原子服務組合而成，原子服務之間有明確的邏輯執(zhí)行循序。服務組合是根據(jù)各原子服務間的邏輯關系，重用已有的Web服務，組合成能夠滿足用戶業(yè)務需求的服務組合。根據(jù)其邏輯執(zhí)行關系，服務組合流程有如下四種基本結構。

以上模型的QoS計算公式如表1所示。

表1 組合服務的QoS計算公式

對以上Web服務的QoS屬性，可劃分為兩種類型：積極型和消極型。積極型（positive型)，其指標值越大服務質(zhì)量越好，如可靠性、可用性。消極型（negative型)，如響應時間、費用等，其指標越小，服務質(zhì)量越好。為統(tǒng)一度量組合服務的QoS屬性，需要對各個QoS屬性進行標準化?？刹捎霉剑?）和（2）分別對消極屬性和積極屬性進行歸一化處理。

Qh,k表示第h類服務中的某個Web服務實例的第k個質(zhì)量屬性，為第h類服務中的某個Web服務實例的第k個質(zhì)量屬性的最大值，為最小值。對于消極屬性采用公式（1）計算，而對于積極屬性則可采用公式（2）計算。Qh,k為轉換后的質(zhì)量屬性，其值越大表示QoS屬性越好。

3 標準PSO算法

PSO算法是1995年由Eberhart和Kennedy博士提出的一種啟發(fā)式進化計算方法[12]，來源于對生物群體智能行為的簡化模擬。PSO算法在初始階段隨機產(chǎn)生一個初始種群并賦予種群中每個粒子一個隨機速度，在飛行過程中粒子速度依據(jù)自身以及種群飛行經(jīng)驗進行不斷調(diào)整，使整個種群能夠飛向更好的搜索區(qū)域，從而發(fā)現(xiàn)較優(yōu)的解。

PSO具體算法具體實現(xiàn)步驟描述如下：

Step 1初始化粒子群，隨機初始化種群中每個粒子的位置與速度。

Step 2根據(jù)適應度函數(shù)Fitness(x)，計算出每個粒子位置的適應度值。

Step 3更新pbest，對比粒子本次迭代位置與其歷史最佳位置，若Fitness(xi)＞Fitness(pbest)，則Fitness(pbest)=Fitness(xi)。

Step 4更新gbest，找出當前種群中適應度值最大的粒子，假設為xg，若Fitness(xg)＞Fitness(gbest)，則Fitness(gbest)=Fitness(xg)。

Step 5根據(jù)公式（3）和（4）更新粒子的位置和速度。

Step 6檢驗是否滿足終止條件(通常是達到最大迭代次數(shù)或得到滿足一定條件的較優(yōu)解)，若滿足，終止迭代，算法結束。否則返回步驟Step 2。

4 基于改進ICPSO算法的服務組合算法

4.1 混沌機制及其特性

一般將由確定性方程得到的具有隨機性的運動狀態(tài)稱為混沌，混沌狀態(tài)廣泛存在于自然現(xiàn)象和社會現(xiàn)象中，是非線性系統(tǒng)中一種較為普遍的現(xiàn)象，其行為復雜且類似隨機。混沌變化過程看似一片混亂，但實際上并不是一片混亂，而是有著內(nèi)在結構的一類現(xiàn)象。

混沌變量有以下特點：隨機性即它的分布雜亂，如同隨機變量。遍歷性即它可以遍歷空間區(qū)域內(nèi)的所有狀態(tài)且不重復。規(guī)律性該變量是由確定的混沌模型迭代導出的。

混沌優(yōu)化算法是一種智能優(yōu)化算法，利用混沌特性在一定范圍內(nèi)進行優(yōu)化搜索。其基本思想是首先產(chǎn)生一組混沌變量，其數(shù)量與待求解問題中的優(yōu)化變量相同，利用混沌變量具有隨機性、遍歷性和規(guī)律性的特點進行混沌擾動產(chǎn)生新解，同時把混沌變量的運動范圍映射到優(yōu)化變量的解空間，對優(yōu)化變量做出優(yōu)劣評價，經(jīng)多次迭代，最終產(chǎn)生最優(yōu)解。Logistic映射方程是一個典型的混沌系統(tǒng)[13]：

其中μ為控制變量，當μ=4時，系統(tǒng)（5）進入完全混沌狀態(tài)，對于任意的χ(0)∈[0,1],可根據(jù)Logistic方程迭代出一個序列χ(1)，χ(2)，χ(3),…。

4.2 算法改進策略

4.2.1 混沌初始化種群

假設種群中有m個粒子群，搜索空間為n維,即Web服務組合模型中有n個服務類。粒子位置變量則表示服務組合優(yōu)化的解（即可行的組合服務方案），粒子的位置可用一個n維向量來表示，本文采用整數(shù)編碼，若第j個服務類Sj對應的候選服務集規(guī)模為hj，候選服務集中的每個候選服務依次進行編碼，則第z個候選服務對應的編號為z，其中z是區(qū)間[1,hj]上的整數(shù)，初始化時粒子位置的每一維都是整數(shù)，即對應得候選服務集中Web服務的編號。例如向量xi=(xi,1,xi,2,...,xi,n)表示粒子i的位置，則xi,j表示第i種服務組合方案中第j個服務類的編號為xi,j的候選服務。

本文采用混沌序列初始化粒子群中的粒子，對簡單的一維邏輯混沌映射模型公式（5）的進行重寫，描述形式如下：

其中，μ取值與公式（5）相同，t是迭代次數(shù)，ctj為粒子位置在j維上的混沌變量，初始化生一個n維的混沌序列，采用公式（6）進行m-1次混沌迭代，即則產(chǎn)生m-1個混沌序列，然后將每個混沌序列利用公式（4）行映射到粒子位置解空間，最終得到m個粒子的初始化位置。

hj是第k個粒子位置第j維的解空間大小，即第j個服務類的候選服務規(guī)模。對變量四舍五入，保證粒子位置映射到解空間。

4.2.2 早熟收斂處理機制

PSO算法解決服務組合優(yōu)化問題時種群易陷入早熟收斂狀態(tài)，導致得到的解很可能不是全局最優(yōu)的，本文根據(jù)種群的多樣性和種群在進化過程中找到最優(yōu)解的波動程度，判斷種群是否陷入早熟收斂，同時采用Chaos-Process混沌擾動機制處理粒子群早熟收斂狀態(tài)，提高種群多樣性。本文參考文獻[14]，當粒子群多樣性小于0.35且K代最優(yōu)算法平均數(shù)在連續(xù)10代內(nèi)不發(fā)生變化，則認為滿足收斂條件，粒子群早熟，此時啟動混沌擾動機制增加種群多樣性。

混沌擾動機制Chaos-Process描述如下：

將Chaos1i[j]映射到粒子維數(shù)區(qū)間[1,n]內(nèi)得到num1，然后將Chaos2i[j]映射到第num1維服務類的候選服務集中得到服務編號num2。用num2替換xi[num1]得到新的粒子位置xi_new，但Fitness(xi)＜Fitness(xi_new)，則xi=xi_new。

當種群陷入早熟收斂時，經(jīng)過Chaos-Process混沌擾動機制處理使種群中所有粒子進行混沌搜索，提高種群多樣性，加速全局最優(yōu)解粒子以及其它粒子附近的進一步搜索，而且可以使粒子更易跳出局部極值，提高算法的尋優(yōu)能力。

4.3 ICPSO算法描述

ICPSO算法首先使用Skyline操作[15]對所有服務類對應的候選服務集進行處理，剔除那些被其他服務支配的候選服務，保留可能成為最優(yōu)服務組合的潛在候選者，從而得到Skyline服務。然后從每個服務類的Skyline服務中進行Web服務選擇，提高了服務選擇效率。采用混沌序列初始化粒子群，使初始種群保留了經(jīng)典PSO算法中的隨機性，同時由于混沌的特性使得種群的多樣性得到提高。Chaos-Process混沌擾動機制針對粒子群易陷入早熟收斂狀態(tài)，進行有效處理，提高種群多樣性改善解質(zhì)量。

ICPSO算法具體實現(xiàn)描述如下：

輸入：所有服務類的候選服務集

輸出：最優(yōu)組合服務

Step 1：使用Skyline操作處理所有服務類的候選服務集，得到每個服務類的Skyline服務。

Step 2：設置當前迭代次數(shù)t=0，并混沌初始化粒子群中m個粒子的位置。

Step 3：計算粒子群中粒子的適應度值

找出種群中全局最優(yōu)粒子下標gi，更新粒子群全局最優(yōu)解

Step 10：計算粒子群多樣性psdis和K代最優(yōu)算術平均kma，判斷粒子群是否收斂。

Step 11：If（滿足收斂條件）then啟動Chaos-Process增加種群多樣性。

Step 12：Ift＜T（最大迭代次數(shù)）then轉到Step 5。

Step 13：結束。

其中，搜索空間為n維，種群規(guī)模為m，X=(x1,x2,…,xm)表示整個粒子群。粒子i位置xi=(xi,1,xi,2,…,xi,n)，速度vi=(vi,1,vi,2,…,vi,n)，粒子i歷史最優(yōu)解pi=(pi,1,pi,2,…,pi,n)，全局最優(yōu)解pg=(pg,1,pg,2,…,pg,n)。

5 實驗設計與結果分析

本文的實驗數(shù)據(jù)采用公共數(shù)據(jù)集QWS[16,17]。實驗基于順序型服務組合模型，且模型中包含7個服務類，默認情況下每個服務類的候選服務集規(guī)模為500，最大迭代次數(shù)為500次，每個候選服務有4個QoS屬性，即響應時間(T，response time)、可靠性（R，reliability）、可用性（A，availability）和費用（C，cost）。QoS屬性值在規(guī)定范圍內(nèi)均勻分布，參數(shù)取值范圍參考表1。ICPSO代表本文提出的算法，CPSO代表文獻[18]中提出的算法是由Wang等人[19]提出的改進粒子群算法以解決服務組合優(yōu)化問題。假設種群規(guī)模m=100，對于以下實驗結果，算法運行50次取平均值。

表1 隨機數(shù)據(jù)集QoS屬性取值范圍

5.1 可行性

為驗證本文提出的ICPSO算法在解決Web服務組合優(yōu)化問題的可行性，將ICPSO算法與其它算法分別在不同服務候選規(guī)模下與不同迭代次數(shù)下的求解質(zhì)量進行對比，實驗結果如圖1所示。

圖1 不同算法的尋優(yōu)性能

通過圖1的實驗結果可以看出，本文算法的尋優(yōu)結果明顯優(yōu)于算法其它兩種算法，CPSO算法與Proposed by Wang算法的尋優(yōu)結果差不多。在ICPSO算法中，本文針對粒子群算法易陷入早熟收斂，導致所求得的解為局部最優(yōu)解的缺點采用Chaos-Process混沌擾動機制進行早熟收斂處理。引入混沌優(yōu)化的思想使種群中所有粒子進行混沌搜索，提高種群多樣性，加速全局最優(yōu)粒子以及其它粒子附近的進一步搜索，而且可以使粒子更易跳出局部極值，從而使更易找到更好的解。

5.2 穩(wěn)定性

為驗證本文提出的ICPSO算法在解決Web服務組合優(yōu)化問題的穩(wěn)定性，將ICPSO算法與其它算法分別在不同服務候選規(guī)模下與不同迭代次數(shù)下的運行50次實驗所求得解的方差進行了對比，實驗結果如圖2。

通過圖2的實驗結果可以看出，本文的ICPSO算法在不同服務候選規(guī)模下與不同迭代次數(shù)下的方差小于其它兩種算法，所以ICPSO算法具有較好的穩(wěn)定性，總體上比CPSO算法好。隨著候選服務規(guī)模的增加，組合服務可選方案數(shù)量也增加，因此增加了服務選擇難度，總體上方差值也有小服務的增加，即候選服務規(guī)模越大選優(yōu)性能穩(wěn)定性越差。但由于ICPSO算法先采用Skyline操作對數(shù)據(jù)進行預處理，剔除冗余服務減少了服務選擇空間，在粒子群初始化階段，利用混沌的特征初始化種群，使初始種群中粒子位置既保留了經(jīng)典PSO的隨機性，又利用混沌變量的優(yōu)點提高種群的多樣性與搜索的遍歷性，以及對于粒子群陷入早熟時的處理操作提高求解質(zhì)量，增加較優(yōu)組合服務被選中的幾率，因此算法穩(wěn)定性也有所提高。

圖2 不同算法的穩(wěn)定性

6 結束語

本文研究了標準粒子群算法在Web服務組合優(yōu)化問題上的應用，結合Skyline技術以及混沌的思想提出一種改進的混沌粒子群算法（ICPSO），在數(shù)據(jù)預處理階段引入Skyline操作，減少服務選擇搜索空間，提高服務選擇效率。在初始化階段混沌初始化種粒子群，當種群陷入早熟收斂狀態(tài)時，采用Chaos-Process混沌擾動機制增加粒子群多樣性，增強全局搜索能力，提高服務組合質(zhì)量。最后通過仿真實驗對算法的綜合性能驗證，實驗結果表明，ICPSO在服務優(yōu)化問題上，較其他算法有更好的可行性和有效性。

[1]Papazoglou M P,Traverso P,Dustdar S,et al.Service-Oriented Computing:State of the Art and Research Challenges[J].Computer,2007,40(11):38-45.

[2]鄧水光，吳朝暉.Web服務組合方法綜述[J].中國科技論文在線，2008，3（2）：79-84．

[3]Zhang Y W,Cui G M,Zhao S,et al.IFOA4WSC:a quick and effective algorithm for QoS-aware service composition[J].International Journal of Web&Grid Services,2016,12(1):81-108.

[4]王尚廣，孫其博，楊放春.基于全局QoS約束分解的Web服務動態(tài)選擇[J].軟件學報，2011，22（7）：1426-1439．

[5]Alrifai M,Risse T,Nejdl W.A hybrid approach for efficient Web service composition with end-to-end QoS constraints[J].Acm Transactions on the Web,2012,6 (2):373-382.

[6]范小芹，蔣昌俊，王俊麗，等.隨機QoS感知的可靠Web服務組合[J].軟件學報，2009,20（3）：546-556．

[7]張成文，蘇森，陳俊亮．基于遺傳算法的QoS感知的Web服務選擇[J].計算機學報，2006，29（7）：1029-1037．

[8]Zhang W,Chang C K,Feng T M,et al.QoS-Based Dynamic Web Service Composition with Ant Colony Optimization[C]//Computer Software and Applications Conference(COMPSAC),2010 IEEE 34th Annual. IEEE,2010:493-502.

[9]劉莉平，陳志剛，劉愛心.基于粒子群算法的Web服務組合研究[J].計算機工程，2008，34（5）：104-106．

[10]范小芹，蔣昌俊，方賢文，等.基于離散微粒群算法的動態(tài)Web服務選擇[J].計算機研究與發(fā)展，2010，47（1）：147-156．

[11]胡旺，李志蜀.一種更簡化而高效的粒子群優(yōu)化算法[J].軟件學報，2007，18（4）：861-868．

[12]Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C]//International Symposium on MICRO Machine and Human Science.1995:39-43.

[13]Alatas B,Akin E,Ozer A B.Chaos embedded particle swarm optimization algorithms[J].Chaos Solitons& Fractals,2009,40(4):1715-1734.

[14]溫濤，盛國軍，郭權，等.基于改進粒子群算法的Web服務組合[J].計算機學報，2013，36（05）：1031-1046．

[15]Alrifai M,Skoutas D,Risse T.Selecting skyline services for QoS-based web service composition[C]//International Conference on World Wide Web.2010:11-20. [16]Al-Masri E,Mahmoud Q H.Discovering the best web service:A neural network-based solution[C]//IEEE International Conference on Systems.IEEE,2009: 4250-4255..

[17]Al-Masri E,Mahmoud Q H.QoS-based Discovery and Ranking of Web Services[C]//Computer Communications and Networks,2007.ICCCN 2007.Proceedings of 16th International Conference on.IEEE,2007:529-534.

[18]Wang L,He Y X.Web Service Composition Based on QoS with Chaos Particle Swarm Optimization[C]// Wireless Communications Networking and Mobile Computing(WiCOM),2010 6th International Conference on.IEEE,2010:1-4.

[19]Wang S G,Sun Q B,Zou H,et al.Particle Swarm Optimization with Skyline Operator for Fast Cloud-based Web Service Composition[J].Mobile Networks&Applications,2013,18(1):116-121.

Web service composition optimization based on chaotic mechanism and improved particle swarm optimization

WANG Yan,LIU Yu-lan,JING Zi-hui,ZHANG Yi-wen*
(Key Laboratory of Intelligent Computing and Signal Processing,Anhui University,Hefei Anhui230031,China)

with the rapid development of internet and big data,it becomes a hotspot to select appropriate ones from substantial web services and composite them to meet users’requirements.So an improved chaotic particle swarm optimization algorithm(ICPSO)is presented and applied to web service composition optimization problem.As the traditional PSO is easy to fall into premature convergence and local optimum,chaotic mechanism is introduced to make the particle jump out of local optimum,thereby enhancing population diversity and improving the optimization capacity.Finally the feasibility and effectiveness of ICPSO are verified through simulation experiments.

service composition;improved chaotic particle swarm optimization algorithm;chaotic mechanism;QoS

TP311

A

1004-4329（2017）01-066-07

10.14096/j.cnki.cn34-1069/n/1004-4329（2017）01-066-07

2016-07-15

安徽省自然科學基金(1408085MF132)；大學生科研訓練計劃項目（KYXL2014060）資助。

張以文（1976-），男，博士，副教授，研究方向：服務計算、云計算。Email：yuji912@163.com。