Ｗｅｂ服務(wù)組合中基于ＱｏＳ的改進(jìn)型遺傳算法

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

基金項(xiàng)目：國家科技支撐計(jì)劃資助項(xiàng)目（2007BAH08B04）; 國家“863”計(jì)劃資助項(xiàng)目（2006AA102233）;國家博士點(diǎn)基金資助項(xiàng)目（20050611027）；重慶市教委科技項(xiàng)目（KJ081701）

作者簡(jiǎn)介：龔小勇（1970-），男，CCF高級(jí)會(huì)員，博士研究生，主要研究方向?yàn)閃eb服務(wù)、電子商務(wù)、服務(wù)質(zhì)量（g_x_y_h_m@yahoo.com.cn）；朱慶生（1958-），男，教授，博導(dǎo)，主要研究方向?yàn)檐浖こ獭㈦娮由虅?wù)、圖像處理等；武春嶺（1975-），男，碩士，主要研究方向?yàn)槊嫦蚍?wù)的計(jì)算和Web服務(wù)組合*

（1. 重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044；2. 重慶電子工程職業(yè)學(xué)院 計(jì)算機(jī)系，重慶 401331）

摘 要：提出了一種在Web服務(wù)組合中基于QoS的改進(jìn)型遺傳算法。該算法通過計(jì)算個(gè)體間服務(wù)質(zhì)量的海明距離提高了服務(wù)組合的質(zhì)量；通過指定用戶總時(shí)間限制和實(shí)施優(yōu)良解保留策略解決了算法運(yùn)行時(shí)間對(duì)服務(wù)質(zhì)量的影響問題。實(shí)驗(yàn)結(jié)果表明了算法的有效性。

關(guān)鍵詞：服務(wù)質(zhì)量；Web服務(wù)組合；海明距離；遺傳算法

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)志碼：A

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

1 服務(wù)組合結(jié)構(gòu)及QoS計(jì)算

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

下面是一個(gè)Web服務(wù)組合的例子，該服務(wù)組合由任務(wù)集合｛t0，t1，t2，t3，t4，t5，t6，t7｝組成。其結(jié)構(gòu)如圖2所示。

由圖2可知，完成從初始任務(wù)到終止任務(wù)的組合功能，會(huì)存在多條組合路徑（composite path，簡(jiǎn)稱cp，一條從起始任務(wù)到終止任務(wù)的任務(wù)組合方案），這些路徑在任務(wù)組成數(shù)量、組合順序上是不同的。例如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所示。

在服務(wù)組合過程中，每個(gè)任務(wù)會(huì)有多個(gè)候選服務(wù)（ser-vices，簡(jiǎn)稱s，用來完成邏輯任務(wù)各項(xiàng)操作功能的具體Web服務(wù)）與之對(duì)應(yīng)。這些服務(wù)由不同提供者提供，具有相同調(diào)用接口、相同功能和不同QoS屬性。因此，每條組合路徑又包含多個(gè)執(zhí)行計(jì)劃（executive plan，簡(jiǎn)稱ep，從組合路徑每個(gè)任務(wù)的候選服務(wù)中選取的，能完成組合路徑功能的一組服務(wù)組合方案）組成。執(zhí)行計(jì)劃的QoS屬性可以通過上述四種基本結(jié)構(gòu)的QoS屬性來獲取。

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

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

b）并行結(jié)構(gòu)，如圖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）分支結(jié)構(gòu)，如圖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）循環(huán)結(jié)構(gòu)，如圖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 算法描述

在對(duì)服務(wù)組合問題建立結(jié)構(gòu)模型后，必須構(gòu)造相應(yīng)的算法對(duì)問題進(jìn)行優(yōu)化求解。文獻(xiàn)[5]證明了服務(wù)組合問題屬于NP-complete問題。遺傳算法作為一種智能優(yōu)化方法，具有并行計(jì)算、群體尋優(yōu)的特點(diǎn)，不需要與應(yīng)用背景相關(guān)的啟發(fā)式知識(shí)，只需要目標(biāo)函數(shù)和相應(yīng)適應(yīng)值函數(shù)[6]。本文根據(jù)Web服務(wù)組合的特點(diǎn)，對(duì)傳統(tǒng)遺傳算法進(jìn)行了改進(jìn)，通過計(jì)算個(gè)體間服務(wù)質(zhì)量的海明距離來實(shí)現(xiàn)多樣性保持，通過指定服務(wù)組合的總時(shí)間限制和優(yōu)良解保留策略來處理算法本身的執(zhí)行時(shí)間對(duì)服務(wù)組合質(zhì)量的影響。

21 基因編碼

本文把任務(wù)ti定義為基因座，其個(gè)數(shù)與服務(wù)組合結(jié)構(gòu)圖中的任務(wù)數(shù)相等（這樣做可以使算法一次執(zhí)行就能完成所有路徑QoS最優(yōu)的全局搜索[7]），所有基因座構(gòu)成了個(gè)體的基本結(jié)構(gòu)，每個(gè)基因座包含一個(gè)與對(duì)應(yīng)任務(wù)相匹配的候選服務(wù)集，候選服務(wù)集的每個(gè)服務(wù)再指向表示QoS屬性的數(shù)組。由于每個(gè)個(gè)體的長(zhǎng)度都相同，采用整數(shù)定長(zhǎng)編碼的方式，個(gè)體中第一個(gè)（最后）基因總是服務(wù)組合的起點(diǎn)（終點(diǎn)），個(gè)體中間的每一個(gè)基因?qū)?yīng)一個(gè)具體服務(wù)在候選服務(wù)集中的編號(hào)。其結(jié)構(gòu)如圖4所示。

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

22 算法過程描述

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

算法1 主控程序

輸入：種群P及輔助種群Pa的規(guī)模，進(jìn)化代數(shù)N

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

23 個(gè)體適應(yīng)值的計(jì)算和多樣性保持

適應(yīng)度評(píng)價(jià)是遺傳操作的依據(jù)，其中目標(biāo)函數(shù)的設(shè)計(jì)直接影響到遺傳算法的性能。根據(jù)QoS模型，筆者得出目標(biāo)函數(shù)f(x)的計(jì)算公式為

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

其中：Tep、Cep、 Rep、Repep都是經(jīng)歸一化后的QoS屬性值；wT、wC、wR、wRep分別是對(duì)應(yīng)的權(quán)值，表示用戶對(duì)QoS屬性的關(guān)注程度，并且wT+wC+wR+wRep=1。

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

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

算法2 FitnessEvaluate

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

輸出：P(t)的適應(yīng)值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）對(duì)目標(biāo)函數(shù)值排序，得到個(gè)體的排序值；步驟f）計(jì)算個(gè)體xi與xj的海明距離，Len為QoS屬性的個(gè)數(shù)；步驟i）計(jì)算個(gè)體xi在群體中的密度Deni；步驟j）進(jìn)行個(gè)體適應(yīng)值的計(jì)算，適應(yīng)值的計(jì)算要服從極大化原則，即大適應(yīng)值的個(gè)體具有較高的繁殖概率。

24 優(yōu)良解保留

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

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

3 實(shí)驗(yàn)及分析

針對(duì)圖2的Web服務(wù)組合情況，通過實(shí)驗(yàn)對(duì)本文算法進(jìn)行了有效性驗(yàn)證。實(shí)驗(yàn)環(huán)境為100 Mbps局域網(wǎng)，計(jì)算機(jī)配置為P4處理器，2 GB內(nèi)存，Windows Server操作系統(tǒng)，算法用Java實(shí)現(xiàn)。Web服務(wù)的QoS屬性信息通過分類tModel在集中式UDDI注冊(cè)中心進(jìn)行注冊(cè)。

3. 1 多樣性保持實(shí)驗(yàn)及分析

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

3. 2 優(yōu)良解保留實(shí)驗(yàn)及分析

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

[2]代鈺， 楊雷， 張斌， 等. 支持組合服務(wù)選取的QoS模型及優(yōu)化求解[J]. 計(jì)算機(jī)學(xué)報(bào)， 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]袁亞湘， 孫文瑜. 最優(yōu)化理論與方法[M]. 北京: 科學(xué)出版社， 2001.

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

[8]王小平， 曹立明. 遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M]. 西安: 西安交通大學(xué)出版社， 2002.