基于量子粒子群優化算法的Web服務組合問題

王創偉，湯克明

(鹽城師范學院信息科學與技術學院，江蘇鹽城 224002)

基于量子粒子群優化算法的Web服務組合問題

王創偉，湯克明

(鹽城師范學院信息科學與技術學院，江蘇鹽城 224002)

使用量子粒子群優化算法(QPSO)，將可能的Web服務工作流執行路徑看作粒子，按照QPSO算法進行進化，從而解決了基于服務質量(Quality of Service，QoS)約束的Web服務組合問題，此為解決Web服務組合問題提出了一種新的思路.實驗表明，使用QPSO算法求解復雜Web服務組合問題在組合時間上具有一定的優越性.

Web服務組合問題；量子粒子群優化算法；服務質量

0 引 言

隨著Web服務技術的日益成熟，Web服務已經成為下一代分布式處理系統的核心，越來越多的穩定易用的Web服務共享在網絡上.但單個Web服務提供的功能有限，不能適應開放的、動態的Web環境，為了更加充分地利用共享的Web服務，有必要將共享的Web服務組合起來，提供更為強大的服務功能，從而加快系統開發的速度，滿足用戶的需求.如何從眾多服務中選擇子服務，組成符合用戶要求的復雜的服務組合?目前，該問題是Web服務應用集成的核心問題[1-5].對此，本研究采用智能優化算法—量子粒子群優化(Quantum-behavior Particle Swarm Optimization，QPSO)算法，提出對該問題的解決思路和方法，給出了求解過程，并與其他算法進行比較.實驗表明，采用QPSO算法求解此類問題具有一定的優越性.

1 Web服務組合問題模型

圖1 服務組合(CS)問題模型

設有一服務組合CS[4]，其由m個服務類組成(見圖 1)，表示為，CS={SC1，SC2，…，SCm}，其中，SCi表示組成服務組合的第i個服務類(1≤i≤m)，而SCi={ES1，ES2，…，ESj}，其中，j≥1，即每個服務類又由j個候選的原子服務構成.該服務組合問題模型可以進一步細化為如圖2所示模型.

圖2 服務組合問題細化模型

假設一個合成服務由m個服務類組成，每個服務類有n個具有候選關系的原子服務，現要從每個服務類中選擇一個原子服務，則會產生nm個可選方案，如何從這些方案中選擇，以使合成服務滿足用戶的需求?對此，本研究利用QPSO算法的原理，尋求Web服務組合中最優解，從而得到構成服務組合的最佳原子服務.

2 量子粒子群優化算法(QPSO)

2004年，Sun等[2]提出QPSO算法，該算法是對整個PSO算法進化搜索策略的改變，進化方程不需要速度向量，而且進化方程的形式更簡單，參數更少且更容易控制.

QPSO算法利用波函數 Ψ(x，t)來描述粒子的狀態，并通過求解薛定諤方程得到粒子在空間某一點出現的概率密度函數，再通過Monte-Carlo隨機模擬得到粒子的位置方程為，

式中，u為在[0，1]上服從均勻分布的隨機數.

在此基礎上，本研究在粒子群中引入一個全局點mbest來計算粒子的下一迭代步的變量L，它定義為所有粒子的個體最好位置的平均值，其計算公式為，

式中，M為種群中粒子的數目，Pi為粒子i的個體最好位置.

則，L的值可由下式確定，

為了保證算法的收斂性，每一個粒子必須收斂于各自的p點，p=(p1，p2，…，pD)，第i個粒子的p點的第d維坐標為，

式中，φ是在[0，1]上均勻分布的隨機數，D為粒子的維數，Pi和Pg分別表示粒子i的個體最好位置和種群的全局最好位置.

最后，得到QPSO算法的進化方程為，

式中，β稱為收縮擴張系數，是QPSO算法唯一的參數，一般取，

QPSO算法具體描述如下:

3 QPSO算法求解服務組合問題思路

基于QPSO算法求解Web服務組合問題的基本思路是:首先，產生一定數目的粒子群，每一個服務組合路徑編碼為一個粒子；然后，每一個粒子依據自身信息、局部較優信息(pbest)和全局較優信息(gbest)，產生具有更高目標準則值的新粒子，這一過程循環進行，在解空間中進行全局搜索；最后，算法停止時，得到一組粒子集合，即獲得較優路徑的組合集.

算法具體流程描述如下:

①初始化種群，根據調度規則設定各粒子的隨機位置，并初始化Pi和Pg；

②根據當前迭代次數動態調整收縮擴張系數，從而實現算法搜索空間由全局逐步過渡到局部；

③計算每一粒子的適應度值，并確定是否更新Pi和Pg；

④按種群的進化方程生成新的粒子；

⑤判斷是否滿足算法的終止條件，若滿足則轉到步驟⑥，不滿足則轉到步驟②；

⑥輸出構成服務組合的最佳原子服務ID，算法結束.

4 編碼方案與實驗分析

4.1 編碼方案

編碼方案的具體步驟為:

1)定義m個粒子，代表m種可能的服務組合路徑.本方案采用一個3維數組Particle[i][j，k]表示每一個進化后的當前粒子所選擇的服務和其QoS屬性值，其中，i代表第i個粒子(0≤i≤m-1)，j代表可執行路徑上第j個服務，k代表第k維QoS屬性，當k=0時，代表第j個任務當前所選擇的服務.

2)通過服務名稱發現所有可選擇的服務并讀取每個服務的QoS值.從各個服務類的候選服務中隨機選擇一個服務，完成對用戶提出請求的Web服務組合的初始化.

3)依據服務質量的量化方法，計算出當前粒子(組合路徑)的QoS值，并把當前路徑作為局部最優路徑，再在整個解空間獲得QoS最大的服務組合，并把該路徑作為全局最優路徑，完成最優粒子初始化.

4)對每個粒子進行進化，即對構成服務組合的路徑進行更新.依據用戶自定義的QoS約束條件和進化次數，進行循環.循環結束后，便得到全局最優組合路徑.

4.2 實驗結果與分析

在實驗時，分別考慮服務類數量為10，每類服務中分別具有10、15、20個功能相同、服務質量不同的候選服務，也就是粒子服務群規模分別為100、150和200，迭代次數分別取 200、300、400、500和 600的情況下CPU的時間開銷，并對于每一種情況，算法分別運行15次求其平均值，結果如圖3所示.

圖3 算法的執行時間比較

由圖3可以看出，隨著服務實例數目的增加，在不同的迭代次數下，CPU運行時間并沒有大量增加.

同時，本實驗采用線性規劃算法、PSO算法和QPSO算法，分別對它們取得最優服務組合時所需要時間進行分析，結果如圖4所示.

圖4 不同算法執行時間的比較

由圖4可看出，采用QPSO算法對求解規模較大的服務組合問題在計算時間上具有較大的優越性.

5 結 語

在Web服務技術日益發展的今天，為了滿足用戶對復雜Web服務請求的需求，就需要把多個原子服務組合起來實現更強大的服務功能.而在服務類中如何選擇原子服務并把它們組合起來就成為解決該問題的關鍵.QPSO算法作為一種新興的模擬進化算法，具有群體協作、正反饋和分布式并行計算等特點，在空間復雜度上與傳統的算法相比具有較大的優越性.利用QPSO算法來解決Web服務組合問題有一定的理論參考價值和實際意義.

:

[1]陳彥萍，李增智.Web服務組合中基于服務質量的服務選擇算法[J].西安交通大學學報，2006，40(8):897-900.

[2]Sun J，Feng B，XuW B.ParticleSwarmOptimization withParticles Having Quantum Behavior[C]//Proceedings of2004Congresson Evolutionary Computation.New York:IEEE Conference Publications，2004:325-331.

[3]王創偉，錢雪忠.蟻群算法在Web服務組合問題中的應用研究[J].計算機工程與設計，2007，28(24):5912-591.

[4]劉書雷，劉云翔，張帆，等.一種服務聚合中QoS全局最優服務動態選擇算法[J].軟件學報，2007，18(3):646-656.

[5]Zeng L ，Benatallah B ，Ngu A HH ，et al.QoS-awareMiddle ware for Web ServicesComposition[J].IEEE Transactions on Software Engineering，2004，30(5):311-327.

Quantum-behavior Particle Swarm Optimization Algorithm for Solving Problem of Web Service Composition

WANGChuangwei，TANGKeming

(College of Information Science and Technology，Yancheng Teachers University，Yancheng 224002，China)

QPSO(Quantum-behavior Particle Swarm Optimization)algorithm was attempted to solve the problem of web services composition in this paper，which took web services workflow path as particles and was optimized according to QPSO algorithm，so as to solve the problems of web services composition based on QoS constraints.The experimental results indicate that QPSO algorithm for solving complex composition problems has some advantage at composition time.

web services composition problem ；quantum-behavior particle swarm optimization ；QoS

TP301.6；TP393.0

A

1004-5422(2012)04-0354-03

2012-09-12.

王創偉(1974—)，男，碩士，副教授，從事計算機Web服務技術研究.