改進杜娟鳥搜索算法的Web服務組合優化

狄婧

摘 要： 傳統的Web服務組合優化方法均基于Web服務的功能進行規劃，獲取的Web服務組合的服務性能較低，為了解決該問題，提出基于改進杜鵑鳥搜索算法的Web服務組合優化方法。首先從數據集中采集相似服務塑造Web服務組合集，然后采用杜鵑鳥搜索算法獲取Web服務組合QoS最優化方案，并對杜鵑鳥搜索算法中萊維飛行時的路徑和位置隨機數進行改進，增強杜鵑鳥搜索算法在Web服務組合優化問題中的適應度，避免算法出現局部最佳解問題，得到優化的Web服務組合。實驗結果表明該方法具有較高的運算效率和服務質量。

關鍵詞： 杜鵑鳥搜索算法； Web服務； 組合優化； 最優方案

中圖分類號： TN911?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2017）15?0087?03

Abstract： Since the traditional Web service combination optimization method can plan on the basis of the function of Web service， and the obtained service performance of Web service composition is low， a Web service combination optimization method based on improved cuckoo search algorithm is put forward. The similar service is collected in dataset to shape the Web service group. The cuckoo search algorithm is used to acquire the QoS optimization scheme of Web service composition， improve the path of Levy flight and position random number in cuckoo search algorithm， strengthen the fitness of cuckoo search algorithm in Web service combination optimization problem， and avoid the problem of local optimal solution of the algorithm. The optimized Web service composition is obtained. The experimental results indicate that the method has high computing efficiency and service quality.

Keywords： cuckoo search algorithm； Web service； composition optimization； optimal scheme

0 引 言

隨著當前云計算技術的快速發展，Web服務的應用領域也逐漸擴張，Web服務數量呈現海量增長趨勢。為了增強Web服務的質量，Web服務組合的優化問題受到學者的廣泛關注。以往研究出的Web服務組合優化方法大都基于Web服務的功能進行規劃，未對服務質量進行全面的分析，獲取的Web服務組合優化方法的服務性能大大降低[1]。因此，大量學者著手尋求高質量的Web服務組合優化方法。

在Web服務組合優化過程中采用杜鵑鳥搜索算法進行分析，通過杜鵑鳥搜索算法得到Web服務組合QoS最優化方案，不斷改進杜鵑鳥搜索算法中Levy（萊維）飛行時的路徑和位置隨機數[2]，提高杜鵑鳥搜索算法在Web服務組合優化問題中的適應度。

1 QoS的Web服務組合問題

采用Web服務分析的數據集QWS對Web服務組合問題進行建模，通過Web服務爬蟲引擎采集6 000個Web服務，各Web服務具有9個QoS特征。QWS數據集是一種全面的數據集，廣泛應用于Web服務組合的QoS分析過程中。因此，通過QWS數據集獲取相似服務塑造Web服務組合集，采用杜鵑鳥搜索算法求解最優化的QoS組合問題，針對QoS組合問題中的服務響應時間（T）、執行成本（C）、服務價值度（A）以及服務穩定性（R）四種QoS參數進行分析，則QoS服務組合問題的表達式為：

式中：是對應的服務組合內的QoS運算公式，式（1）是目標函數，對和實施極小化處理。

在理想點的原理下，將多目標問題變換成單目標問題[3]，將全部Web服務中的服務響應時間以及執行成本的最低值當成理想點以及則獲取的目標函數為：

式（2）是將QoS的服務組合問題從多目標問題變換成單目標問題的數學模型，基于目標系統的實際應用情況設置以及的值。

進行Web服務組合時，應在大量特定功能的小粒度Web服務內，采集滿足用戶要求的服務[4]，并將這些服務基于合理的組合方式塑造成功能完整的Web服務。通常狀態下Web服務組合的目標以及原始規范都是已知的，也就是輸入以及輸出Web服務都已知，對Web服務組合進行優化時的Web服務數量以及組合方案都未知。一般在服務組合方案明確的狀態下[5]，也就是提供候選服務集，并且候選服務集的組合方案已知，各候選服務集內存在不同的具體服務，從各候選服務集內獲取最佳的Web服務方案，如圖1所示。其反映的是構建在已知服務組合方案Plan下的Web服務組合流程。

圖1描述的Web服務組合方案，在一個Web服務組合的工作流內，不同步驟的Web服務采集包含較多的有價值目標服務組件，獲取所有有價值Web服務組合方案后[6]，采用式（2）的目標函數運算各策略的QoS值，可獲取最佳的Web服務組合。當候選服務集存在海量的Web服務數量時，將大大降低Web服務組合優化效率，因此采用杜鵑鳥搜索算法降低目標函數的運算量，獲取最佳的Web服務組合方案。

2 改進杜鵑鳥搜索算法的Web服務組合優化

2.1 改進杜鵑鳥搜索算法

杜鵑鳥搜索算法是在模擬杜鵑鳥的孵蛋行為以及Levy飛行的基礎上產生的，原始杜鵑鳥搜索算法中存在如下前提條件[7]：

（1） 各杜鵑鳥一次僅下一個蛋，將蛋任意存儲到一個鳥巢內。

（2） 對主巢內最優品種的杜鵑鳥蛋進行孵化，生成后續杜鵑鳥。

（3） 杜鵑鳥選擇孵蛋的鳥巢數量固定，設置發現杜鵑鳥蛋的概率。

設置杜鵑鳥搜索算法的初始解為目標函數是采用運算解的適應度值；算法采用Levy飛行模式搜索鳥巢，是一種獲取新解的過程；搜索算法此刻的最優適應度為如果新解的適應度同一致，則用新適應度值替換。

基于上文分析的三種前提條件，杜鵑鳥搜索鳥巢的位置也就是產生新解的修正公式為：

式中：分別用于描述第個鳥巢在第代以及第代條件下，第維的位置；是萊維飛行的跳躍路徑，其是一種隨機檢索的路徑，通過調控量對路徑大小進行合理調控[8]。

對以及使用服從正態分布的隨機數，可確保以及值正負交叉，增強Levy飛行方向的差異性，提高杜鵑鳥在不同區域間的飛行效率[9]，避免算法出現局部最佳解問題。

2.2 改進杜鵑鳥搜索算法的Web服務優化流程

改進算法的Web服務優化流程具體如下：

（1） 采用基于QoS的Web服務組合問題建模方法，將多目標的Web服務組合問題變換成單目標問題；

（2） 設置個杜鵑鳥巢，也就是個Web服務組合方案；

（3） 將不同杜鵑鳥巢中的解看成服務組合方案的解，分析服務組合是否符合式（1）描述的限制規范，如果符合，則運算目標函數的值[10]，并將獲取的值當成解的適應度，如式（2）；

（4） 采用式（5）描述位置修正過程，對隨機數以及采用改進后的選取方法產生個新解，分析新解是否符合式（1）描述的限制規范，同時記錄原始最佳解；

（5） 基于被發現概率將產生新解；

（6） 采用式（2）運算各解的適應度，獲取最小適應度對應的解，用該解替換最優解集；

（7） 分析是否達到最高迭代次數，達到則終止運算；否則，返回過程（4）。

具體流程如圖2所示。

3 實驗結果與分析

實驗將改進杜鵑鳥搜索算法應用在基于QoS的Web服務最優化模型中，分析改進杜鵑鳥搜索算法的Web服務優化性能。實驗采用數據集QWS中選擇的Web服務構成服務組合，設置6個服務組，各服務組合中含有80個服務，設置不同的循環次數，對比分析兩種方法獲取的適應度值。基于改進杜鵑鳥搜索算法和標準杜鵑鳥搜索算法的Web服務組合的適應度值，見表1。

對比分析表1中的數據可得，相同循環次數條件下，相對于原始杜鵑鳥搜索算法的Web服務組合，采用本文提出的改進杜鵑鳥搜索算法的Web服務組合的適應度均值以及最小值都較優。

不同迭代次數下本文方法和原始方法的運算時間以及服務滿意度分別如圖3和圖4所示。

分析圖3可得，本文方法的運算時間低于原始方法，并且在1 000次迭代條件下，本文方法的運算時間低于1.8 s，說明本文方法可在短時間內獲取符合用戶要求的Web服務組合，運算性能強。分析圖4可得，本文方法獲取的Web服務組合的服務滿意度遠遠高于原始方法，并且隨著迭代次數的增加，服務滿意度呈現平穩上升趨勢，說明本文方法具有較高的服務質量。

4 結 語

為了提高Web服務組合優化過程中的服務質量，本文提出了基于改進杜鵑鳥搜索算法的Web服務組合優化方法，并通過實驗檢測該種方法的性能，能夠看出本文方法獲取的Web服務組合適應度較優，并具有較高的運算效率和服務質量。

參考文獻

[1] 張以文，吳金濤，趙姝，等.基于改進煙花算法的Web服務組合優化[J].計算機集成制造系統，2016，22（2）：422?432.

[2] 倪志偉，方清華，李蓉蓉，等.改進蟻群算法在基于服務質量的Web服務組合優化中的應用[J].計算機應用，2015，35（8）：2238?2243.

[3] 徐甜，劉凌霞.基于改進遺傳算法的Web服務優化組合研究[J].計算機應用與軟件，2016，33（5）：24?27.

[4] 段立，侯興哲，陳俐冰，等.基于改進DAG的Web服務組合優化[J].計算機系統應用，2015，24（2）：22?27.

[5] 高葉軍，連志剛，曹宇.基于改進杜鵑鳥搜索算法的火電廠機組組合優化[J].電氣自動化，2015，37（4）：64?66.

[6] 王野，周井泉，常瑞云.基于知識的人工蜂群服務組合優化算法[J].計算機技術與發展，2016，26（5）：46?50.

[7] 張晶，吳虎勝.改進二進制杜鵑鳥搜索算法求解多維背包問題[J].計算機應用，2015，35（1）：183?188.

[8] 方清華，倪麗萍，李一鳴.求解物流Web服務組合問題的兩階段多目標蟻群算法[J].中國機械工程，2016，27（10）：1327?1336.

[9] 馮艷，陳富贊.基于QoS多屬性決策的Web服務組合優化方法[J].計算機工程，2015，41（6）：33?37.

[10] 張燕平，荊紫慧，張以文，等.基于離散粒子群算法的動態Web服務組合[J].計算機科學，2015，42（6）：71?75.