康國勝，劉建勛，唐明董，徐 宇

（湖南科技大學(xué)知識(shí)處理與網(wǎng)絡(luò)化制造湖南省普通高校重點(diǎn)實(shí)驗(yàn)室 湘潭 411201）

1 引言

Web服務(wù)作為一種嶄新的分布式計(jì)算模式在電子商務(wù)、企業(yè)應(yīng)用集成等領(lǐng)域扮演著越來越重要的角色。隨著Web服務(wù)技術(shù)的日益成熟，越來越多穩(wěn)定易用的Web服務(wù)共享在網(wǎng)絡(luò)上，但單個(gè)的Web服務(wù)能夠提供的功能有限，為更加充分利用共享的Web服務(wù)，有必要將共享的Web服務(wù)組合起來，提供更為強(qiáng)大的服務(wù)功能，加快系統(tǒng)開發(fā)的速度，快速滿足用戶的需求。因此，如何將若干個(gè)現(xiàn)存的Web服務(wù)整合起來以形成新的、滿足用戶需求的、增值的大粒度流程服務(wù)已成為新的應(yīng)用需求。

服務(wù)組合流程模型由多個(gè)抽象的服務(wù)結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)只包含功能需求描述，不指定具體的服務(wù)調(diào)用實(shí)例?；ヂ?lián)網(wǎng)環(huán)境中，存在多個(gè)相同或相似功能而具有不同QoS參數(shù)(如執(zhí)行時(shí)間、費(fèi)用等)的Web服務(wù)，如何從中選擇出滿足各服務(wù)結(jié)點(diǎn)非功能需求的具體服務(wù)，形成一個(gè)可執(zhí)行的服務(wù)路徑來完成用戶的需求成為服務(wù)組合的關(guān)鍵問題，本文稱其為Web服務(wù)動(dòng)態(tài)選擇問題。

目前，支持QoS的Web服務(wù)動(dòng)態(tài)選擇的研究大部分基于QoS局部最優(yōu)的原則[1，2]，即對(duì)滿足組合流程中單個(gè)服務(wù)結(jié)點(diǎn)功能需求的一組服務(wù)，根據(jù)服務(wù)的各個(gè)QoS參數(shù)信息進(jìn)行加權(quán)和的排序，并以此為依據(jù)分別為各服務(wù)結(jié)點(diǎn)選擇加權(quán)和最大的服務(wù)來執(zhí)行其功能。局部最優(yōu)服務(wù)選擇方法中為各服務(wù)結(jié)點(diǎn)獨(dú)立地選擇服務(wù)，未考慮服務(wù)之間的相互關(guān)聯(lián)性，不能解決服務(wù)組合的QoS全局最優(yōu)問題，如：要求組合流程的可靠性和信譽(yù)等級(jí)均滿足一定條件的情況下執(zhí)行費(fèi)用最低、時(shí)間最短。對(duì)于QoS全局最優(yōu)問題，目前的研究工作不多[3～7]，其主要思想都是通過將Web服務(wù)組合流程的各個(gè)QoS參數(shù)線性加權(quán)為一個(gè)單目標(biāo)，利用線性規(guī)劃的基本原理來解決服務(wù)選擇的QoS全局最優(yōu)問題或者研究求解該模型的各種算法。總之，它們尚存在以下問題：

·把組合流程中的各個(gè)QoS參數(shù)線性化為一個(gè)目標(biāo)函數(shù)，不能解決多目標(biāo)優(yōu)化問題；

·由于加權(quán)和的結(jié)果不僅對(duì)權(quán)重敏感，而且用戶需要對(duì)問題有一定的認(rèn)識(shí)，使得加權(quán)的方法在實(shí)際應(yīng)用中不可行；

·產(chǎn)生的優(yōu)化結(jié)果為單個(gè)解，用戶沒有選擇的余地；

·算法的時(shí)間復(fù)雜度大，隨著候選服務(wù)數(shù)量的增加，整個(gè)服務(wù)組合的性能將會(huì)受到影響。

所以，研究Web服務(wù)組合中基于服務(wù)質(zhì)量的服務(wù)選擇問題的智能優(yōu)化算法及其實(shí)現(xiàn)顯得尤為重要。參考文獻(xiàn)[8]針對(duì)現(xiàn)有服務(wù)選擇算法的不足，提出一種解決服務(wù)組合中QoS全局最優(yōu)動(dòng)態(tài)Web服務(wù)選擇算法，解決了傳統(tǒng)方法中難以解決的問題，但算法的執(zhí)行效率還有待提高。

本文利用差異演化算法，針對(duì)參考文獻(xiàn)[8]中的服務(wù)組合多目標(biāo)優(yōu)化問題進(jìn)行了算法設(shè)計(jì)和求解。理論分析和實(shí)驗(yàn)結(jié)果表明，相對(duì)多目標(biāo)遺傳算法，本文提出的算法的時(shí)間復(fù)雜度低，收斂速度快，搜索的全局性更好，能夠快速找到全局最佳服務(wù)組合決策。一般情況下，服務(wù)請(qǐng)求只要求找出滿足條件約束的組合服務(wù)，而非全局最優(yōu)服務(wù)，這可通過控制迭代次數(shù)來實(shí)現(xiàn)，因此進(jìn)化算法更適合解決該類型的組合優(yōu)化問題。

2 服務(wù)組合問題

動(dòng)態(tài)服務(wù)組合中，服務(wù)組合流程模型由多個(gè)抽象的服務(wù)結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)服務(wù)群。同一服務(wù)群中的服務(wù)具有相同功能，不同的QoS。服務(wù)動(dòng)態(tài)選擇QoS全局最優(yōu)化問題即在組合流程模型執(zhí)行過程中，從各服務(wù)結(jié)點(diǎn)對(duì)應(yīng)的服務(wù)群中選擇具體的服務(wù)組成一個(gè)可執(zhí)行的服務(wù)鏈，使得服務(wù)鏈在滿足QoS約束的前提下，多個(gè)目標(biāo)(QoS參數(shù))達(dá)到最優(yōu)。服務(wù)組合中的服務(wù)動(dòng)態(tài)選擇QoS全局最優(yōu)化問題可轉(zhuǎn)化為一個(gè)求解服務(wù)組合流程圖(service composition graph,SCG)中帶QoS約束條件的多目標(biāo)最優(yōu)路徑問題，即SCG中的多約束條件下多目標(biāo)最優(yōu)路徑(MCOOP)求解問題[8]。本文研究并提出了求解該問題的DE-GODSS算法。

服務(wù)組合流程實(shí)際是一個(gè)基于Web服務(wù)的工作流，與工作流管理聯(lián)盟(WfMC)定義的4種基本模型(即串聯(lián)模型、并聯(lián)模型、選擇模型和循環(huán)模型)相對(duì)應(yīng)，大部分組合流程均可由這4種基本模型組合而成。基于4種基本模型的組合服務(wù)QoS參數(shù)、約減規(guī)則和QoS計(jì)算方法已有一些研究[3，5，8]。大多是計(jì)算基本模型的 QoS，通過恰當(dāng)?shù)木酆虾瘮?shù)將各結(jié)點(diǎn)的QoS合起來構(gòu)成組合服務(wù)的QoS。本文參考參考文獻(xiàn)[8]中的方法對(duì)4種模型進(jìn)行了表示和QoS參數(shù)的計(jì)算?？紤]Web服務(wù)的4種QoS參數(shù)，即執(zhí)行時(shí)間T、執(zhí)行費(fèi)用C、信譽(yù)等級(jí)Rep和可靠性R。設(shè)cs為組合服務(wù)，si為組合服務(wù)中的單個(gè)服務(wù)，則si和cs的服務(wù)質(zhì)量分別為

3 DE-GODSS算法

3.1 MCOOP問題的形式化描述

為方便說明，本文將組合服務(wù)的執(zhí)行時(shí)間和費(fèi)用作為兩目標(biāo)準(zhǔn)則，信譽(yù)等級(jí)和可靠性作為兩約束條件，Rep0和R0分別表示組合服務(wù)所要求的最低信譽(yù)等級(jí)和最低可靠性，則一個(gè)帶約束的多目標(biāo)服務(wù)組合優(yōu)化模型的形式化描述如下：

其中，P 為 Web服務(wù)組合方案，T(P)，C(P)，Rep(P)和 R(P)對(duì)應(yīng)服務(wù)組合流程的QoS參數(shù)計(jì)算式，根據(jù)參考文獻(xiàn)[8]中定義的服務(wù)組合模型QoS的聚合方法獲得；式(1)表示取向量極小化，即使T(P)和C(P)兩個(gè)目標(biāo)函數(shù)同時(shí)極小化。QoS參數(shù)的考慮并不限于這些，主要思想是將它們看作優(yōu)化模型的目標(biāo)函數(shù)或約束條件，故本模型可推廣到任意多個(gè)目標(biāo)函數(shù)和約束條件。

3.2 MCOOP問題轉(zhuǎn)化為單目標(biāo)問題

求解多目標(biāo)規(guī)劃的最基本方法為評(píng)價(jià)函數(shù)。它的基本思想是借助幾何或應(yīng)用中的直觀背景，構(gòu)造評(píng)價(jià)函數(shù)，將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，然后利用成熟的單目標(biāo)求解方法求出最優(yōu)解，并把這種最優(yōu)解當(dāng)作多目標(biāo)的最優(yōu)解。本文采用理想點(diǎn)法來構(gòu)造MCOOP問題的評(píng)價(jià)函數(shù)。

其中，（T*，C*）為一個(gè)理想點(diǎn)。理想點(diǎn)是對(duì) T(P)和 C(P)分別求出約束最優(yōu)值得到的，即：

對(duì)該多目標(biāo)服務(wù)組合優(yōu)化問題，根據(jù)組合服務(wù)QoS的聚合方法可知，在各服務(wù)群中均選擇執(zhí)行時(shí)間最短的服務(wù)形成的組合服務(wù)的執(zhí)行時(shí)間為T*；同理，在各服務(wù)群中均選擇執(zhí)行費(fèi)用最低的服務(wù)形成的組合服務(wù)的執(zhí)行費(fèi)用為C*。

3.3 DE-GODOSS算法設(shè)計(jì)

差異演化(DE)[9,10]算法是由Rainer Storn和Kenneth Price于1996年提出的一種優(yōu)化技術(shù)。它具有記憶個(gè)體最優(yōu)解和種群內(nèi)信息共享的特點(diǎn)，其基本思想是利用從種群中隨機(jī)選取的兩個(gè)個(gè)體的差向量作為第三者的隨機(jī)變化源，生成變異個(gè)體，然后變異個(gè)體和目標(biāo)個(gè)體通過交叉操作生成新個(gè)體。若新個(gè)體的適應(yīng)度優(yōu)于目標(biāo)個(gè)體，則新個(gè)體取代目標(biāo)個(gè)體進(jìn)入下一代；否則，目標(biāo)個(gè)體保留到下一代。因此，它主要包括4個(gè)基本步驟：種群初始化、變異操作、交叉操作和選擇操作。差異演化算法具有簡單易用、收斂速度快、控制參數(shù)少等特點(diǎn)，在各領(lǐng)域得到了廣泛的應(yīng)用[11]。

基于差異演化算法，對(duì)第 3.2節(jié)的優(yōu)化模型設(shè)計(jì)相應(yīng)參數(shù)。對(duì)于存在m個(gè)服務(wù)結(jié)點(diǎn)的組合服務(wù)流程，第i個(gè)服務(wù)結(jié)點(diǎn)對(duì)應(yīng)的服務(wù)群中有ni個(gè)服務(wù)，即SGi=(si,1,…,si,ni)(i=1,…，m)，為某個(gè)具體服務(wù)在該服務(wù)群中的編號(hào)。為第i個(gè)服務(wù)結(jié)點(diǎn)選擇一個(gè)具體的服務(wù)xk=sik，則組合服務(wù)方案構(gòu)成一個(gè) m 元組 Xi=(xi1,xi2,…，xim)，xik∈[1,nk]，每個(gè)元組對(duì)應(yīng)m維空間中的某一位置。

從Xi的編碼方式可看出，本文研究的組合優(yōu)化問題是離散型問題，方便差異演化算法的變異和交叉操作。在差異演化算法中，根據(jù)基向量、差向量個(gè)數(shù)及交叉方法的選擇不同，分為10種不同的變異策略組合[11]。本文結(jié)合組合服務(wù)的特點(diǎn)選擇DE/best/1/bin變異策略，其變異操作的計(jì)算式如式(5)所示：

其中，Xbest(t)表示第 t代種群中的最好個(gè)體；Xp1、Xp2是種群中隨機(jī)選出的兩個(gè)互不相同的個(gè)體，且i≠p1≠p2≠best。由此可知，該變異策略的種群規(guī)模必須大于4，否則無法進(jìn)行變異操作。Xp1(t)-Xp2(t)為差異化向量；F為縮放因子，用于控制差向量的影響大小，取值在[0,2]。本文的組合優(yōu)化問題屬于離散問題，因此取F=1。Hi(t)為產(chǎn)生的變異個(gè)體。

為增加種群的多樣性，差異演化算法將變異向量和目標(biāo)向量按如下式子進(jìn)行交叉：

其中，randij是在 [0,1]的隨機(jī)小數(shù)；CR為交叉概率，CR∈[0,1]；為在[1,m]的隨機(jī)整數(shù)，這種交叉策略可確保Vi(t)中至少有一位分量與目標(biāo)向量Xi(t)不同。

和其他演化算法一樣，差異演化也是通過“優(yōu)勝劣汰”的選擇操作來保證算法不斷向最優(yōu)解進(jìn)化。本文將式(3)作為最小化的目標(biāo)函數(shù)，則差異演化算法的選擇策略可由式(7)來表示：

通過以上描述的差異演化的變異、交叉和選擇操作使種群演化到下一代，反復(fù)循環(huán)演化，最后種群將達(dá)到最優(yōu)。因此，結(jié)合差異演化算法的優(yōu)化思想和服務(wù)組合中的動(dòng)態(tài)服務(wù)選擇問題，設(shè)計(jì)出求解MCOOP問題的DE-GODSS算法，算法的描述如下。

（1）將MCOOP問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，并設(shè)置算法相關(guān)控制參數(shù)。

（2）初始化種群 P(0)，t=0。

（3）計(jì)算種群 P(t)中每個(gè)個(gè)體的適應(yīng)度，并根據(jù)適應(yīng)度選擇出最優(yōu)個(gè)體。

（4）從種群P(t)中隨機(jī)選出與當(dāng)前個(gè)體不同的兩個(gè)個(gè)體。

（5）按式(5)進(jìn)行變異操作，生成變異向量。

（6）對(duì)變異向量按式(6)執(zhí)行交叉操作，生成新個(gè)體。

（7）計(jì)算新個(gè)體的適應(yīng)度，并與之前的最優(yōu)個(gè)體的適應(yīng)度比較。若優(yōu)于之前的最優(yōu)個(gè)體，則將當(dāng)前個(gè)體作為最優(yōu)個(gè)體。

（8）按式(7)執(zhí)行選擇操作。當(dāng)新個(gè)體的適應(yīng)度優(yōu)于目標(biāo)個(gè)體時(shí)，新個(gè)體代替目標(biāo)個(gè)體進(jìn)入下一代種群P(t+1)；否則，目標(biāo)個(gè)體繼續(xù)保留在下一代種群中。

（9）重復(fù)（4）到（8），直到種群中所有個(gè)體都執(zhí)行完畢。

（10）t=t+1。

（11）判斷是否滿足結(jié)束條件(迭代次數(shù))，不滿足則返回（4）。

在計(jì)算個(gè)體適應(yīng)度時(shí)，先將個(gè)體解碼成具體的組合服務(wù)方案，再判斷該方案是否滿足約束條件。若滿足，則按式(3)計(jì)算該個(gè)體的適應(yīng)度；否則，賦予該個(gè)體最差的一個(gè)適應(yīng)度。算法的時(shí)間復(fù)雜度主要由差異演化算法進(jìn)行迭代的時(shí)間復(fù)雜度組成。假設(shè)迭代次數(shù)為T，種群規(guī)模為N，服務(wù)結(jié)點(diǎn)數(shù)為m，則算法總的時(shí)間復(fù)雜度為O(TN2m)。整個(gè)算法過程的時(shí)間復(fù)雜度主要與迭代次數(shù)、種群規(guī)模和組合服務(wù)中的服務(wù)結(jié)點(diǎn)數(shù)有關(guān)，而與各服務(wù)結(jié)點(diǎn)對(duì)應(yīng)的服務(wù)群規(guī)模無關(guān)。而多目標(biāo)遺傳算法GODSS的總時(shí)間復(fù)雜度為O((mN2+NN*)T)，其中N*為輔助種群規(guī)模。因此，較已有的多目標(biāo)遺傳算法，本文設(shè)計(jì)的差異演化算法的時(shí)間復(fù)雜度較低，且無需另外設(shè)計(jì)輔助種群。GODSS算法在每次迭代賦予染色體適應(yīng)度時(shí)，需對(duì)個(gè)體之間的優(yōu)于關(guān)系進(jìn)行排序，增加了算法的時(shí)間復(fù)雜度，而本文采用理想點(diǎn)的方法很好地將多目標(biāo)向單目標(biāo)轉(zhuǎn)化，只需將個(gè)體適應(yīng)度同目標(biāo)個(gè)體的適應(yīng)度和最優(yōu)個(gè)體的適應(yīng)度比較即可。因此，從理論分析可知，DE-GODSS算法規(guī)則簡單，易于實(shí)現(xiàn)。在相同迭代次數(shù)下，算法的執(zhí)行時(shí)間更少，證明該算法的可行性。

4 仿真實(shí)驗(yàn)及分析

本節(jié)針對(duì)參考文獻(xiàn)[8]中的例子進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)的組合服務(wù)流程如圖1所示。

流程中的每個(gè)服務(wù)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)服務(wù)群，各服務(wù)群中服務(wù)的QoS參數(shù)在一定范圍內(nèi)隨機(jī)生成，并使用極差變換方法對(duì)其進(jìn)行標(biāo)準(zhǔn)化。對(duì)于信譽(yù)等級(jí)，利用模糊數(shù)學(xué)中隸屬度的方法進(jìn)行量化。根據(jù)服務(wù)組合流程基本模型以及QoS聚合方法，得到目標(biāo)函數(shù)和約束函數(shù)。由基本模型組合服務(wù)的QoS聚合方法可知，組合服務(wù)的可靠性約束不宜設(shè)置太大，故本章中設(shè)，Rep0=0.8,R0=0.5。第3節(jié)中，已從理論分析的角度分析了本文提出算法的時(shí)間復(fù)雜度優(yōu)于已有的多目標(biāo)遺傳算法，證明了該算法的可行性。進(jìn)一步地，本節(jié)實(shí)驗(yàn)通過比較算法的收斂速度來驗(yàn)證DE-GODSS算法的有效性。實(shí)驗(yàn)考慮各服務(wù)群規(guī)模為10個(gè)，種群規(guī)模為100個(gè)，迭代次數(shù)為100次，與多目標(biāo)遺傳算法GODSS比較每一代種群的平均適應(yīng)度。如圖2所示，發(fā)現(xiàn)DE-GODSS算法的收斂速度明顯優(yōu)于GODSS算法。GODSS算法在71代收斂到最優(yōu)值，而DE-GODSS算法在34代就已經(jīng)收斂到了最優(yōu)值，說明了DE-GODSS算法的有效性。

5 結(jié)束語

針對(duì)組合服務(wù)中QoS全局最優(yōu)動(dòng)態(tài)Web服務(wù)選擇問題，基于差異演化算法，提出并設(shè)計(jì)了求解該問題的DE-GODSS算法。將服務(wù)動(dòng)態(tài)選擇全局優(yōu)化問題轉(zhuǎn)化為一個(gè)帶QoS約束的多目標(biāo)服務(wù)組合優(yōu)化問題，通過理想點(diǎn)的方法將多目標(biāo)向單目標(biāo)轉(zhuǎn)化，利用差異演化算法的智能優(yōu)化原理進(jìn)行優(yōu)化，通過控制迭代次數(shù)，可產(chǎn)生多組滿足約束條件的優(yōu)化服務(wù)組合流程，能夠更好地滿足用戶的需求。理論分析和實(shí)驗(yàn)結(jié)果表明了該算法的可行性和有效性，該算法的時(shí)間復(fù)雜度和收斂速度優(yōu)于已有的多目標(biāo)遺傳算法。

1 Liu Y,Ngu A H,Zeng L Z.QoS computation and policing in dynamic Web service selection.In： Proceedings of the International World Wide Web Conference,ACM,Manhattan,NY,USA,2004

2 Casati F,Ilnicki S,Jin L J,et al.Adaptive and dynamic service composition in eFlow.In：12th InternationalConference on Advanced Information Systems Engineering，Stockholm,Sweden,2000

3 Zeng L,Benatallah B,Dumas M,et al.Quality driven Web services composition.In:Proceedings of the International World Wide Web Conference.ACM,Budapest,Hungary,2003

4 Ardagna D,Pernici B.Global and local QoS guarantee in Web service selection.In:Third Internation Conference on Business Process Management,Vienna,Austria,2006

5 Alrifai M,Risse T.Combining global optimization with local selection for efficient QoS-aware service composition.In:ACM,Madrid,Spain，2009

6 邢慶秀.支持QoS全局優(yōu)化的動(dòng)態(tài)Web服務(wù)組合問題研究.中國海洋大學(xué)碩士學(xué)位論文,2008

7 范小芹,蔣昌俊,方賢文等.基于離散微粒群算法的動(dòng)態(tài)Web服務(wù)選擇.計(jì)算機(jī)研究與發(fā)展,2010(1):147～156

8 劉書雷,劉云翔,張帆等.一種服務(wù)聚合中 QoS全局最優(yōu)服務(wù)動(dòng)態(tài)選擇算法.軟件學(xué)報(bào),2007,18(3):646～656

9 Storn R,Price K.Minimizing the real functions of the ICEC'96 contest by differential evolution.In：Proceedings of the IEEE Conference on Evolutionary Computation.Nagoya,Japan,1996

10 Storn R,Price K.Differential evolutionc¨a simple and efficient heuristic for global optimization over continuous spaces.Journal of Global Optimization,1997,11(4):341～359

11 武志峰.差異演化算法及其應(yīng)用研究.北京交通大學(xué)博士學(xué)位論文,2009