改進(jìn)杜娟鳥(niǎo)搜索算法的Web服務(wù)組合優(yōu)化

狄婧

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

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

中圖分類(lèi)號(hào)： TN911?34； TP391 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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)前云計(jì)算技術(shù)的快速發(fā)展，Web服務(wù)的應(yīng)用領(lǐng)域也逐漸擴(kuò)張，Web服務(wù)數(shù)量呈現(xiàn)海量增長(zhǎng)趨勢(shì)。為了增強(qiáng)Web服務(wù)的質(zhì)量，Web服務(wù)組合的優(yōu)化問(wèn)題受到學(xué)者的廣泛關(guān)注。以往研究出的Web服務(wù)組合優(yōu)化方法大都基于Web服務(wù)的功能進(jìn)行規(guī)劃，未對(duì)服務(wù)質(zhì)量進(jìn)行全面的分析，獲取的Web服務(wù)組合優(yōu)化方法的服務(wù)性能大大降低[1]。因此，大量學(xué)者著手尋求高質(zhì)量的Web服務(wù)組合優(yōu)化方法。

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

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

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

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

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

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

進(jìn)行Web服務(wù)組合時(shí)，應(yīng)在大量特定功能的小粒度Web服務(wù)內(nèi)，采集滿足用戶(hù)要求的服務(wù)[4]，并將這些服務(wù)基于合理的組合方式塑造成功能完整的Web服務(wù)。通常狀態(tài)下Web服務(wù)組合的目標(biāo)以及原始規(guī)范都是已知的，也就是輸入以及輸出Web服務(wù)都已知，對(duì)Web服務(wù)組合進(jìn)行優(yōu)化時(shí)的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ù)組合方案，在一個(gè)Web服務(wù)組合的工作流內(nèi)，不同步驟的Web服務(wù)采集包含較多的有價(jià)值目標(biāo)服務(wù)組件，獲取所有有價(jià)值Web服務(wù)組合方案后[6]，采用式（2）的目標(biāo)函數(shù)運(yùn)算各策略的QoS值，可獲取最佳的Web服務(wù)組合。當(dāng)候選服務(wù)集存在海量的Web服務(wù)數(shù)量時(shí)，將大大降低Web服務(wù)組合優(yōu)化效率，因此采用杜鵑鳥(niǎo)搜索算法降低目標(biāo)函數(shù)的運(yùn)算量，獲取最佳的Web服務(wù)組合方案。

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

2.1 改進(jìn)杜鵑鳥(niǎo)搜索算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

具體流程如圖2所示。

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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