楊麗琴，康國(guó)勝

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

1 概 述

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

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

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

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

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

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

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

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

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

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

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

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

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

3 gPSO-GODSS算法描述

3.1 MCOOP問(wèn)題描述

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

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

(1)

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

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

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

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

(2)

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

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

(3)

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

(4)

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

3.3 PSO算法

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

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

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

(7)

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

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

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

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

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

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進(jìn)化計(jì)算的基本思想，并將進(jìn)化控制在整數(shù)空間內(nèi)。需注意：兩式表示的是粒子在某一維的速度和位置變化。式8和式9使得PSO可應(yīng)用到離散的情形。收斂速度快是PSO的一個(gè)優(yōu)點(diǎn)，但若在起始階段過(guò)快，反而可能會(huì)收斂不到全局最優(yōu)解。為保證PSO不僅收斂速度快，且收斂到全局最優(yōu)解，文中基于梯度的思想進(jìn)行改進(jìn)，指導(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)用來(lái)平衡PSO和梯度，c3為一個(gè)給定的常數(shù)。將結(jié)合梯度信息的PSO稱為gPSO。文中根據(jù)xi，采用Sigmoid函數(shù)來(lái)定義，如式13所示，函數(shù)圖像如圖3所示。

(13)

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

圖3 Sigmoid函數(shù)圖像

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

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

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

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

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

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

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

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

Step8：t=t+1；

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

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

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

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

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

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

首先，比較每一代種群的平均適應(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í)行時(shí)間和PSO-GODSS的執(zhí)行時(shí)間非常相近。但由圖5可知，gPSO-GODSS的收斂速度較快，找到最優(yōu)解時(shí)的迭代次數(shù)更少，故達(dá)到收斂的時(shí)間開銷會(huì)更短。因此，從收斂的執(zhí)行效率上說(shuō)明了gPSO-GODSS更具可行性。

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

5 結(jié)束語(yǔ)

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