基于差異演化算法的QoS全局最優(yōu)動態(tài)Web服務選擇*

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

（湖南科技大學知識處理與網(wǎng)絡化制造湖南省普通高校重點實驗室 湘潭 411201）

1 引言

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

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

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

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

·由于加權和的結果不僅對權重敏感，而且用戶需要對問題有一定的認識，使得加權的方法在實際應用中不可行；

·產生的優(yōu)化結果為單個解，用戶沒有選擇的余地；

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

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

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

2 服務組合問題

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

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

3 DE-GODSS算法

3.1 MCOOP問題的形式化描述

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

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

3.2 MCOOP問題轉化為單目標問題

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

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

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

3.3 DE-GODOSS算法設計

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

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

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

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

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

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

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

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

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

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

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

（4）從種群P(t)中隨機選出與當前個體不同的兩個個體。

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

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

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

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

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

（10）t=t+1。

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

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

4 仿真實驗及分析

本節(jié)針對參考文獻[8]中的例子進行仿真實驗，實驗的組合服務流程如圖1所示。

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

5 結束語

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

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)化的動態(tài)Web服務組合問題研究.中國海洋大學碩士學位論文,2008

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

8 劉書雷,劉云翔,張帆等.一種服務聚合中 QoS全局最優(yōu)服務動態(tài)選擇算法.軟件學報,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 武志峰.差異演化算法及其應用研究.北京交通大學博士學位論文,2009