Ｗｅｂ服務組合中基于ＱｏＳ的改進型遺傳算法

收稿日期：2007-12-03；修回日期：2008-07-18

基金項目：國家科技支撐計劃資助項目（2007BAH08B04）; 國家“863”計劃資助項目（2006AA102233）;國家博士點基金資助項目（20050611027）；重慶市教委科技項目（KJ081701）

作者簡介：龔小勇（1970-），男，CCF高級會員，博士研究生，主要研究方向為Web服務、電子商務、服務質量（g_x_y_h_m@yahoo.com.cn）；朱慶生（1958-），男，教授，博導，主要研究方向為軟件工程、電子商務、圖像處理等；武春嶺（1975-），男，碩士，主要研究方向為面向服務的計算和Web服務組合*

（1. 重慶大學 計算機學院，重慶 400044；2. 重慶電子工程職業學院 計算機系，重慶 401331）

摘 要：提出了一種在Web服務組合中基于QoS的改進型遺傳算法。該算法通過計算個體間服務質量的海明距離提高了服務組合的質量；通過指定用戶總時間限制和實施優良解保留策略解決了算法運行時間對服務質量的影響問題。實驗結果表明了算法的有效性。

關鍵詞：服務質量；Web服務組合；海明距離；遺傳算法

中圖分類號：TP393

文獻標志碼：A

文章編號：1001-3695(2008)10-2922-03

Improved genetic algorithm based on QoS in Web services composition

GONG Xiao-yong¹，2，ZHU Qing-sheng¹，WU Chun-ling²

(1. School of Computer， Chongqing University， Chongqing 400044， China; 2. Dept. of Computer， Chongqing College of Electronic Enginee-ring， Chongqing 401331， China)

Abstract:This paper proposed an improved genetic algorithm based on QoS in the Web services composition. The algorithm improved the quality of the services composition by means of calculating Hamming distance of QoS among individuals; solved the problem that algorithm’s executive time impaired the QoS of services composition by prescribing a total time limit and implementing a fine solutions reservation strategy. The experimental results indicate the feasibility of this algorithm.

Key words：QoS; Web services composition; Hamming distance; genetic algorithm

Web服務作為目前最新穎的分布式計算模型，有力地整合了Internet上的各種資源。越來越多的企業將自己的應用程序作為Web服務發布，相應地，用戶對服務的功能和質量要求也越來越高，單個服務很難滿足用戶的實際需要，因此，服務組合成為必然。服務組合最有挑戰性的問題之一就是面向服務質量（QoS）的組合問題[1]。隨著Web服務數量的增多，出現了許多服務提供者提供的服務具有相同功能不同的QoS，因此，在服務組合過程中，需要根據用戶的QoS要求對Web服務進行選擇。目前服務組合的算法主要有窮盡計算法[2]、線性規劃法[3]、遺傳算法[4]等。文獻[4]針對在服務組合中出現的分支、循環、并發等情況，對服務組合的QoS屬性計算進行了分析，提出了使用遺傳算法進行服務選擇和再次選擇。但文獻[4]存在兩方面的問題：a)在計算個體的適應值時，未考慮個體的多樣性保持，使最終選擇的服務可能不是最優的；b)沒有考慮在服務執行過程中，服務再次選擇算法本身的執行時間給服務質量帶來的影響。為此，本文提出了在Web服務組合中基于QoS的改進型遺傳算法。

1 服務組合結構及QoS計算

Web服務組合的功能可以分成多個子功能，本文稱這些子功能為任務（task，簡稱t，是構成服務組合的基本邏輯單位，僅包含功能描述和接口信息，不指向具體的Web服務）。為了能有效地說明服務組合中的問題，本文引入初始虛擬任務和終止虛擬任務（兩個邏輯上存在、物理上不存在的任務）來標志一個服務組合邏輯上的開始和結束，這里分別用t0和tn＋1來表示。根據任務間的執行邏輯關系，本文使用狀態圖將服務組合劃分為如圖1所示的四種結構。其他大部分服務組合都可以由這四種基本結構復合而成。

下面是一個Web服務組合的例子，該服務組合由任務集合｛t0，t1，t2，t3，t4，t5，t6，t7｝組成。其結構如圖2所示。

由圖2可知，完成從初始任務到終止任務的組合功能，會存在多條組合路徑（composite path，簡稱cp，一條從起始任務到終止任務的任務組合方案），這些路徑在任務組成數量、組合順序上是不同的。例如t0，t1，t2，t3，t4，t5，t7和t0，t1，t2，t3，t3，t4，t6，t7是兩條不同的組合路徑，如圖3所示。

在服務組合過程中，每個任務會有多個候選服務（ser-vices，簡稱s，用來完成邏輯任務各項操作功能的具體Web服務）與之對應。這些服務由不同提供者提供，具有相同調用接口、相同功能和不同QoS屬性。因此，每條組合路徑又包含多個執行計劃（executive plan，簡稱ep，從組合路徑每個任務的候選服務中選取的，能完成組合路徑功能的一組服務組合方案）組成。執行計劃的QoS屬性可以通過上述四種基本結構的QoS屬性來獲取。

假設Web服務包括四種QoS屬性，即執行時間T（time）、執行費用C（cost）、可靠性R（reliability）和信譽等級Rep（reputation）。設ep是由多個服務組成的執行計劃，si為組成執行計劃的單個服務，si和ep的服務質量模型分別為Qsi=（Ti，Ci，Repi，Ri），Qep=（Tep，Cep，Repep，Rep）。服務組合基本結構的QoS屬性計算方法如下：

a）順序結構，如圖1（a）所示。Tep=∑ni=1Ti，Cep=∑ni=1Ci， Rep=∏ni=1Ri ，Repep=∑ni=1Repi/n

b）并行結構，如圖1（b）所示。Tep=max(T1，T2，…，Tn)， Cep=∑ni=1Ci， Rep=min(R1，R2，…，Tn)，

Repep=∑ni=1Repi/n

c）分支結構，如圖1（c）所示。∑ni=1pi=1， Tep=∑ni=1Tipi， Cep=∑ni=1Cipi ，Rep=∑ni=1Ripi，

Repep=∑ni=1Repipi

d）循環結構，如圖1（d）所示。Tep=k×∑vi=uTi， Cep=k×∑vi=uCi， Rep=∏ki=1∏vj=uRj，

Repep=∑vi=uRepi/(v-u+1)2 算法描述

在對服務組合問題建立結構模型后，必須構造相應的算法對問題進行優化求解。文獻[5]證明了服務組合問題屬于NP-complete問題。遺傳算法作為一種智能優化方法，具有并行計算、群體尋優的特點，不需要與應用背景相關的啟發式知識，只需要目標函數和相應適應值函數[6]。本文根據Web服務組合的特點，對傳統遺傳算法進行了改進，通過計算個體間服務質量的海明距離來實現多樣性保持，通過指定服務組合的總時間限制和優良解保留策略來處理算法本身的執行時間對服務組合質量的影響。

21 基因編碼

本文把任務ti定義為基因座，其個數與服務組合結構圖中的任務數相等（這樣做可以使算法一次執行就能完成所有路徑QoS最優的全局搜索[7]），所有基因座構成了個體的基本結構，每個基因座包含一個與對應任務相匹配的候選服務集，候選服務集的每個服務再指向表示QoS屬性的數組。由于每個個體的長度都相同，采用整數定長編碼的方式，個體中第一個（最后）基因總是服務組合的起點（終點），個體中間的每一個基因對應一個具體服務在候選服務集中的編號。其結構如圖4所示。

由于服務組合結構圖中可能存在分支結構，實際組合路徑包含的任務數只能少于或等于任務總數，再加上遺傳算法固有的隨機性，造成交叉或變異操作生成的新個體可能不代表任何現有的組合路徑。因此，本文采用文獻[7]的關系矩陣參與遺傳操作。關系矩陣的主對角線元素表示個體，其他元素表示任務間的位置關系。在進行交叉與變異操作時，需要根據關系矩陣中任務間的位置關系檢查新生成個體的路徑合法性。

22 算法過程描述

算法從QoS全局最優的角度出發，搜索所有執行計劃中滿足約束條件的一組非劣解。主要過程是：將每一個執行計劃編碼為一個個體，通過個體之間的交叉、變異等重組操作，產生具有更高目標函數值的新個體，該過程不斷進行，實現在解空間的并行全局搜索；搜索停止時，得到一個個體集合，即滿足約束條件的優化或近似優化的執行計劃集。具體流程見算法1。

算法1 主控程序

輸入：種群P及輔助種群Pa的規模，進化代數N

輸出：QoS全局最優的服務組合P*

a) t←0

b) Initialize (P(t))

c) Pa(t)←

d) While(t

e) FitnessEvaluate (P(t))

f) Pa(t+1)←FineReserve(P(t)，Pa(t))

g) Pm(t)←MateSelect(P(t)， Pa(t+1))

h) P(t+1)←Evolove(Pm(t))

i) t←t+1

j) Endwhile

k) P*←OptimalSelect (Pa(t))

其中：步驟b）按隨機方法進行初始種群的生成；e）進行個體適應值的計算和多樣性保持，參見第2.3節；f）利用種群P輔助種群Pa進行優良解保留，參見第2.4節；g）采用輪盤賭選擇方式從種群P中選擇優勢個體，與輔助種群Pa中的個體混合后賦予交配池；h）執行交叉和變異操作，產生新的個體作為新種群，根據前面的編碼規則，執行計劃的任務數可能小于個體的長度，因此，對于交叉和變異操作必須由關系矩陣來判斷其合法性。本文采用兩點交叉的方法來加快算法收斂的速度，變異位置的選擇應該是除了t0和tn+1以外的其他基因位。由于初始種群采用隨機方法產生，初始種群的多樣性受到限制，進化過程中的空間搜索能力完全取決于交叉和變異操作。交叉概率和變異概率取值不可過低，交叉概率可取1，變異概率可取0.09。步驟k）在輔助種群的優良解中選擇一個最優解P*作為結果輸出。

23 個體適應值的計算和多樣性保持

適應度評價是遺傳操作的依據，其中目標函數的設計直接影響到遺傳算法的性能。根據QoS模型，筆者得出目標函數f(x)的計算公式為

f(x)=（wRRep+wRepRepep）/（wTTep+wcCep）（1）

其中：Tep、Cep、 Rep、Repep都是經歸一化后的QoS屬性值；wT、wC、wR、wRep分別是對應的權值，表示用戶對QoS屬性的關注程度，并且wT+wC+wR+wRep=1。

按照進化理論，總是希望選擇其中具有較高質量的個體參與后續遺傳操作。本文采用兩個步驟進行個體適應值的計算：a)基于目標函數式（1）對整個群體中的個體進行排序，得到排序值；b)通過個體的多樣性保持策略對個體的排序結果進行修正，得到群體中每個個體的適應值。

常用的多樣性保持策略是小生境技術[8]。其主要思想是利用共享函數來限制相似個體的選擇概率。但是小生境技術對小生境半徑σshare非常敏感，σshare的略微偏移會導致共享函數取值的極大偏差，因此，本文采用基于個體間海明距離來保持群體的多樣性，它不存在參數的估算和敏感問題。適應值的計算過程見算法2。

算法2 FitnessEvaluate

輸入：第t代種群P(t)

輸出：P(t)的適應值Fitness

a) S←

b) S←Sort(f(x))

c) for each xi∈P(t) ∧ xi≠xj do

d)m←0

e)for each xj∈P(t) ∧xi≠xj do

f)disij←∑Lenk=1(xik-xjk)²

g)if disij

h)m←m+1

i)Deni←m/N

j)Fitnessi←1/Si×Deni

k) Output Fitnessi

其中：步驟b）對目標函數值排序，得到個體的排序值；步驟f）計算個體xi與xj的海明距離，Len為QoS屬性的個數；步驟i）計算個體xi在群體中的密度Deni；步驟j）進行個體適應值的計算，適應值的計算要服從極大化原則，即大適應值的個體具有較高的繁殖概率。

24 優良解保留

在動態環境中，由于環境的變化，已經選出的服務可能在執行時不再可用或QoS屬性出現大的改變，這時需要對剩余的未執行服務進行再次選擇（即重計劃），以使服務組合繼續執行并保持較高的服務質量。考慮到重計劃的經常性、隨機性，以及它本身占用的時間，用戶往往對總執行時間（從服務選擇開始到所有服務執行完畢的時間）有一定的要求，如要求總執行時間不超過T0，服務執行過程中一旦需要對服務組合進行重計劃，則需要考慮算法本身占用的執行時間T ga。如果從服務組合開始執行到服務執行完畢總共進行了k次重計劃，則服務組合所用的執行時間可以表示為T=∑ki=1(Ti+Tiga)+Tend（2）其中：Ti表示組合服務從第i-1次重計劃完畢到第i次重計劃發生時刻的時間差;T1是從組合服務開始執行到發生第一次重計劃的時間差;Tend是從最后一次重計劃完畢后到服務執行結束的時間差;Tiga表示第i次重計劃占用的時間。

經過多次重計劃，服務組合執行過程中總的T ga隨著算法的運行逐漸變大。為了保證服務組合所用的執行時間T小于用戶的時間限制T0，本文引入輔助種群對當前適應值大的滿足時間限制的優良解個體實施保留。因此，把優良解加入到輔助種群時，需要檢查輔助種群集合是否已滿，是否已有該個體。如果集合未滿，則加入新的個體；如果集合已滿，檢查集合中的個體是不是已經不滿足總時間T0限制了。如果存在個體不滿足時間限制T0，就使用新的個體代替T最大的舊個體；如果所有個體都滿足時間限制，則代替適應值最低的個體。

3 實驗及分析

針對圖2的Web服務組合情況，通過實驗對本文算法進行了有效性驗證。實驗環境為100 Mbps局域網，計算機配置為P4處理器，2 GB內存，Windows Server操作系統，算法用Java實現。Web服務的QoS屬性信息通過分類tModel在集中式UDDI注冊中心進行注冊。

3. 1 多樣性保持實驗及分析

假設計算個體間服務質量的海明距離進行種群多樣性保持的方法為H算法，否則為NH算法。圖5為在候選服務規模為25的情況下，H與NH算法分別迭代50、100、150、200代的運行時間比較。從圖5可以看出，因為種群多樣性策略的加入，H算法的時間開銷要大于NH。圖6為在候選服務規模為25、在不同進化代數下，H與NH算法所得的目標函數值分布情況。可以看出，H算法雖然計算復雜性高一些，但其得到的目標函數值更大，所求得的最優解性能要優于NH。

3. 2 優良解保留實驗及分析

為了確保服務組合在規定時間內能執行完畢，本文給出了總運行時間限制T0。圖7是在服務數為25、迭代數為150的情況下，分別指定不同T0，獲得的帶T0執行時間和不帶T0執行時間的12個樣本數據。由圖7可以看出，通過優良解保留，能夠保證執行時間在限制范圍以內，說明了本文算法的有效性。

4 結束語

Web服務以其特有優勢使人們看到其廣泛的應用前景，而支持QoS的Web服務組合的有效解決將為Web服務的普及起到有力的推動作用，使Web服務由一種技術轉換為真正可以被人們使用的工具。本文提出的基于QoS的改進型遺傳算法通過個體多樣性保持使最終選出的執行計劃具有較大的目標函數值，能最大限度地滿足用戶的QoS需求。另外，本文注意了算法本身的執行時間對服務組合質量的影響，通過指定總執行時間限制和優良解保留策略解決了這個問題。最后通過實驗對算法進行了驗證，實驗結果證明了算法的有效性。今后需要對算法的自適應性、遺傳搜索動態終止條件等方面的內容進行深入研究。

參考文獻：

[1]岳昆， 王曉玲， 周傲英. Web 服務核心支撐技術:研究綜述[J]. 軟件學報， 2004， 15(3):428-442.

[2]代鈺， 楊雷， 張斌， 等. 支持組合服務選取的QoS模型及優化求解[J]. 計算機學報， 2006，29(7):1167-1178.

[3]ZENG Liang-zhao ， BENATALLAH B， NGU A H H， et al. QoS-aware middleware for Web services composition[J]. IEEE Trans on Software Engineering， 2004， 30(5): 311-327.

[4]CANFORA G， DI PENTA M， ESPOSITO R， et al. A lightweight approach for QoS-aware service composition[C]//Proc of ICSOC. New York: [s.n.]， 2004:36-47.

[5]CAREY M R， JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. New York: W.H.Freeman and Company， 1999.

[6]袁亞湘， 孫文瑜. 最優化理論與方法[M]. 北京: 科學出版社， 2001.

[7]張成文， 蘇森， 陳俊亮. 基于遺傳算法的QoS感知的Web服務選擇[J]. 計算機學報， 2007，29(7):1029-1037.

[8]王小平， 曹立明. 遺傳算法——理論、應用與軟件實現[M]. 西安: 西安交通大學出版社， 2002.