楊麗琴，康國勝

(1.上海中醫(yī)藥大學(xué) 計算機綜合教研室，上海 201203;2.復(fù)旦大學(xué) 計算機科學(xué)技術(shù)學(xué)院，上海 201203)

1 概 述

隨著服務(wù)計算技術(shù)的迅猛發(fā)展，互聯(lián)網(wǎng)上的可用服務(wù)的數(shù)量迅速增長。然而，單個Web服務(wù)提供的功能往往比較單一，為了實現(xiàn)更復(fù)雜的功能，需要將共享的多個Web服務(wù)組合成為用戶所需要的復(fù)雜服務(wù)，滿足用戶定制化的需求。因此，Web服務(wù)組合優(yōu)化問題成為服務(wù)計算研究的一個挑戰(zhàn)。

支持QoS的Web服務(wù)選擇主要分為三大類。第一類，研究單個服務(wù)請求的Web服務(wù)優(yōu)化選擇[1-3]；第二類，研究面向多個相同或相似功能服務(wù)請求的全局優(yōu)化Web服務(wù)選擇[4-5]；第三類，研究組合服務(wù)中動態(tài)Web服務(wù)優(yōu)化選擇[6-7]。文中主要考慮第三類情形。通常，對一個復(fù)雜的功能，會建立一個業(yè)務(wù)流程來實現(xiàn)，該業(yè)務(wù)按一定的流程結(jié)構(gòu)組成，每個流程節(jié)點通過調(diào)用服務(wù)來完成，最終整個流程就形成了一個組合服務(wù)。然而，互聯(lián)網(wǎng)環(huán)境復(fù)雜多變，帶來Web服務(wù)質(zhì)量的動態(tài)變化。即使Web服務(wù)的功能相同或相似，但是它們的服務(wù)質(zhì)量(quality of service，QoS)參數(shù)(如執(zhí)行費用、信譽等級、執(zhí)行時間等)可能不同。而且，同一服務(wù)在不同的時間點服務(wù)質(zhì)量也可能不同。因此，如何從滿足各節(jié)點功能需求的服務(wù)中選出最終的服務(wù)，形成一個組合服務(wù)來完成用戶的定制化需求成為一個難題，該問題文中稱為動態(tài)Web服務(wù)選擇。尤其是在當(dāng)前大數(shù)據(jù)、云計算環(huán)境下，服務(wù)選擇問題顯得尤為嚴(yán)峻。

目前，關(guān)于組合服務(wù)中的動態(tài)Web服務(wù)選擇的研究大多是基于QoS局部最優(yōu)的原則[8]，即獨立地為流程中的每個節(jié)點選擇一個滿足業(yè)務(wù)功能且服務(wù)的綜合服務(wù)質(zhì)量最優(yōu)的服務(wù)。這種方法沒有考慮單個服務(wù)節(jié)點質(zhì)量對組合服務(wù)中的其他節(jié)點質(zhì)量的影響，即考慮了滿足局部約束但沒考慮滿足全局約束，因此無法解決多目標(biāo)多約束的QoS全局優(yōu)化問題。比如：對一部分服務(wù)質(zhì)量需要滿足約束條件即可，而對另一些服務(wù)質(zhì)量需要盡量優(yōu)化。一個具體的例子如下：在對組合流程中的費用和執(zhí)行時間做約束的條件下使得可靠性和信譽等級最高。針對組合服務(wù)中的QoS全局最優(yōu)Web服務(wù)選擇問題，目前已有一些相關(guān)工作[9-12]，但均具有以下缺點：集中在解決局部優(yōu)化問題以及單目標(biāo)問題，無法解決多目標(biāo)的優(yōu)化問題；只提供單個的優(yōu)化方案，用戶無法從多個優(yōu)化方案中進行選擇；計算量大、算法復(fù)雜度高，隨著流程中業(yè)務(wù)節(jié)點以及節(jié)點對應(yīng)的候選服務(wù)的增多，組合優(yōu)化問題的求解效率將大大降低。因此，使用啟發(fā)式算法來提高Web服務(wù)組合優(yōu)化問題的求解是一個可行方案。針對以上服務(wù)組合優(yōu)化選擇算法的缺點，文獻[13]基于多目標(biāo)遺傳算法提出了一種動態(tài)選擇QoS全局最優(yōu)化算法。首先將服務(wù)動態(tài)組合優(yōu)化建模為一個帶QoS約束的多目標(biāo)優(yōu)化問題；然后，采用遺傳算法啟發(fā)式原理求解多目標(biāo)優(yōu)化問題；最后，產(chǎn)生一組滿足約束的Pareto優(yōu)化服務(wù)組合方案。這種啟發(fā)式算法解決了多目標(biāo)優(yōu)化求解的問題，然而算法的執(zhí)行效率還需要改進?；诹Ｗ尤簝?yōu)化算法，文獻[6]出了解決動態(tài)Web服務(wù)優(yōu)化選擇問題的算法PSO-GODSS，該算法不僅解決了前述的3個問題，并改進了動態(tài)Web服務(wù)選擇的執(zhí)行效率。實驗結(jié)果證明相比遺傳算法，PSO-GODSS算法的執(zhí)行效率和收斂速度均較優(yōu)，但依然還有待提高。尤其在當(dāng)前的大數(shù)據(jù)環(huán)境下，Web服務(wù)的規(guī)模非常龐大，算法的求解效率顯得尤為重要。

在文獻[6]的基礎(chǔ)上，針對多目標(biāo)多約束服務(wù)組合優(yōu)化問題，文中引入梯度的方法改進傳統(tǒng)的粒子群算法，提出了解決該問題的改進算法gPSO-GODSS(gradient PSO-GODSS)。相對于文獻[6]中的PSO-GODSS算法，該算法收斂速度更快，能夠快速找到全局最佳服務(wù)組合決策。

2 服務(wù)組合優(yōu)化問題

定義(多約束多目標(biāo)的優(yōu)化路徑，即MCOOP)[6]：對于圖G=(N,E,W)，其中N為頂點集，E為鏈路集，W為鏈路權(quán)重，設(shè)存在k(k≥2)個約束Ci(i=1,2,…,k)，從源點S到目的點T的全部路徑稱之為解空間的集合Ω，對?P∈Ω，具有m(m≥2)個非負(fù)的性能度量指標(biāo)f1,f2,…,fm，若P*∈Ω，?P∈Ω(P≠P*)，在P和P*均滿足約束Ci的條件下，對于所有的度量準(zhǔn)則均使得fi(P*)?fi(P)，至少存在一個嚴(yán)格不等式fi(P*)?fi(P)(i=1,2,…,m)成立，則稱P*為多約束條件下多目標(biāo)問題的Pareto優(yōu)化解。其中?和?是兩個偏序關(guān)系，分別表示不劣于和優(yōu)于關(guān)系。

服務(wù)節(jié)點(service node，SN)是一個抽象概念，各服務(wù)節(jié)點只包含對Web服務(wù)的功能描述和接口信息，不綁定具體的Web服務(wù)。服務(wù)組合按照流程模型的方式來建模，由多個業(yè)務(wù)或服務(wù)節(jié)點按照一定的順序結(jié)構(gòu)組成，每個服務(wù)節(jié)點對應(yīng)一個Web服務(wù)群(service group，SG)。同一服務(wù)群中的多個Web服務(wù)具有相同或相似的功能，而QoS不盡相同。一個包含n個服務(wù)節(jié)點的串行結(jié)構(gòu)服務(wù)組合流程模型如圖1所示。圖中，第i個服務(wù)節(jié)點SNi含有ni個服務(wù)，每個業(yè)務(wù)節(jié)點對應(yīng)一組具有相同或相似功能的候選Web服務(wù)，稱之為一個服務(wù)群，將其表示為SGi=(Si,1,Si,2,…,Si,ni)(i=1,2,…,n) 。

圖1 串行服務(wù)組合流程

基于動態(tài)Web服務(wù)選擇的組合服務(wù)QoS全局優(yōu)化問題，即在業(yè)務(wù)流程的執(zhí)行過程中，在各業(yè)務(wù)節(jié)點對應(yīng)的候選服務(wù)集合中分別選擇針對全局是優(yōu)化的服務(wù)實例，使得整個流程可以執(zhí)行完成，實現(xiàn)整體的業(yè)務(wù)流程功能，同時滿足組合服務(wù)流程的全局服務(wù)質(zhì)量約束，使得多目標(biāo)達(dá)到最優(yōu)。然而，該問題的求解是一個挑戰(zhàn)。

結(jié)合前面介紹的MCOOP問題，可把Web服務(wù)組合中的動態(tài)服務(wù)選擇QoS全局優(yōu)化問題進行轉(zhuǎn)化，將其建模為一個求解服務(wù)組合流程圖中帶QoS條件約束的多目標(biāo)優(yōu)化路徑問題，從而解決服務(wù)組合優(yōu)化問題。每個服務(wù)節(jié)點所對應(yīng)的服務(wù)群中的服務(wù)對應(yīng)圖中的頂點。為方便分析，在圖中添加兩個虛節(jié)點S和T，則圖1對應(yīng)的串行服務(wù)組合流程如圖2所示。

圖2 服務(wù)組合流程(串行結(jié)構(gòu))

文中將提出求解動態(tài)Web服務(wù)選擇QoS全局優(yōu)化問題的gPSO-GODSS算法。如前所述，服務(wù)組合流程常建模為一個基于Web服務(wù)的業(yè)務(wù)流程。業(yè)務(wù)流程由不同的流程結(jié)構(gòu)組成，常用的流程結(jié)構(gòu)主要有如下四大類型：串聯(lián)模式、并聯(lián)模式、選擇模式和循環(huán)模式。大多數(shù)服務(wù)組合流程均可由這四種基本模型組合而成。針對這四種基本模型的組合服務(wù)QoS參數(shù)計算方法，已有一些相關(guān)工作[14-15]。為了計算組合服務(wù)在各維度的綜合質(zhì)量，文中對四種基本模式的QoS進行聚合[6]。下面，以執(zhí)行時間T、執(zhí)行費用C、信譽等級Rep和可靠性R四種服務(wù)質(zhì)量為例介紹其聚合方法。在組合服務(wù)CS中，Si為執(zhí)行組合服務(wù)中滿足單個業(yè)務(wù)節(jié)點功能的具體服務(wù)，Si和CS的QoS服務(wù)質(zhì)量分別建模表示為Q(Si)=(Ti,Ci,Repi,Ri)、Q(cs)=(Tcs,Ccs,Repcs,Rcs)，四種基本模式的QoS參數(shù)聚合方法如表1所示。其中，設(shè)選擇模式中的第i個分支被選擇的概率為αi，循環(huán)模式中的循環(huán)次數(shù)為k。

表1 四種基本模式的QoS參數(shù)計算方法

3 gPSO-GODSS算法描述

3.1 MCOOP問題描述

在MCOOP問題中，將信譽等級Rep和可靠性R兩個質(zhì)量屬性作為約束，要求其值大于一定的值；目標(biāo)則是使組合服務(wù)的執(zhí)行費用C(P)和執(zhí)行時間T(P)最小化。因此，該問題可形式化為：

minf(P)={[T(P),C(P)]}

(1)

其中，T(P)、C(P)、Rep(P)和R(P)分別表示服務(wù)組合流程的QoS聚合公式，根據(jù)第1節(jié)表1中的QoS聚合方法計算。

式1表示使T(P)和C(P)兩個目標(biāo)函數(shù)同時最小化。在實際場景中，QoS屬性的個數(shù)可能多于4種，可根據(jù)具體的場景選擇合適的QoS參數(shù)作為優(yōu)化模型的目標(biāo)屬性和約束屬性。因此，文中的MCOOP模型具有可擴展性。

3.2 MCOOP問題轉(zhuǎn)化為單目標(biāo)問題

在解空間中尋找多目標(biāo)的優(yōu)化解，需要有一個評價機制來評估可行解的好壞。文中使用歐氏距離來構(gòu)造評價函數(shù)。首先分別求解單目標(biāo)的解，將其作為理想點，然后計算可行解對應(yīng)的組合服務(wù)的綜合執(zhí)行時間和執(zhí)行費用到理想點的歐氏距離作為評價可行解的適應(yīng)值函數(shù)，這樣便將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題。最后，利用單目標(biāo)的求解方法求出最優(yōu)解，并把這些最優(yōu)解作為多目標(biāo)的最優(yōu)解。構(gòu)造的MCOOP問題的評價函數(shù)如下：

(2)

其中，(T*,C*)為一個理想點。由此可知，N個目標(biāo)就對應(yīng)一個由N維向量表示的理想點。文中的理想點(T*,C*)是對T(P)和C(P)在各約束條件下分別求出的單目標(biāo)最優(yōu)值，它們的計算方法如下：

T*=min{T(P)|Rep(P)≥Rep0,R(P)≥R0}

(3)

C*=min{C(P)|Rep(P)≥Rep0,R(P)≥R0}

(4)

為了求解理想點，根據(jù)組合服務(wù)QoS屬性的聚合計算方法可得，在各候選服務(wù)集合中均選擇執(zhí)行時間最短的服務(wù)形成的組合服務(wù)的綜合執(zhí)行時間為T*；在各候選服務(wù)集合中均選擇執(zhí)行費用最低的服務(wù)形成的組合服務(wù)的綜合執(zhí)行費用為C*，從而得到組合服務(wù)的綜合執(zhí)行時間和執(zhí)行費用的理想值。

3.3 PSO算法

粒子群優(yōu)化算法(PSO)是一種進化計算技術(shù)，由Russel Eberhart和James Kennedy于1995年提出，源于對鳥群捕食的行為研究[16]。算法最初受飛鳥和魚類等集群活動規(guī)律的啟發(fā)，模擬種群間個體協(xié)作來搜索問題的最優(yōu)解。該算法的優(yōu)勢是易于實現(xiàn)同時又有深刻的智能背景，既適合科學(xué)研究，又適合工程應(yīng)用，且沒有許多參數(shù)的調(diào)節(jié)。關(guān)于PSO的更多詳情可參考文獻[17-18]。MCOOP問題是一個NP難問題[17]，因此使用智能進化算法求解是一個合適的選擇。PSO算法作為一種啟發(fā)式的智能優(yōu)化方法，具有群體尋優(yōu)、并行計算等特點。因此，可用于各種NP難問題的近似求解。

PSO算法的初始種群為一群隨機粒子，在每一次迭代中粒子通過跟蹤局部“極值”和全局“極值”(gbest和pbesti)來更新粒子的速度和位置，其迭代公式如下：

νi(t+1)=wvi(t)+c1r1(pbesti-xi(t))+c2r2(gbest-xi(t))

(5)

xi(t+1)=xi(t)+vi(t+1)

(6)

其中,r1和r2是(0,1)之間的隨機數(shù)；c1和c2是兩個學(xué)習(xí)因子，分別表示將每個微粒向局部最佳位置和全局最佳位置移動的統(tǒng)計加速項的權(quán)重。式5的第一項為記憶項，第二項為自身認(rèn)知項，第三項為群體認(rèn)知項。為了使粒子維持一定的慣性，在原來速度基礎(chǔ)上乘以一個慣性權(quán)重因子w，使粒子既能有原來的運動趨勢又能探索新的區(qū)域。w值越大，全局尋優(yōu)能力越強，局部尋優(yōu)能力越弱；w值越小，則反之。w采用較多的是線性遞減權(quán)值策略進行設(shè)置，其公式如下：

(7)

其中，wmax和wmin的經(jīng)典取值應(yīng)為：wmax=0.9，wmin=0.4。

在每一維，粒子都有一個最大的限制速度vmax，決定當(dāng)前位置與最好位置之間區(qū)域的分辨率(或精度)。當(dāng)粒子在某一維度的速度超過了最大限制速度vmax，則將其速度設(shè)定為最大的限制速度vmax。因為粒子運動速度過快，則單次迭代時越過的位移會比較大，從而容易越過極小值；相反，如果粒子的運動速度太慢，則單次迭代移動的位移太小，一方面可能越陷入局部極小值，另一方面可能導(dǎo)致長時間無法收斂。

3.4 gPSO-GODOSS算法設(shè)計

假設(shè)組合服務(wù)流程模型中有m個業(yè)務(wù)節(jié)點，第i個業(yè)務(wù)節(jié)點對應(yīng)ni個服務(wù)實例，即SGi=(Si1,Si2,…,Sini)。其中Sij為第i個業(yè)務(wù)節(jié)點對應(yīng)的某個服務(wù)實例的編號。第i個業(yè)務(wù)節(jié)點選擇的服務(wù)實例表示為xi=Sik，則最終的組合服務(wù)方案可形式化為一個m維的向量xi=(xi1,xi2,…,xim)，其中xik∈[1,nk]。

文中考察的速度、位移模型均是離散型數(shù)據(jù)，因此需要對xi的編碼進行離散化，改進原始粒子群算法中粒子的速度、位移模型，保證粒子在整數(shù)空間內(nèi)移動。具體改進的公式如下：

vid(t+1)=int(wvid(t))+?1+?2

(8)

xid(t+1)=xid(t)+vid(t+1)

(9)

其中，?1和?2為均勻分布的整數(shù)。?1∈[a1,b1]，p{?1}=1/m1,m1=?b1-a1+1」；?2∈[a2,b2]，p{?2}=1/m2,m2=?b2-a2+1」，其中

式8和式9反映了PSO進化計算的基本思想，并將進化控制在整數(shù)空間內(nèi)。需注意：兩式表示的是粒子在某一維的速度和位置變化。式8和式9使得PSO可應(yīng)用到離散的情形。收斂速度快是PSO的一個優(yōu)點，但若在起始階段過快，反而可能會收斂不到全局最優(yōu)解。為保證PSO不僅收斂速度快，且收斂到全局最優(yōu)解，文中基于梯度的思想進行改進，指導(dǎo)速度的變化。將粒子的變化速率作為梯度，定義如下：

(10)

將粒子xi在第d維的梯度記為?3，則

(11)

將梯度信息引入式8，可得：

vid(t+1)=int(wvid(t)+α(t)(?1+?2)+(1-α(t))c3?3)

(12)

式12中包含了梯度的信息，其中α(t)和1-α(t)用來平衡PSO和梯度，c3為一個給定的常數(shù)。將結(jié)合梯度信息的PSO稱為gPSO。文中根據(jù)xi，采用Sigmoid函數(shù)來定義，如式13所示，函數(shù)圖像如圖3所示。

(13)

由此可見，α(t)的值和xi相關(guān)。當(dāng)粒子的f(xi(t))越大時，α(t)越大，表示gPSO在一個大的解區(qū)域進行搜索；當(dāng)粒子的f(xi(t))越小時，α(t)越小，表示gPSO在一個小的解區(qū)域進行搜索，使得gPSO較早達(dá)到收斂，且不跳過最優(yōu)解。

圖3 Sigmoid函數(shù)圖像

基于前面的QoS屬性聚合方法和位置向量xi的編碼表示，以及基于梯度改進的速度、位移模型，結(jié)合基本PSO的智能進化思想，文中提出求解MCOOP問題的改進算法gPSO-GODOSS，具體的過程描述如下：

Step1：將多目標(biāo)問題向單目標(biāo)優(yōu)化問題轉(zhuǎn)化；

Step2：初始化所有粒子的速度和位置，并給出參數(shù)賦值；

Step3：根據(jù)粒子的位置解碼成對應(yīng)的服務(wù)組合方案，計算組合服務(wù)的綜合信譽等級和可靠性，判斷其是否滿足約束條件。若滿足，則按照評價函數(shù)計算該粒子的適應(yīng)值；否則，賦予該粒子一個最差的適應(yīng)值即可，并重新優(yōu)化；

Step4：計算粒子xi的局部最佳位置pbesti。具體方法如下：將其適應(yīng)值與其本身經(jīng)歷過的局部最佳位置pbesti的適應(yīng)值進行比較，若更優(yōu)，則將xi的值賦給pbesti；

Step5：計算粒子xi的全部最佳位置gbest。具體方法如下：將其適應(yīng)值與所有粒子經(jīng)歷過的全局最佳位置gbest的適應(yīng)值進行比較，若更優(yōu)，則將xi的值賦給gbest；

Step6：更新粒子的速度和位置，然后檢查新位置和速度的范圍，限制粒子的搜索范圍和最大速度；

Step7：循環(huán)計算所有粒子，即重復(fù)Step3～Step6；

Step8：t=t+1；

Step9：判斷是否滿足終止條件。若不滿足，則返回Step3。

gPSO-GODOSS的時間復(fù)雜度為O(mN2T)，其中T為迭代次數(shù)，N為粒子群規(guī)模，m為抽象服務(wù)數(shù)。

4 實驗結(jié)果與分析

針對文獻[6]中提出的組合服務(wù)流程例子進行比較實驗，其中計算機配置為Pentium D 3 400 MHz處理器，4 G內(nèi)存，Windows 7操作系統(tǒng)，算法用Matlab7.0實現(xiàn)。仿真實驗的流程如圖4所示。

圖4 服務(wù)組合流程

圖4中各服務(wù)節(jié)點對應(yīng)一個候選服務(wù)集合，每個候選服務(wù)集合中的服務(wù)實例的QoS各屬性值隨機生成，并采用極大極小方法標(biāo)準(zhǔn)化。根據(jù)第2節(jié)中服務(wù)組合流程基本模式及QoS聚合方法，構(gòu)造適應(yīng)值函數(shù)和約束條件。實驗中設(shè)Rep0=0.8，R0=0.5。其他參數(shù)設(shè)置如下：c1=c2=2，c3=0.05，itermax=100，w按式7進行計算。實驗中的候選服務(wù)集合的服務(wù)數(shù)量規(guī)模為10，迭代次數(shù)分別為100、200、300、400。文中根據(jù)執(zhí)行時間和收斂速度來評價gPSO-GODSS算法的可行性和有效性，與文獻[6]中的多目標(biāo)粒子群算法PSO-GODSS的執(zhí)行結(jié)果進行對比及分析。

首先，比較每一代種群的平均適應(yīng)值。如圖5所示，PSO-GODSS在第63代收斂到最優(yōu)值，而gPSO-GODSS在第34代已收斂到最優(yōu)值，表明gPSO-GODSS的收斂速度優(yōu)于PSO-GODSS的收斂速度。因此，從收斂速度上看，gPSO-GODSS優(yōu)于PSO-GODSS。

圖5 算法收斂速度的比較

下面比較算法收斂的執(zhí)行效率，如圖6所示。在相同迭代次數(shù)下，gPSO-GODSS的執(zhí)行時間和PSO-GODSS的執(zhí)行時間非常相近。但由圖5可知，gPSO-GODSS的收斂速度較快，找到最優(yōu)解時的迭代次數(shù)更少，故達(dá)到收斂的時間開銷會更短。因此，從收斂的執(zhí)行效率上說明了gPSO-GODSS更具可行性。

圖6 算法執(zhí)行時間比較

5 結(jié)束語

針對組合服務(wù)流程中QoS全局最優(yōu)動態(tài)Web服務(wù)選擇問題，基于粒子群算法及梯度下降的思想，提出了求解該問題的gPSO-GODSS改進算法。利用粒子群算法的智能優(yōu)化原理進行優(yōu)化，通過在PSO的速度更新公式中引入梯度的方法，不僅保證算法快速收斂且收斂到全局最優(yōu)解。實驗結(jié)果證明了gPSO-GODSS算法的可行性和有效性，且算法收斂的執(zhí)行效率和收斂速度均優(yōu)于傳統(tǒng)的離散粒子群算法。