狄婧

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

關(guān)鍵詞： 杜鵑鳥搜索算法； Web服務(wù)； 組合優(yōu)化； 最優(yōu)方案

中圖分類號： TN911?34； TP391 文獻標(biāo)識碼： 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 引 言

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

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

1 QoS的Web服務(wù)組合問題

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

式中：是對應(yīng)的服務(wù)組合內(nèi)的QoS運算公式，式（1）是目標(biāo)函數(shù)，對和實施極小化處理。

在理想點的原理下，將多目標(biāo)問題變換成單目標(biāo)問題[3]，將全部Web服務(wù)中的服務(wù)響應(yīng)時間以及執(zhí)行成本的最低值當(dāng)成理想點以及則獲取的目標(biāo)函數(shù)為：

式（2）是將QoS的服務(wù)組合問題從多目標(biāo)問題變換成單目標(biāo)問題的數(shù)學(xué)模型，基于目標(biāo)系統(tǒng)的實際應(yīng)用情況設(shè)置以及的值。

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

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

2 改進杜鵑鳥搜索算法的Web服務(wù)組合優(yōu)化

2.1 改進杜鵑鳥搜索算法

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

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

（2） 對主巢內(nèi)最優(yōu)品種的杜鵑鳥蛋進行孵化，生成后續(xù)杜鵑鳥。

（3） 杜鵑鳥選擇孵蛋的鳥巢數(shù)量固定，設(shè)置發(fā)現(xiàn)杜鵑鳥蛋的概率。

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

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

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

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

2.2 改進杜鵑鳥搜索算法的Web服務(wù)優(yōu)化流程

改進算法的Web服務(wù)優(yōu)化流程具體如下：

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

（2） 設(shè)置個杜鵑鳥巢，也就是個Web服務(wù)組合方案；

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

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

（5） 基于被發(fā)現(xiàn)概率將產(chǎn)生新解；

（6） 采用式（2）運算各解的適應(yīng)度，獲取最小適應(yīng)度對應(yīng)的解，用該解替換最優(yōu)解集；

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

具體流程如圖2所示。

3 實驗結(jié)果與分析

實驗將改進杜鵑鳥搜索算法應(yīng)用在基于QoS的Web服務(wù)最優(yōu)化模型中，分析改進杜鵑鳥搜索算法的Web服務(wù)優(yōu)化性能。實驗采用數(shù)據(jù)集QWS中選擇的Web服務(wù)構(gòu)成服務(wù)組合，設(shè)置6個服務(wù)組，各服務(wù)組合中含有80個服務(wù)，設(shè)置不同的循環(huán)次數(shù)，對比分析兩種方法獲取的適應(yīng)度值?；诟倪M杜鵑鳥搜索算法和標(biāo)準(zhǔn)杜鵑鳥搜索算法的Web服務(wù)組合的適應(yīng)度值，見表1。

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

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

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

4 結(jié) 語

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

參考文獻

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

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

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

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

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

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

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

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

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

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