基于改良蜂群算法的Web服務組合優化方法

張志鵬,周井泉

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

0 引 言

時代飛速發展,Web服務已經成為軟件行業的新技術融合點。由于用戶的需求日益復雜,通過單一的Web服務幾乎不可能滿足用戶的需求。因此,要以適當的順序組成一組基本服務,以滿足用戶的要求。組合現有Web服務以創建新Web服務的過程稱為Web服務組合[1],但Web服務組合往往是多種多樣的,這就需要考慮如何處理此類復雜Web服務組合。

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

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

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

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

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

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

1.1 Web服務組合的概念

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

Web服務是一種可以構建分布式系統的新的網絡開發技術。它同時兼備低耦合性、可復用性,獨立于編程語言和操作平臺性。Web服務還有三大協議：SOAP(Simple Object Access Protocol),WSDL(Web Services Description Language),UDDI(Universal Description Discovery and Integration)。SOAP是一種輕量級的交換數據的規范,指可以在分布式系統中交換標準化的信息;WSDL用于描述一個Web服務及如何與Web服務通信;UDDI是服務提供者和用戶之間的一個鏈接,使用戶更加容易搜索和找到目標服務[6]。

1.2 Web服務組合的形式

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

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

圖1 Web服務組合生命周期

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

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

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

第四步：服務執行。面向客戶執行滿足其服務需求的最優Web服務組合。

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

最大化

(4)

約束,

2 基于改良蜂群算法的QoS-Web組合優化

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

2.1 改良蜂群算法

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

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

(1)初始化策略。

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

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

(5)

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

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

(6)

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

(2)雇傭蜂方程。

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

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

(7)

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

(3)圍觀蜂方程。

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

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

(8)

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

2.2 QoS-Web組合優化

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

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

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

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

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

步驟5：偵察蜂階段,如果搜索了預定義的實驗次數即限制次數后,某個解決方案的位置沒有更新,則該解決方案將被放棄,與該解決方案相關的雇傭蜂將變為偵察蜂。偵察蜂將會生成新的解決方案。

步驟6：記錄目前獲得的最優解。

步驟7：若當前沒有達到迭代次數則回到步驟3,否則輸出最優解。

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

3 實驗結果與討論

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

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

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

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

圖2 隨迭代次數變化的適應度

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

表1 適應度4種數據

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

圖3 算法的適應度標準差

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

圖4 算法執行時間

4 結束語

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

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