基于量子粒子群優(yōu)化算法的Web服務(wù)組合問題

王創(chuàng)偉，湯克明

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

基于量子粒子群優(yōu)化算法的Web服務(wù)組合問題

王創(chuàng)偉，湯克明

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

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

Web服務(wù)組合問題；量子粒子群優(yōu)化算法；服務(wù)質(zhì)量

0 引 言

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

1 Web服務(wù)組合問題模型

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

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

圖2 服務(wù)組合問題細(xì)化模型

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

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

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

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

式中，u為在[0，1]上服從均勻分布的隨機(jī)數(shù).

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

式中，M為種群中粒子的數(shù)目，Pi為粒子i的個(gè)體最好位置.

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

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

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

最后，得到QPSO算法的進(jìn)化方程為，

式中，β稱為收縮擴(kuò)張系數(shù)，是QPSO算法唯一的參數(shù)，一般取，

QPSO算法具體描述如下:

3 QPSO算法求解服務(wù)組合問題思路

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

算法具體流程描述如下:

①初始化種群，根據(jù)調(diào)度規(guī)則設(shè)定各粒子的隨機(jī)位置，并初始化Pi和Pg；

②根據(jù)當(dāng)前迭代次數(shù)動(dòng)態(tài)調(diào)整收縮擴(kuò)張系數(shù)，從而實(shí)現(xiàn)算法搜索空間由全局逐步過渡到局部；

③計(jì)算每一粒子的適應(yīng)度值，并確定是否更新Pi和Pg；

④按種群的進(jìn)化方程生成新的粒子；

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

⑥輸出構(gòu)成服務(wù)組合的最佳原子服務(wù)ID，算法結(jié)束.

4 編碼方案與實(shí)驗(yàn)分析

4.1 編碼方案

編碼方案的具體步驟為:

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

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

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

4)對每個(gè)粒子進(jìn)行進(jìn)化，即對構(gòu)成服務(wù)組合的路徑進(jìn)行更新.依據(jù)用戶自定義的QoS約束條件和進(jìn)化次數(shù)，進(jìn)行循環(huán).循環(huán)結(jié)束后，便得到全局最優(yōu)組合路徑.

4.2 實(shí)驗(yàn)結(jié)果與分析

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

圖3 算法的執(zhí)行時(shí)間比較

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

同時(shí)，本實(shí)驗(yàn)采用線性規(guī)劃算法、PSO算法和QPSO算法，分別對它們?nèi)〉米顑?yōu)服務(wù)組合時(shí)所需要時(shí)間進(jìn)行分析，結(jié)果如圖4所示.

圖4 不同算法執(zhí)行時(shí)間的比較

由圖4可看出，采用QPSO算法對求解規(guī)模較大的服務(wù)組合問題在計(jì)算時(shí)間上具有較大的優(yōu)越性.

5 結(jié) 語

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

:

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

[2]Sun J，F(xiàn)eng B，XuW B.ParticleSwarmOptimization withParticles Having Quantum Behavior[C]//Proceedings of2004Congresson Evolutionary Computation.New York:IEEE Conference Publications，2004:325-331.

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

[4]劉書雷，劉云翔，張帆，等.一種服務(wù)聚合中QoS全局最優(yōu)服務(wù)動(dòng)態(tài)選擇算法[J].軟件學(xué)報(bào)，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.

王創(chuàng)偉(1974—)，男，碩士，副教授，從事計(jì)算機(jī)Web服務(wù)技術(shù)研究.