張志鵬,周井泉

(南京郵電大學(xué) 電子與光學(xué)工程學(xué)院、柔性電子(未來技術(shù))學(xué)院,江蘇 南京 210003)

0 引 言

時代飛速發(fā)展,Web服務(wù)已經(jīng)成為軟件行業(yè)的新技術(shù)融合點。由于用戶的需求日益復(fù)雜,通過單一的Web服務(wù)幾乎不可能滿足用戶的需求。因此,要以適當(dāng)?shù)捻樞蚪M成一組基本服務(wù),以滿足用戶的要求。組合現(xiàn)有Web服務(wù)以創(chuàng)建新Web服務(wù)的過程稱為Web服務(wù)組合[1],但Web服務(wù)組合往往是多種多樣的,這就需要考慮如何處理此類復(fù)雜Web服務(wù)組合。

為了為用戶的任務(wù)設(shè)計復(fù)合Web服務(wù)(Composite Web Service,CWS),首先將任務(wù)劃分為n個子任務(wù)。然后,從有m個候選服務(wù)的候選池挑選一個基本的Web服務(wù)根據(jù)其功能屬性映射到一個子任務(wù)中。最后,將映射的Web服務(wù)集成到組合Web服務(wù)中,子任務(wù)的執(zhí)行順序與服務(wù)組合順序相同。Web服務(wù)候選池中存在許多具有相同功能屬性的基本服務(wù),從候選Web服務(wù)集中選擇最優(yōu)CWS稱為Web服務(wù)選擇。

每個Web服務(wù)都有一個核心功能,稱為該Web服務(wù)的功能屬性。除了功能屬性外,每個Web服務(wù)還擁有一些非功能屬性,這些屬性也被稱為QoS屬性。最優(yōu)選擇定義為：既能滿足用戶的功能性需求,又能滿足QoS屬性的CWS稱為最優(yōu)選擇。因此,如何挑選出最優(yōu)選擇是解決Web服務(wù)組合問題的重點。

對于此類最優(yōu)選擇問題,沒有哪種特定的元啟發(fā)式算法一定是最好的。因此,新的算法在Web服務(wù)選擇領(lǐng)域一直廣受歡迎。Wang Hei-Chia等人結(jié)合用戶對Web服務(wù)的主觀評價數(shù)據(jù)和服務(wù)本身的客觀數(shù)據(jù),通過模糊專家系統(tǒng)建立服務(wù)的QoS評測模型。隨后基于評測后的QoS屬性值,利用遺傳算法(Genetic Algorithm,GA)進(jìn)行服務(wù)組合方案的求解[2]。范小琴等人根據(jù)自然界中的物種協(xié)同進(jìn)化的思想,提出了一種協(xié)同進(jìn)化的元啟發(fā)算法來求解全局Web服務(wù)選擇問題[3]。Klein和Adrian等人利用遺傳算法來解決包含多個子任務(wù)的Web服務(wù)選擇問題。趙欣超等人利用粒子群優(yōu)化算法對人工免疫算法進(jìn)行改良,把其應(yīng)用到全局Web服務(wù)選擇中[4]。黃碧晴等人利用混沌的思想提出了一個新的元啟發(fā)算法來解決Web服務(wù)組合問題,并取得了比傳統(tǒng)遺傳算法更好的結(jié)果。Huo,Yin等人利用單維度小擾動的思想改進(jìn)了人工蜂群算法(Artificial Bee Colony,ABC)并應(yīng)用于Web服務(wù)選擇中[5]。

可見,QoS評價模型和群體智能算法經(jīng)常被用于處理Web服務(wù)組合問題。QoS模型能使處理結(jié)果更加符合客戶非功能需求,而群體智能算法中的蜂群算法具有設(shè)置參數(shù)少、實現(xiàn)簡單、工程適用性強等優(yōu)點,近年來一直被用于處理Web服務(wù)組合問題。但上述研究對于種群初始化、求解策略未做過多改進(jìn),并且算法適應(yīng)度、穩(wěn)定性有待進(jìn)一步提高,于是該文在這兩個方面展開進(jìn)一步研究。

為提高算法的適應(yīng)度和穩(wěn)定性,該文提出了一種新的改良人工蜂群算法用于Web服務(wù)的選擇。它使用基于混沌的初始化技術(shù)將初始解分散在搜索空間,采用改良的蜜源搜索方程對搜索空間進(jìn)行優(yōu)化,并改良了圍觀蜂相位的搜索方程,獲得了良好的性能。

1 Web服務(wù)組合與QoS評價模型

1.1 Web服務(wù)組合的概念

Web Services Architecture組織給Web服務(wù)組合的定義是：一個支持網(wǎng)絡(luò)節(jié)點交互的應(yīng)用程序,每個Web服務(wù)都存在明確的、機(jī)器可識別的通用標(biāo)準(zhǔn)描述來說明節(jié)點如何以特定的方式彼此交互。

Web服務(wù)是一種可以構(gòu)建分布式系統(tǒng)的新的網(wǎng)絡(luò)開發(fā)技術(shù)。它同時兼?zhèn)涞婉詈闲?、可?fù)用性,獨立于編程語言和操作平臺性。Web服務(wù)還有三大協(xié)議：SOAP(Simple Object Access Protocol),WSDL(Web Services Description Language),UDDI(Universal Description Discovery and Integration)。SOAP是一種輕量級的交換數(shù)據(jù)的規(guī)范,指可以在分布式系統(tǒng)中交換標(biāo)準(zhǔn)化的信息;WSDL用于描述一個Web服務(wù)及如何與Web服務(wù)通信;UDDI是服務(wù)提供者和用戶之間的一個鏈接,使用戶更加容易搜索和找到目標(biāo)服務(wù)[6]。

1.2 Web服務(wù)組合的形式

Web服務(wù)組合是通過調(diào)用相互連接的其他服務(wù)來構(gòu)造的。服務(wù)的組合允許不同應(yīng)用程序之間在Internet上進(jìn)行協(xié)作、協(xié)調(diào)和合作。并且服務(wù)組合可用于構(gòu)建一些智能化定制的應(yīng)用程序,以交付給用戶新的服務(wù)和功能。在日常使用越來越多的復(fù)雜系統(tǒng)中,已經(jīng)出現(xiàn)了這種便于用戶實現(xiàn)其需求的組合技術(shù)系統(tǒng)。

Web服務(wù)組合通常經(jīng)歷很多步驟,圖1展示了Web服務(wù)組合的一般生命周期,主要分為4個步驟：

圖1 Web服務(wù)組合生命周期

第一步：定義。用戶提出其個人服務(wù)需求,先根據(jù)其需求提取關(guān)鍵信息,并對其進(jìn)行拆解,分成多個子步驟去完成,每個子步驟按一定的拓?fù)湎噙B接組合,定義為一個新的抽象流程。

第二步：服務(wù)選擇。不同的供應(yīng)者向注冊服務(wù)中心提供各種候選Web服務(wù)以形成候選Web服務(wù)集合。這時根據(jù)第一步得到的抽象流程,向每一個子步驟中挑選多個符合其要求的Web服務(wù)。

第三步：服務(wù)調(diào)度。對第二步得到的服務(wù)組合中每一個子步驟進(jìn)行排列組合,每一種不同的排列方法都會生成一個新的服務(wù)組合,經(jīng)過篩選比對后從中挑選出最優(yōu)的Web服務(wù)組合。

第四步：服務(wù)執(zhí)行。面向客戶執(zhí)行滿足其服務(wù)需求的最優(yōu)Web服務(wù)組合。

當(dāng)知道其任務(wù)具體分解形式時,便可以采用上述方法向用戶提供最優(yōu)的Web服務(wù),當(dāng)不知道任務(wù)具體需求時,即非功能需求,便可通過QoS模型進(jìn)行處理。

1.3 Web服務(wù)組合的QoS評價模型

QoS屬性是Web服務(wù)里非常重要的綜合指標(biāo),可以將用戶對某項服務(wù)非功能屬性的滿意度用數(shù)值表示,是客戶的非功能需求的直觀體現(xiàn)。常用的QoS屬性包括可用性、可靠性、響應(yīng)時間、延遲,它們的具體定義為：

(1)可用性：成功調(diào)用的數(shù)量與總調(diào)用數(shù)量的比率。

(2)可靠性：正確消息與總消息的比率。

(3)響應(yīng)時間：發(fā)送請求到接收響應(yīng)之間的時間跨度。

(4)延遲：執(zhí)行請求所花費的時間。

可靠性與可用性屬于積極的QoS屬性,越高越好。響應(yīng)時間與延遲屬于消極的QoS屬性,越低越好。

QoS評價模型將CWS的聚合QoS值映射為實數(shù),即效用值,以便后續(xù)計算使用,需要執(zhí)行以下兩個步驟：

(1)歸一化：將不同Web服務(wù)的QoS屬性值歸一化為0到1之間的實數(shù)。

(2)加權(quán)：將每個歸一化的QoS值與相應(yīng)的權(quán)重相乘并相加,得到該CWS的效用值。

CWS各個QoS屬性歸一化處理如下：

如果qk為積極屬性,則qk的歸一化處理結(jié)果如式1所示。

(1)

如果qk為消極屬性,則qk的歸一化處理結(jié)果如式2所示。

(2)

服務(wù)組合執(zhí)行有4種基本結(jié)構(gòu)：順序、并行、選擇和循環(huán),本次采用順序結(jié)構(gòu)。順序結(jié)構(gòu)下CWS的第k個QoS屬性的聚合值如式3所示。

(3)

利用上述QoS屬性歸一化處理和QoS聚合值計算公式,將尋找滿足全局約束的最優(yōu)CWS的問題表述為：

最大化

(4)

約束,

2 基于改良蜂群算法的QoS-Web組合優(yōu)化

近年來,多種智能算法用于處理Web組合優(yōu)化問題,其中蜂群算法在解決問題過程中具有設(shè)置參數(shù)少、實現(xiàn)簡單、工程適用性強等優(yōu)點,近年來一直是熱門算法。針對蜂群算法中的群體初始化、相位搜索方程、圍觀搜索策略進(jìn)行改良,該文提出一種改良的蜂群算法(modified Artificial Bee Colony,mABC)來解決Web組合優(yōu)化問題。

2.1 改良蜂群算法

ABC(Artificial Bee Colony)算法由Karaboga和Basturk提出,是一種基于蜂群的元啟發(fā)式算法,基于蜜蜂的覓食行為。一群蜜蜂一起生活在一個蜂箱被稱為蜂群。蜂群由三種不同類型的蜜蜂組成：(i)雇傭蜂;(ii)圍觀蜂;(iii)偵察蜂。不同的蜂種執(zhí)行各自的任務(wù),蜂群的覓食任務(wù)是由雇傭蜂發(fā)起的。每只雇傭蜂都瞄準(zhǔn)食物來源的位置,并收集有關(guān)該食物來源中可用花蜜量的信息。之后,它們與巢友分享關(guān)于花蜜量的信息。在收集了食物來源的信息后,圍觀蜂會選擇更好的食物來源。當(dāng)一只雇傭蜂發(fā)現(xiàn)食物來源被遺棄時,會恢復(fù)它作為偵察蜂的角色。這樣,開發(fā)的責(zé)任由雇傭蜂和圍觀蜂共同承擔(dān),而探索的責(zé)任則由偵查蜜蜂獨自承擔(dān)[7]。

對傳統(tǒng)蜂群算法的初始化策略、雇傭蜂和圍觀蜂的方程進(jìn)行修改。

(1)初始化策略。

為了選擇更好的初始種群,提出了一種基于混沌映射的對立學(xué)習(xí)方法,如式5所示。

chk+1=μ×chk(1-chk)

(5)

其中,chk為0到1之間的隨機(jī)數(shù),μ設(shè)置為4。

基于對立學(xué)習(xí)(Opposition Based Learning,OBL),同時考慮估計解X及其對應(yīng)的相反估計值,以覆蓋整個搜索空間。每個解的相反估計值的計算方法如式6所示。

(6)

蜂群算法的種群初始化中有兩個循環(huán)：第一個循環(huán)中,使用基于混沌映射原理的式5來進(jìn)一步生成估計解X。第二個循環(huán)中,使用基于OBL原理的式6得到另一個解的集合Xo,對所有解進(jìn)行求值,形成組合集,利用精英主義原理得到更好的初始化種群。

(2)雇傭蜂方程。

被雇傭的蜜蜂首先尋找新的潛在候選解,為了充分挖掘每一種可能,需要對各個維度信息進(jìn)行交換,提出一個新的相位搜索方程,見式7。

Vi=φijXi+(1-φij)Xk

(7)

其中,i,k∈(1,SN),k≠i,φij～U(-1,1)為-1和1之間的隨機(jī)分布數(shù)。

(3)圍觀蜂方程。

圍觀蜜蜂的功能很大程度上取決于雇傭蜜蜂,因為它們需要從雇傭蜂那里得到有用信息再進(jìn)行下一步判斷處理。為了提高搜索強度,對傳統(tǒng)ABC算法中圍觀蜂的搜索方程進(jìn)行了改良。在文獻(xiàn)[8-9]的研究中都可以明顯看出,涉及最優(yōu)解并探索其周圍的搜索空間可以提高開發(fā)性能。新的圍觀搜索方程如式8。

xij=xij+φij(xbest,j-xr1,j)+(1-φij)(xr2,j-xr3,j)

(8)

其中,r1,r2,r3是互斥隨機(jī)數(shù),且i,r1,r2,r3∈(1,SN),r1≠r2≠r3,j∈(1,D)是隨機(jī)選擇的指標(biāo)。類似地,xbest是當(dāng)前種群中具有最佳適應(yīng)度的最佳解向量。

2.2 QoS-Web組合優(yōu)化

由QoS的Web服務(wù)組合模型得到的QoS效用函數(shù)U如式4所示,作為適應(yīng)度值。

改良蜂群算法應(yīng)用于Web服務(wù)組合問題的具體步驟描述如下：

步驟1：參數(shù)設(shè)置階段,種群大小為m,維數(shù)為n,限制為mn/2,最大迭代次數(shù)為Max。

步驟3：雇傭蜂階段,雇傭蜂根據(jù)鄰域搜索方程(式7)產(chǎn)生新解,計算其適應(yīng)度值,并進(jìn)行貪婪選擇。

步驟4：圍觀蜂階段,圍觀蜂進(jìn)行輪盤選擇,從雇傭蜂產(chǎn)生的解中選擇一個更合適的解,解決方案的質(zhì)量取決于適應(yīng)度值,在評估適應(yīng)度后,圍觀蜂更新解決方案的位置,即圍觀搜索策略(式8)。

步驟5：偵察蜂階段,如果搜索了預(yù)定義的實驗次數(shù)即限制次數(shù)后,某個解決方案的位置沒有更新,則該解決方案將被放棄,與該解決方案相關(guān)的雇傭蜂將變?yōu)閭刹旆?。偵察蜂將會生成新的解決方案。

步驟6：記錄目前獲得的最優(yōu)解。

步驟7：若當(dāng)前沒有達(dá)到迭代次數(shù)則回到步驟3,否則輸出最優(yōu)解。

通過U的值來判斷得出解的質(zhì)量,即顧客對于Web服務(wù)組合的滿意度,U越高表示結(jié)果越符合客戶需求,U越低表示結(jié)果不滿足客戶需求,U的值越高越好。

3 實驗結(jié)果與討論

此次實驗采用Web服務(wù)的QWS數(shù)據(jù)集[10]。該數(shù)據(jù)集包含2 507行和9列。一行代表一個基本的Web服務(wù),一列代表一個QoS屬性。因此此次實驗使用2 500行,4列,即Web服務(wù)數(shù)量為2 500,QoS屬性數(shù)量為4。

為了分析算法性能,將mABC與5種現(xiàn)有的元啟發(fā)式算法(人工蜂群算法[11](ABC)、差分進(jìn)化算法[12](DE)、改良灰狼算法[13](MGWO)、最優(yōu)導(dǎo)向人工蜂群算法[14](GABC)和改進(jìn)人工蜂群算法[15](IABC))進(jìn)行了比較。

QoS的4個屬性是：響應(yīng)時間(ms)、延遲(ms)、可用性(%)和可靠性(%)。所有的實驗都是在64位3.40 GHz Intel(R)酷睿(TM) i7-3770 PC上的窗口環(huán)境中實現(xiàn)的,具有8 GB RAM。在實驗中對mABC進(jìn)行了以下參數(shù)設(shè)置。在引言中提到的n個子任務(wù)和每個子任務(wù)中的m個候選Web服務(wù),對應(yīng)算法中的維數(shù)(n)和種群大小(m),分別設(shè)置為10和250,限制設(shè)置為(mn/2)。所有算法的停止條件是最大迭代次數(shù)(Max),設(shè)置為500,所有算法迭代次數(shù)為Max=500。

圖2顯示了mABC算法與其它算法的適應(yīng)度比較?？梢钥闯?當(dāng)?shù)螖?shù)達(dá)到25次時,mABC算法適應(yīng)度為5.69,開始始終優(yōu)于其他算法。當(dāng)?shù)螖?shù)達(dá)到50次時,適應(yīng)度為5.72,已經(jīng)高于當(dāng)他算法的最優(yōu)值。迭代次數(shù)100時,其余算法適應(yīng)度趨于穩(wěn)定不再增加,而改良蜂群算法仍在逐步提升直至200次時達(dá)到最優(yōu)值5.8,其余算法在迭代50到75次之間逐漸趨于穩(wěn)定,但探索的不夠充分,無法達(dá)到更高的適應(yīng)度,而mABC算法雖然收斂的慢,但仍在探索解,并在不斷提高最大適應(yīng)度。在整個迭代過程中可以看出,從第25次迭代開始mABC的適應(yīng)度都比其余算法的高。并且mABC算法能在保證收斂的情況下取得更高的適應(yīng)度,更適合解決Web服務(wù)組合問題,與理論上的預(yù)期相同。

圖2 隨迭代次數(shù)變化的適應(yīng)度

為對比不同算法適應(yīng)度標(biāo)準(zhǔn)差的情況,分析了數(shù)據(jù)的最大值、最小值、中間值、平均值,如表1所示,其中mABC算法適應(yīng)度的最大值5.8、最小值5.69、中間值5.78、平均值5.76,與其余幾種算法的數(shù)據(jù)對比可見mABC算法的最大值、最小值、中間值、平均值都比其他幾種算法的優(yōu)。并且mABC算法相較原始ABC算法在適應(yīng)度最大值提升了11.9%,適應(yīng)度平均值提升了12.5%。

表1 適應(yīng)度4種數(shù)據(jù)

標(biāo)準(zhǔn)差是衡量一個數(shù)據(jù)穩(wěn)定狀況的值,標(biāo)準(zhǔn)差越低表示該數(shù)據(jù)越穩(wěn)定,越高則表示越不穩(wěn)定。通過表1數(shù)據(jù)計算幾種算法適應(yīng)度的標(biāo)準(zhǔn)差,如圖3所示,mABC的標(biāo)準(zhǔn)差為0.043,明顯低于其余幾種算法,說明mABC算法相較于其余幾種算法具有較好的穩(wěn)定性,更適合解決Web服務(wù)組合問題,與理論上的預(yù)期相同。

圖3 算法的適應(yīng)度標(biāo)準(zhǔn)差

執(zhí)行時間指的是算法完成一次實驗需要的時間,通過將實驗運行100次記錄算法的平均時間使結(jié)果更加可靠。圖4為6種算法執(zhí)行時間統(tǒng)計圖,其中mABC的執(zhí)行時間為1.81 s,高于其余幾種算法,這是由于在算法的種群初始化階段加入了混沌映射,同時這也使得算法更加復(fù)雜,執(zhí)行時間增加,但增加了算法的探索性。從圖2中也可以看出,mABC的最大適應(yīng)度在其余算法都已經(jīng)收斂時仍在增加,說明初始化策略的改動使得算法犧牲一定的執(zhí)行時間去換取更大的適應(yīng)度[16-19]。

圖4 算法執(zhí)行時間

4 結(jié)束語

文中給出了Web服務(wù)組合的QoS數(shù)學(xué)模型,通過使用基于混沌的對立學(xué)習(xí)方法生成初始種群提高傳統(tǒng)ABC算法的開發(fā)能力,再修改雇傭蜂和圍觀蜂的搜索方程,改良了ABC算法并用來解決Web服務(wù)組合優(yōu)化問題。實驗數(shù)據(jù)表明,mABC算法在執(zhí)行時間方面比其余算法略微都要長一些,但在適應(yīng)度、穩(wěn)定性方面有較好表現(xiàn),優(yōu)于其余參照算法,在處理Web服務(wù)組合問題上具有可行性和有效性。

該文的研究空間還很大,在后續(xù)的工作中,筆者將會對ABC算法的尋優(yōu)過程進(jìn)行進(jìn)一步優(yōu)化并投入到Web服務(wù)組合優(yōu)化研究。