基于改進(jìn)PSO用戶習(xí)慣感知的服務(wù)組合

趙 陽，郭 星

（安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230031）

基于改進(jìn)PSO用戶習(xí)慣感知的服務(wù)組合

趙 陽，郭 星*

（安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230031）

隨著Web服務(wù)數(shù)量的急劇增加，如何動態(tài)地從大量候選服務(wù)集中選擇出合適的Web服務(wù)，并組合成能夠完成復(fù)雜增值業(yè)務(wù)過程需求的組合服務(wù)，是服務(wù)組合優(yōu)化領(lǐng)域亟待解決的問題。本文提出了一種基于PSO的具有用戶習(xí)慣感知能力的優(yōu)化算法，并應(yīng)用于離散服務(wù)組合優(yōu)化問題。該算法通過對用戶習(xí)慣的感知進(jìn)行服務(wù)組合優(yōu)化，在傳統(tǒng)PSO算法的基礎(chǔ)上，根據(jù)粒子與用戶習(xí)慣的相似度來控制粒子收斂，使尋優(yōu)過程具有用戶習(xí)慣感知能力。大量實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法的可行性和有效性。

服務(wù)組合；PSO；用戶習(xí)慣感知；服務(wù)質(zhì)量

隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，出現(xiàn)了具有良好封閉性、松散耦合和高度可集成等特點(diǎn)的Web服務(wù)，越來越多的企業(yè)將技術(shù)、資源以及應(yīng)用加入到Web服務(wù)中。不過單獨(dú)的Web服務(wù)所能夠?qū)崿F(xiàn)的功能是有局限性的，而用戶提出的需求往往不能完全得到滿足，Web服務(wù)組合就是為了解決該類問題。Web服務(wù)組合是通過利用Web服務(wù)的松耦合特性以及高度可集成的能力，把原子服務(wù)無縫且快速靈活地組合在一起，形成新的新增服務(wù)，而新的組合服務(wù)可以滿足用戶的復(fù)雜需求，而原子服務(wù)是目前已經(jīng)存在的獨(dú)立的簡單的Web服務(wù)[1]。近年來Web服務(wù)的種類和數(shù)量越來越多，大量功能屬性相同的服務(wù)存在于網(wǎng)絡(luò)上，但是這些服務(wù)在非功能屬性即服務(wù)質(zhì)量（quality of ser-vice,QoS）上是不相同的。怎樣將多種類別的Web服務(wù)組合起來，形成一組新的服務(wù)組合，并且要高效的完成這一組合過程是一個(gè)新的研究熱點(diǎn)[2,3]。同時(shí)，如何在海量Web服務(wù)中，高效的選擇出合適的服務(wù)來滿足用戶需求也成為了一個(gè)迫切需要解決的問題。

倪晚成等[4]對Web服務(wù)組合的研究現(xiàn)狀進(jìn)行了綜述，對典型Web服務(wù)組合方法進(jìn)行了分類，對Web服務(wù)的評價(jià)模型進(jìn)行了論述。AgFlow[5]提出了五維QoS評價(jià)模型。李金忠、夏潔武和唐衛(wèi)東等[6]提到有關(guān)個(gè)性化的Web服務(wù)組合問題，必要的個(gè)性化組合可以滿足特定用戶的特定需求，而個(gè)性化的服務(wù)組合問題也是一個(gè)亟待解決。在服務(wù)組合選擇過程中，同時(shí)考慮用戶的偏好和服務(wù)的QoS屬性的Web服務(wù)組合算法仍然是以后研究的難點(diǎn)。而目前的服務(wù)組合算法大多從如何快速高效尋優(yōu)的角度出發(fā)來解決服務(wù)組合問題。

粒子群優(yōu)化算法（PSO）是當(dāng)前較為流行的應(yīng)用于基于QoS的Web服務(wù)組合問題上的智能算法，相比其他智能算法具有參數(shù)少和收斂快的特點(diǎn)。劉莉平等[7]提出一種基于粒子群算法的解決Web服務(wù)組合的算法，重新定義了粒子的位置、速度和運(yùn)算，利用粒子群算法的智能優(yōu)化原理快速得到一組優(yōu)化的服務(wù)組合，并證明了算法的可行性和有效性。文獻(xiàn)[8]提出一個(gè)改進(jìn)PSO算法，設(shè)計(jì)了一種新的慣性權(quán)重，在粒子搜索的不同階段采用不同的公式得到慣性權(quán)重，并且通過實(shí)驗(yàn)證明了該算法比基本粒子群算法有更好的收斂性。

常見Web組合算法都沒有考慮用戶偏好，本文從用戶習(xí)慣感知的角度出發(fā)，結(jié)合粒子群算法，提出一種能感知用戶習(xí)慣的Web服務(wù)組合算法，對于某一用戶，在已知某一組服務(wù)組合是其習(xí)慣使用組合的情況下，依據(jù)該用戶的這一習(xí)慣來進(jìn)行尋優(yōu)，從而解決用戶習(xí)慣感知的服務(wù)組合問題。

為解決此類用戶習(xí)慣感知的服務(wù)組合問題，必須在尋優(yōu)的同時(shí)感知用戶習(xí)慣。粒子群算法具有容易實(shí)現(xiàn)并且收斂速度快的特點(diǎn)，對于參數(shù)選擇已有較為成熟的理論，所以本文基于粒子群算法提出一種用戶感知的服務(wù)組合算法。

1 Web服務(wù)組合

為了清晰的描述本文的服務(wù)組合問題，此節(jié)給出在描述服務(wù)組合問題中涉及到的相關(guān)定義以及基于QoS的服務(wù)組合模型。

1.1 相關(guān)定義

定義1（服務(wù)類，S） 服務(wù)類是指一組具體服務(wù)的抽象，并且同一服務(wù)類的服務(wù)具有相同的功能，而不同具體服務(wù)之間具有非功能屬性上的差異。由滿足這些要求的多個(gè)服務(wù)組成的服務(wù)類是服務(wù)組合的基本組成單元。用此式子來抽象表示第i個(gè)服務(wù)類：，其中Si包含m個(gè)具體候選服務(wù)。

定義2（服務(wù)組合，CS） 服務(wù)組合是由多個(gè)服務(wù)組成的一組服務(wù)，這些服務(wù)是來自不同的服務(wù)類中的某一具體服務(wù)，將這一組服務(wù)稱為服務(wù)組合。可將其抽象表示為：CS={S1,…,Si,…,Sn} ，表示服務(wù)組合由來自n個(gè)服務(wù)類的服務(wù)組成。

1.2 基于QoS的服務(wù)組合問題模型

Web服務(wù)組合一般有4種基本結(jié)構(gòu)。因?yàn)槌樞蚰Ｐ屯獾牧硗?種模型都可以轉(zhuǎn)換為順序模型[9]，所以本文采用順序模型來研究服務(wù)組合的優(yōu)化問題。假設(shè)本文研究的Web服務(wù)有4個(gè)QoS參數(shù)，分別為響應(yīng)時(shí)間（T）、服務(wù)費(fèi)用（C）、可用性（A）、信譽(yù)（Rep）。各種流程的QoS計(jì)算模型如表1所示。

表1 服務(wù)組合QoS計(jì)算公式

對QoS的各項(xiàng)屬性，有的屬于正影響，值越高越符合用戶需求，而有的屬于負(fù)影響，值越小越符合用戶需求。另外，各項(xiàng)屬性的取值不是一個(gè)數(shù)量級。為解決這兩個(gè)問題，必須進(jìn)行分類和歸一化操作。本文按照如下公式進(jìn)行歸一化操作：

其中，和分別為Ti對應(yīng)的所有Si中QoS指標(biāo)最大值和最小值。按照各項(xiàng)屬性屬于成本型或效益型來選擇公式進(jìn)行轉(zhuǎn)換。組合服務(wù)的適應(yīng)度評價(jià)函數(shù)定義為：

其中qk為歸一化轉(zhuǎn)換的第k個(gè)QoS屬性值。wk為第k個(gè)屬性對應(yīng)的權(quán)值。

2 UHPPSO算法描述與模型

2.1 標(biāo)準(zhǔn)粒子群算法

粒子群優(yōu)化（particle swarm optimization,PSO）算法最早由 Eberhart和 Kennedy[10]共同提出。在基本粒子群算法中，每個(gè)個(gè)體成為一個(gè)“粒子”，代表一個(gè)潛在的解。每個(gè)粒子的飛行的方向和下一次的位移由該粒子的飛行速度所決定。對于整個(gè)粒子群，每次粒子都會依據(jù)該粒子的歷史最優(yōu)解pi和整個(gè)群體曾到達(dá)的歷史最優(yōu)解pk來進(jìn)行更新，與鳥群搜尋食物的過程十分相似。例如，如果搜索空間為n維，該空間的某一粒子i的位置xi=(x1，x2，x3…，xn)，速度vi=(v1，v2，…，vn)，歷史最優(yōu)解pi=(p1，p2，…，pn)，全局最優(yōu)解pg=(p1，p2，…，pn)，則i的速度和位置的更新公式為[10-13]：

其中t為當(dāng)前進(jìn)化次數(shù)，c1，c2被稱作學(xué)習(xí)因子，作用是決定pi，pg對新速度的影響能力，r1和r2為[0,1]區(qū)間上的均勻分布的隨機(jī)變量。Shi和Eberhar在1998年正式引入慣性權(quán)重的概念[11]。為了更好的控制算法全局的尋優(yōu)能力，在速度公式中引入一個(gè)慣性權(quán)重w，將式（3）變?yōu)椋?/p>

式（4）和式（5）合稱為標(biāo)準(zhǔn)粒子群算法（standard particle swarm optimization,SPSO）。有很多相關(guān)論文中提出慣性權(quán)重策略來改進(jìn)基本粒子群算法的性能,通過慣性權(quán)重的大小來控制算法的收斂速度。采用最多的是Shi提出的線性遞減慣性權(quán)重值[10]：

其中wmax，wmin分別為初始慣性權(quán)重的值和最終的慣性權(quán)重值，一般取wmax=0.9，wmin=0.4。

2.2 編碼方案

服務(wù)組合CS可抽象表示為CS=(S1,S2,…,Si,…,Sn)，S表示每個(gè)任務(wù)對應(yīng)的服務(wù)類，而粒子群算法中的每一個(gè)粒子的位置X=(x1,x2,…,xi…xn)，對應(yīng)一個(gè)服務(wù)組合，其速度決定飛行方向和下一步位移，由速度得到新的位置后，將對應(yīng)的服務(wù)組合通過公式（2）計(jì)算出該位置的適應(yīng)度。運(yùn)用粒子群算法進(jìn)行求解的基本思想如下：初始化一定數(shù)量的初始粒子，每個(gè)粒子表示一個(gè)可能的服務(wù)組合解。在粒子群的迭代過程中，粒子根據(jù)全局最優(yōu)解和粒子本身經(jīng)過的歷史最優(yōu)解進(jìn)行更新。

2.3 UHPPSO算法思想與模型

假設(shè)用戶曾經(jīng)選擇過的服務(wù)組合對應(yīng)的粒子為A=(a1,a1,…,ai,…,an)，將此粒子設(shè)置為比較粒子，用以感知用戶的習(xí)慣。在計(jì)算慣性權(quán)重大小時(shí)，考慮當(dāng)前粒子位置與比較粒子A的相似程度，得到對應(yīng)的慣性權(quán)重值，用以控制粒子收斂。

2.3.1 粒子間相似度

在給出新的慣性權(quán)重公式之前，先定義粒子間相似度的計(jì)算方法。

假設(shè)有兩個(gè)粒子：粒子P和粒子Q，其粒子間的相似度用Sim(P,Q)表示。每個(gè)組合對應(yīng)的組合服務(wù)可按表1計(jì)算出組合服務(wù)的QoS值，本文用一個(gè)四元組QoS=(Time,Cost,Avai,Rep)表示，粒子P、Q間的相似度用其對應(yīng)的服務(wù)組合QoS值間的4維歐幾里德距離表示[14]。4維空間的歐幾里德距離計(jì)算公式為：

其中x1，x2，x3，x4分別為P的四項(xiàng) QoS 屬性值，y1，y2，y3，y4分別為Q的四項(xiàng)QoS屬性值。P、Q間的歐幾里德距離越大，二者間的相似度越低。由此定義粒子間相似度的計(jì)算公式：

時(shí)，二者的各屬性完全相同，此時(shí)Sim(P,Q)=0.5。由于QoS經(jīng)過歸一化處理后的范圍是[0,1]，所以d的范圍是[0,2]，

時(shí)，Sim(P,Q)=0.25。所以P、Q二者間相似度的范圍是[0.25,0.5]。

2.3.2 用戶習(xí)慣感知的慣性權(quán)重策略

為了感知用戶習(xí)慣，本文提出的UHPPSO算法將粒子間相似度與傳統(tǒng)PSO算法中的慣性權(quán)重公式結(jié)合，速度更新時(shí)，使用如下改進(jìn)的慣性權(quán)重公式來進(jìn)行粒子的速度更新可以達(dá)到感知用戶習(xí)慣的目的。

用戶習(xí)慣感知的慣性權(quán)重策略在Shi提出的線性遞減慣性權(quán)重公式，即式(6)的基礎(chǔ)上加入相似度，使算法更趨向于收斂于與比較粒子A相似度更高的點(diǎn)，所對應(yīng)服務(wù)組合更符合用戶的習(xí)慣。為得到此效果，對式(6)做出如下改進(jìn)：

該式保留了慣性權(quán)重的線性遞減性質(zhì)的同時(shí)，引入了相似度，使得算法獲得了用戶習(xí)慣的感知能力。其中P為當(dāng)前粒子，A為比較粒子。二者間相似度越高，w值越小，算法收斂越快，反之收斂越慢。即算法更傾向產(chǎn)生和用戶習(xí)慣更相似的組合服務(wù)。

2.4 算法流程

基于上述思想和模型，本文改進(jìn)算法的歸納表述如下。

UHPPSO算法

Step 1：置當(dāng)前迭代次數(shù)t=0。初始化m個(gè)粒子的初始位置和速度；

Step 2：設(shè)定一個(gè)比較粒子A表示用戶曾經(jīng)選擇過的服務(wù)組合；

Step 4：初始化每個(gè)粒子的歷史最優(yōu)位置、歷史最優(yōu)適應(yīng)值。根據(jù)所有粒子的歷史最優(yōu)位置、歷史最優(yōu)適應(yīng)值，計(jì)算種群的全局最優(yōu)位置，全局最優(yōu)適應(yīng)值；

Step 5：由式(8)計(jì)算粒子每個(gè)粒子P與A的相似度Sim(P,A)；

Step 6：根據(jù)式(5)、(9)更新粒子速度及位置；

Step 7：計(jì)算出新的到的粒子的適應(yīng)度；

Step 8：對該粒子的歷史最優(yōu)位置和全局最優(yōu)位置進(jìn)行更新；

Step 9：判斷是否達(dá)到最大迭代次數(shù)，若達(dá)到則結(jié)束，否則轉(zhuǎn)至Step 5。

3 仿真實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

為了驗(yàn)證本文所提出的算法在服務(wù)組合應(yīng)用中的性能，本文進(jìn)行了大量的實(shí)驗(yàn)。由于其它幾類服務(wù)組合模型都可以轉(zhuǎn)換為順序模型，本文使用順序模型在QWS數(shù)據(jù)集上進(jìn)行了多次仿真實(shí)驗(yàn)。該數(shù)據(jù)集由Zeng等提供[5,15]，包含250 0個(gè)Web服務(wù)的QoS屬性。實(shí)驗(yàn)只取其中的服務(wù)的響應(yīng)時(shí)間、調(diào)用一次服務(wù)所需的花費(fèi)、服務(wù)的可用性以及服務(wù)的信譽(yù)四個(gè)評價(jià)指標(biāo)。

實(shí)驗(yàn)硬件環(huán)境為：Intel Core i5-4200U CPU，4.00 GB RAM。實(shí)驗(yàn)軟件環(huán)境為：Matlab 6.0，Windows7 64位操作系統(tǒng)。

3.2 實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)參數(shù)設(shè)定如表2所示，本文的實(shí)驗(yàn)結(jié)果為實(shí)驗(yàn)次數(shù)N=20時(shí)計(jì)算得到的平均實(shí)驗(yàn)數(shù)值。實(shí)驗(yàn)比較了標(biāo)準(zhǔn)粒子群算法與本文算法的以下各項(xiàng)性能。

表2 實(shí)驗(yàn)參數(shù)設(shè)定

3.3 可行性

為了驗(yàn)證本文算法的可行性，模擬2.3節(jié)的場景，在QWS數(shù)據(jù)集上進(jìn)行了相應(yīng)的實(shí)驗(yàn)。接下來將本文的UHPPSO算法與標(biāo)準(zhǔn)PSO算法進(jìn)行比較。將任務(wù)數(shù)分別固定為5,10,15,20時(shí)，增加候選服務(wù)的數(shù)量。實(shí)驗(yàn)結(jié)果如圖1所示。

根據(jù)適應(yīng)度評價(jià)函數(shù)，以及2.2節(jié)歸一化操作公式可知，所有指標(biāo)的數(shù)值均是越小越好，由此計(jì)算出的適應(yīng)度越低，表示解的質(zhì)量越好。所以，從圖1可看出，隨著候選服務(wù)數(shù)的增加，解的質(zhì)量越來越高，并且，通過比較各個(gè)子圖，在不同任務(wù)數(shù)下，子任務(wù)數(shù)越少，解的質(zhì)量越高。并且UHPPSO算法的解的質(zhì)量明顯高于PSO算法。可以看出，本文算法通過采用線性遞減的慣性權(quán)重和粒子間相似度的方法來控制粒子收斂，是可行的，并且增強(qiáng)了算法的尋優(yōu)能力。

圖1 算法在不同候選服務(wù)數(shù)下的尋優(yōu)性能對比

圖2 用戶習(xí)慣對結(jié)果的影響

3.4 用戶習(xí)慣的影響

文章開頭提出的服務(wù)組合應(yīng)用的情景下，為了驗(yàn)證本文算法在用戶習(xí)慣感知方面的優(yōu)越性，本文就算法的解的用戶感知情況將UHPPSO算法與PSO算法進(jìn)行了對比。用最終解與比較粒子的粒子間相似度來衡量其感知能力，在不同任務(wù)數(shù)下的實(shí)驗(yàn)結(jié)果如圖2所示。

由粒子相似度定義可知，解與比較粒子間的相似度越高，說明算法的用戶習(xí)慣感知能力越好。所以從圖2可以看出，UHPPSO算法尋得解的用戶習(xí)慣感知能力要明顯優(yōu)于PSO算法，驗(yàn)證了該算法的用戶感知能力。在考慮用戶的選擇習(xí)慣時(shí)，本文提出的算法在用戶習(xí)慣感知方面具有明顯的優(yōu)越性。通過圖2的各個(gè)子圖可以看出，這一性能在候選服務(wù)數(shù)少時(shí)更為明顯。隨著候選服務(wù)數(shù)的增加，其感知能力也會隨之下降。

以上實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的可行性以及算法對用戶習(xí)慣感知能力。本文算法在尋優(yōu)性能和用戶習(xí)慣感知能力上明顯的優(yōu)于PSO算法。本文提出的算法在提高解的質(zhì)量的同時(shí)，增加了用戶習(xí)慣的感知能力。

4 總結(jié)

本文從解決考慮用戶習(xí)慣的服務(wù)組合問題出發(fā)，提出了一種基于改進(jìn)PSO的UHPPSO算法。在描述算法時(shí)，定義了粒子間相似度的概念，并使用相似度來感知用戶習(xí)慣，使得算法的尋優(yōu)過程具有用戶感知能力，最后通過實(shí)驗(yàn)驗(yàn)證了本文算法的可行性和用戶感知能力。

[1]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)：1-7.

[2]范小芹，蔣昌俊，方賢文，等.基于離散微粒群算法的動態(tài)Web服務(wù)選擇[J].計(jì)算機(jī)研究與發(fā)展，2010，47（1）：147-156.

[3]劉書雷，劉云翔，張 帆，等.一種服務(wù)聚合中QoS全局最優(yōu)服務(wù)動態(tài)選擇算法[J].軟件學(xué)報(bào)，2007，18（3）：646-656.

[4]倪晚成，劉連臣，吳 澄.Web服務(wù)組合方法綜述[J].計(jì)算機(jī)工程，2008，34（4）：79-81.

[5]Zeng L Z,Benatallah B,Ngu A H,et al.QoS-aware middleware for Web Services Composition[J].IEEE Transactions on Software Engineering,2004,30(5)：311-327.

[6]李金忠，夏潔武，唐衛(wèi)東，等.基于QoS的Web服務(wù)選擇算法綜述 [J].計(jì)算機(jī)應(yīng)用研究，2010，27（10）：3622-3638.

[7]劉莉平，陳志剛，劉愛心.基于粒子群算法的Web服務(wù)組合研究[J].計(jì)算機(jī)工程，2008，34（5）：104-106,112.

[8]Yuan Q U.改進(jìn)粒子群優(yōu)化算法在服務(wù)組合中的應(yīng)用[J].計(jì)算機(jī)工程，2011，37（17）：130-132.

[9]Cardoso J,Sheth A,Miller J,et al.Quality of service for workflows and web service processes[J].Web Semantics：Science,Services and Agents on the World Wide Web,2004,1(3)：281-308.

[10]Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C]//Micro Machine and Human Science,1995.MHS'95,Proceedings of the Sixth International Symposium on,1,1995：39-43.

[11]Shi Y,Eberhart R C.A modified particle swarm optimizer[C]//The 1998 IEEE International Conference on,1998：69-73.

[12]ShiY,Eberhart R C.Parameter selection in particle swarm optimization[C]//International Conference on Evolutionary Programming.Springer Berlin Heidelberg,1998：591-600.

[13]Poli R,Kennedy J,Blackwell T.Particle swarm optimization[J].Swarm Intelligence,2007,1(1)：33-57.

[14]肖文娟，段玉聰.基于時(shí)間序列的感知QoS的云服務(wù)組合[J].計(jì)算機(jī)工程與科學(xué)，2014，36（11）：2061-2066.

[15]Zeng L,Benatallah B,Dumas M,et al.Quality driven web services composition[C]//Proceedings of the 12th international conference on World Wide Web,2003：411-421.

User’s habit-perceptive service composition based on improved PSO

ZHAO Yang,GUO Xing*
(School of Computer Science,Anhui University,Hefei Anhui230601,China)

With the sharp increase in the number of web services,it has become a problem to be solved in the service composition optimization field how to select suitable web services dynamically from a large number of candidate services sets,and combine them into a composite service to meet the complex need of value-added business process.This paper proposes a user’s habit-perceptive optimization algorithm based on PSO,and applies it to the discrete service composition optimization problem.The algorithm optimizes the service composition through user’s habits perception.Based on traditional PSO,it controls the particle to convergent according to the similarity between the particle and user’s habits,thereby optimizing the user’s habit-perceptive process.The feasibility and validity of the proposed algorithm were verified with a large number of experimental results.

service composition;PSO;user’s habit-perceptive;quality of service

TP393

A

1004-4329（2017）03-053-06

10.14096/j.cnki.cn34-1069/n/1004-4329（2017）03-053-06

2017-04-14

國家支撐計(jì)劃（2015BAK24B01）資助。

郭 星（1983- ），男，博士，講師，研究方向：服務(wù)計(jì)算、云計(jì)算、智能算法。Email：guoxing@ahu.edu.cn。