基于改良蜂群算法的Web服務組合優(yōu)化方法

張志鵬,周井泉

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

0 引 言

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

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

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

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

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

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

1 Web服務組合與QoS評價模型

1.1 Web服務組合的概念

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

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

1.2 Web服務組合的形式

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

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

圖1 Web服務組合生命周期

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

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

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

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

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

1.3 Web服務組合的QoS評價模型

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

最大化

(4)

約束,

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

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

2.1 改良蜂群算法

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

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

(1)初始化策略。

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

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

(5)

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

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

(6)

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

(2)雇傭蜂方程。

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

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

(7)

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

(3)圍觀蜂方程。

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

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

(8)

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

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

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

改良蜂群算法應用于Web服務組合問題的具體步驟描述如下：

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

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

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

步驟5：偵察蜂階段,如果搜索了預定義的實驗次數(shù)即限制次數(shù)后,某個解決方案的位置沒有更新,則該解決方案將被放棄,與該解決方案相關的雇傭蜂將變?yōu)閭刹旆洹刹旆鋵尚碌慕鉀Q方案。

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

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

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

3 實驗結果與討論

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

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

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

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

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

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

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

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

圖3 算法的適應度標準差

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

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

4 結束語

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

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