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

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

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

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

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

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

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

服務組合；ICPSO算法；混沌機制；服務質量

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

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

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

1 相關工作

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

2 組合服務模型描述

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

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

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

定義4組合服務（CS）是由候選服務集中服務依據服務模型，形成的一個具體的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是組合服務評價函數。

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

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

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

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

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

3 標準PSO算法

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

PSO具體算法具體實現步驟描述如下：

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

Step 2根據適應度函數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根據公式（3）和（4）更新粒子的位置和速度。

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

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

4.1 混沌機制及其特性

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

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

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

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

4.2 算法改進策略

4.2.1 混沌初始化種群

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

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

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

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

4.2.2 早熟收斂處理機制

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

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

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

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

4.3 ICPSO算法描述

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

ICPSO算法具體實現描述如下：

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

輸出：最優組合服務

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

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

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

找出種群中全局最優粒子下標gi，更新粒子群全局最優解

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

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

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

Step 13：結束。

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

5 實驗設計與結果分析

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

表1 隨機數據集QoS屬性取值范圍

5.1 可行性

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

圖1 不同算法的尋優性能

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

5.2 穩定性

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

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

圖2 不同算法的穩定性

6 結束語

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

[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服務動態選擇[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]范小芹，蔣昌俊，方賢文，等.基于離散微粒群算法的動態Web服務選擇[J].計算機研究與發展，2010，47（1）：147-156．

[11]胡旺，李志蜀.一種更簡化而高效的粒子群優化算法[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。