基于NicheGA和FPN的獨(dú)立全局約束Web服務(wù)組合優(yōu)化方法

馮英華，許志才，王 娟

（1.安徽理工大學(xué) 理學(xué)院，安徽 淮南232001；2.滁州學(xué)院 數(shù)學(xué)系，安徽 滁州239012；3.淮南聯(lián)合大學(xué) 基礎(chǔ)部，安徽 淮南232001）

基于NicheGA和FPN的獨(dú)立全局約束Web服務(wù)組合優(yōu)化方法

馮英華1，3，許志才2，王 娟1

（1.安徽理工大學(xué) 理學(xué)院，安徽 淮南232001；2.滁州學(xué)院 數(shù)學(xué)系，安徽 滁州239012；3.淮南聯(lián)合大學(xué) 基礎(chǔ)部，安徽 淮南232001）

針對獨(dú)立全局約束Web服務(wù)組合問題，本文提出了利用模糊Petri網(wǎng)（FPN）來建模，將尋找可行的服務(wù)組合問題轉(zhuǎn)化為尋找FPN模型中可發(fā)生序列問題，從而把求解最佳服務(wù)組合問題轉(zhuǎn)化為在FPN模型中尋找信任值最大的合法發(fā)生序列問題.然后利用小生境遺傳算法（NicheGA）來尋找最優(yōu)合法序列，以獲得最優(yōu)的組合服務(wù)。最后實(shí)驗(yàn)仿真結(jié)果表明該方法既減少了計算時間又能找出更多的最優(yōu)解。

模糊Petri網(wǎng)，小生境遺傳算法，Web服務(wù)組合，優(yōu)化

0 引言

目前，服務(wù)組合已成為一個研究熱點(diǎn).組合方法可分為人工合成，半自動合成和全自動合成［7］.由于人工合成不能很好地滿足現(xiàn)實(shí)的期望，而全自動合成的過程又非常復(fù)雜，所以大部分關(guān)于服務(wù)組合的應(yīng)用和研究都是半自動合成.一個服務(wù)發(fā)現(xiàn)的方法要么面向句法要么面向語義.而面向語義的方法的服務(wù)查全率比面向語法的方法要高［8］.

在使用者的要求［5］中，用約束條件來準(zhǔn)確描述需要找的服務(wù).一般有兩種類型：局部約束和全局約束.前者是用來約束單個服務(wù)，比如購買聯(lián)想電腦，那么聯(lián)想電腦就是局部約束，后者是用來約束多個服務(wù)，比如買電腦時，買家收到電腦的時間≤電腦上保險的時間≤電腦組裝時間，這就是全局約束.全局約束可分為嚴(yán)格依賴條件和嚴(yán)格獨(dú)立條件.一個全局約束是依賴的，如果一旦其中的一個屬性被賦值，那么所有剩下的受限制屬性的值都能唯一確定.滿足嚴(yán)格依賴全局約束的組合問題可以用多項(xiàng)式時間［9］的方法容易得解決.

任何全局約束不是嚴(yán)格依賴就是嚴(yán)格獨(dú)立的，而本文研究的是嚴(yán)格獨(dú)立全局約束下的Web服務(wù)組合問題.

1 基本概念

本文將基于模糊Petri網(wǎng)推理來解決Web服務(wù)組合問題.因此，首先介紹一些模糊Petri網(wǎng)的相關(guān)概念.

定義1FPN是一個八元組［2］：FPN＝（P，T，D，I，O，f，α，β），

其中：

P＝｛P1，P2，…，Pn｝是庫所節(jié)點(diǎn)的有限集合，用來表示模糊命題；

T＝｛T1，T2，…，Tn｝是變遷節(jié)點(diǎn)的有限集合，用來表示規(guī)則的實(shí)現(xiàn)；

D＝｛d1，d2，…，dn｝是一個有限命題的集合；

｜P｜＝｜D｜；

I：T→P∞是一個輸入函數(shù)，映射一個變遷到它的輸入庫所集合；

O：T→P∞是一個輸出函數(shù)，映射一個變遷到它的輸出庫所集合；

f：T→［0，1］是一個函數(shù)，映射變遷到一個0～1的數(shù)值，用來表示變遷對應(yīng)的推理規(guī)則置信度（Confidence Factor）；

α：P→［0，1］是一個函數(shù)，映射庫所到一個0～1的數(shù)值，用來表示該庫所對應(yīng)的命題成立的真實(shí)度，即

β：P→D是一個函數(shù)，映射庫所對應(yīng)的命題，即

當(dāng)用FPN進(jìn)行模糊推理時，一個庫所表示一個命題，一個變遷表示一條模糊推理規(guī)則，即兩個命題之間的因果關(guān)系.每個變遷有一個置信度，表示推理規(guī)則的可信度.

圖1 基本FPN推理過程

圖2 類型1的FPN推理過程

圖3 類型2的FPD推理過程

圖4 類型3的FPN推理過程

FPN的基本推理規(guī)則的形式是［2］：

Ri：IFdfTHENdk（CF＝ui），這里df，dk是兩個命題。推理過程可以建模為圖1，其中命題df，dk用庫所pf和pk表示，命題df的真實(shí)度為αf.命題之間的因果關(guān)系用變遷ti表示，它的置信度為ui.當(dāng)變遷觸發(fā)后，命題pk的真實(shí)度為αf×ui.一條推理規(guī)則若包含“and”或者“or”連接符，就稱為組合產(chǎn)生式規(guī)則.組合產(chǎn)生式規(guī)則被分為基本的3類：

類型1：Ifdf1anddf2and…dfnThendk（CF＝ui），這dfk（1≤k≤n）∈D。推理過程可以建模為圖2，推理后命題dk的真實(shí)度是 min（αf1，αf2，…，αfn）×ui。

類型2：IfdfThendk1anddk2and…dkn（CF＝ui），這里dki（1≤i≤n）∈D，推理過程可以建模為圖3。

類型3：Ifdf1ordf2or…dfnThendk（CF＝ui），這dfk（1≤k≤n）∈D，推理過程可以建模為圖4.

2 基于FPN的服務(wù)組合模型的建立

本文采用FPN對獨(dú)立全局約束的服務(wù)組合進(jìn)行建模.服務(wù)組合的FPN模型中庫所代表服務(wù)，變遷代表全局約束條件，變遷的置信度代表該變遷前集所代表的服務(wù)對變遷后集所代表的服務(wù)的信任值.服務(wù)組合的獲得包含三個階段：候選服務(wù)的獲得，約束條件的識別和最優(yōu)組合的獲得.基于獨(dú)立全局約束服務(wù)組合的FPN建模過程如下：

（1）先找到候選服務(wù)［1］，用庫所來表示它們，然后把具有相同功能性質(zhì)的候選服務(wù)放在同一水平線上.

（2）服務(wù)間的獨(dú)立全局約束條件用變遷來表示.若兩個服務(wù)間存在獨(dú)立全局約束條件，則在它們和變遷之間用弧線連接.變遷的置信度表示該變遷前集所代表的服務(wù)對它后集所代表的服務(wù)的信任值.

（3）利用（1）和（2）得到獨(dú)立全局約束服務(wù)組合的模型.那么尋找可行的服務(wù)組合問題即可轉(zhuǎn)化為尋找FPN模型的可發(fā)生序列問題.從而最佳服務(wù)組合也就是模型中信任值最大的可發(fā)生序列.

3 基于小生境遺傳服務(wù)組合最優(yōu)化算法

本文充分利用FPN模型，對FPN模型中的變遷進(jìn)行編碼［5］.具體而言，文中將發(fā)生序列作為染色體，每個可發(fā)生序列代表可行的Web服務(wù)組合.這樣尋找可行的服務(wù)組合問題即可轉(zhuǎn)化為尋找FPN模型的可發(fā)生序列問題.如果只是用FPN來做組合問題，當(dāng)組合規(guī)模相當(dāng)大的時候會非常復(fù)雜.如果只采用GA，那么搜索具有相當(dāng)大的隨機(jī)性［5］，所以文中的方法將兩者結(jié)合起來同時考慮，這樣既降低了計算的復(fù)雜性又降低了搜索的隨機(jī)性.

遺傳算法［4］是模擬自然界生物群體進(jìn)化過程的一種隨機(jī)優(yōu)化方法，具有不依賴于問題模型的特性、尋優(yōu)過程的自適應(yīng)性、隱含的并行性以及解決復(fù)雜非線性問題的魯棒性等優(yōu)點(diǎn)，并在許多復(fù)雜優(yōu)化問題都找到了令人滿意的解。但大量的經(jīng)驗(yàn)表明，標(biāo)準(zhǔn)遺傳算法存在早熟收斂現(xiàn)象和后期搜索速度慢的缺點(diǎn)［3］.在大量的實(shí)際優(yōu)化問題的求解計算中，不僅要求在可行域內(nèi)尋找全局最優(yōu)解，而且往往需要搜索多個全局最優(yōu)解和有意義的局部最優(yōu)解，從而為決策者提供多種選擇或者多方面的信息。為了能夠搜索到全部全局最優(yōu)解和盡量多的局部最優(yōu)解，本文采用的是基于FPN和NicheGA的獨(dú)立全局約束服務(wù)組合的最優(yōu)化方法，算法如下：

（1）染色體編碼

設(shè)置進(jìn)化代數(shù)計數(shù)器t←1，給定一距離L.在FPN模型中，如果存在一組發(fā)生序列σ＝t1t2…tn－1tn，使得M0［σ＞Mf，且σ是滿足組合服務(wù)要求的可發(fā)生序列，那么就將σ當(dāng)成一個染色體，其中M0是初始序列，Mf是末序列，t1，t2…tn－1，tn∈T.

根據(jù)服務(wù)進(jìn)程的要求，隨機(jī)選擇M個滿足條件的可發(fā)生序列作為初始群體P（t）.

（2）個體評價

根據(jù)FPN的推理規(guī)則可以計算出每個染色體σ的信任值TD（σ），TD（σ）＝f（t1）f（t2）…f（tn），因?yàn)?NicheGA要求越優(yōu)的解具有的適應(yīng)度越大［6］，所以適應(yīng)度函數(shù)定義為：

（3）根據(jù)各個可行序列的適應(yīng)度對其進(jìn)行降序排序，記憶前N個可行序列（N＜M）.

（4）選擇運(yùn)算

對群體進(jìn)行單點(diǎn)交叉運(yùn)算，步驟如下：

1）對群體中的可發(fā)生序列進(jìn)行兩兩隨機(jī)配對。

2）對每一對相互配對的可發(fā)生序列，隨機(jī)設(shè)置某一變遷之后的位置為交叉點(diǎn).

3）對每一對相互配對的可發(fā)生序列，按照設(shè)定的交叉概率pc在其交叉點(diǎn)處相互交換部分變遷序列，從而產(chǎn)生出兩個新的變遷序列.

4）按照FPN推理規(guī)則，檢驗(yàn)由3）產(chǎn)生的新變遷序列是否為可行序列，若是則保留，否則排除.

（6）變異運(yùn)算

對群體進(jìn)行均勻變異運(yùn)算，步驟如下：

“天色已晚，回去吧?！苯洗沽?，楊公子一身白衣在前，我走在他身后，耳邊飄來戲臺上的唱曲“錯！錯！錯！”

1）依次指定發(fā)生序列中的每個變遷為變異點(diǎn).

2）對每個變異點(diǎn)，以變異概率pm從對應(yīng)變遷的取值范圍內(nèi)取另一變遷來替代原有變遷，從而得到新的變遷序列.

3）檢驗(yàn)由2）產(chǎn)生的新變遷序列是否為可行序列，若是則保留，否則排除.

（7）小生境淘汰運(yùn)算

將第（6）步得到的M個發(fā)生序列和第（3）步所記憶的N個發(fā)生序列合并在一起，得到一個含有M＋N個可行序列的新群體；對這M＋N個可行序列，按照下式求出每兩個可行序列σ和σ＊之間的海明距離，其中是不同屬性的候選服務(wù)的個數(shù)：

其中f是用來表示變遷對應(yīng)的推理規(guī)則置信度.

當(dāng)‖σ－σ＊‖＜L時，比較個體σ和個體σ＊的適應(yīng)度大小，并對其適應(yīng)度較低的個體處以罰函數(shù)，F(xiàn)min（σ，σ＊）＝10－3.從而在L內(nèi)只保留一個優(yōu)良的可行序列。

（8）依據(jù)這M＋N個發(fā)生序列的新適應(yīng)度對各個序列進(jìn)行降序排序，記憶前N個可行序列.

（9）終止條件判斷.若不滿足終止條件，則：更新進(jìn)化代數(shù)計數(shù)器t←t＋1，并將第（8）步排序中的前 M個發(fā)生序列作為新的下一代群體，然后轉(zhuǎn)到第（4）步；若滿足終止條件，則：輸出計算結(jié)果，算法結(jié)束.

4 實(shí)驗(yàn)仿真結(jié)果

本文提出了基于FPN和NicheGA的獨(dú)立全局約束服務(wù)組合優(yōu)化方法，這種方法不僅利用了FPN在描述多屬性混合約束問題上的優(yōu)越性，而且充分利用了Petri網(wǎng)的特點(diǎn).理論上，這種方法對分析獨(dú)立全局約束服務(wù)組合問題是有效的.既避免了Petri網(wǎng)組合的復(fù)雜性又避免了GA的隨機(jī)性和早熟收斂現(xiàn)象等缺陷.接下來，我們利用實(shí)驗(yàn)仿真來分析該方法的可行性.具體步驟如下：

（1）在服務(wù)庫里寄存大量的服務(wù)，個數(shù)為50至500；

（2）設(shè)置服務(wù)的功能和約束條件，每個服務(wù)包括3到7個服務(wù)組件；

（3）實(shí)驗(yàn)仿真平臺為 Winxp，Dell optiplex320，內(nèi)存1G，L＝0.001Matlab6.5.

對于一個給定的服務(wù)要求，分別利用GA＆APN和NicheGA＆FPN方法，我們從服務(wù)庫中找出可行的候選服務(wù)，然后在不同的候選服務(wù)數(shù)量下比較它們的時間效率和查找可行解的比率.

圖5 兩種算法時間比較

在圖5中，橫坐標(biāo)表示服務(wù)的數(shù)量，縱坐標(biāo)表示兩種方法的執(zhí)行時間，由圖中可以看出本文的方法比GA＆APN方法的時間效率高.而且隨著服務(wù)數(shù)量的增多，這種優(yōu)勢越明顯.

圖6 兩種算法的查找可行解的比率比較

在圖6中，橫坐標(biāo)表示服務(wù)數(shù)量，縱坐標(biāo)表示兩種方法的查找可行解比率.可行解比率是指找到的可行服務(wù)的數(shù)量與所有可行服務(wù)的數(shù)量的比值.由圖可以看出本文的方法比NG＆APN方法的可行解比率遠(yuǎn)比APN方法要高.

5 總結(jié)

研究獨(dú)立全局約束服務(wù)組合問題，現(xiàn)有的方法有Greedy、Approximating和GA＆APN.前兩種方法雖然它們在解決約束問題上有很好的效果，但是對于處理多屬性和混合約束問題，它們存在缺陷.而后一種方法中的遺傳算法存在早熟收斂現(xiàn)象和后期搜索速度慢的缺點(diǎn).

本文采用模糊Petri網(wǎng)對獨(dú)立全局約束的Web服務(wù)組合進(jìn)行建模，然后利用小生境算法來尋找最優(yōu)解，這樣克服了標(biāo)準(zhǔn)遺傳算法早熟收斂現(xiàn)象和后期搜索速度慢的缺點(diǎn)，而且能夠搜索到全部全局最優(yōu)解和盡量多的局部最優(yōu)解.最后的仿真結(jié)果表明這種方法不僅節(jié)省了時間而且搜索到了更多的最優(yōu)解.

［1］Nalaka Gooneratne，Zahir Tari.Matching Independent Global Constraints For Composite Web Sdrvices，WWW2008，765－774，2008.

［2］葛敬軍，黃 華，胡建明.面向語義Web服務(wù)組合的模糊Petri網(wǎng)推理算法［J］.計算機(jī)科學(xué)，2009，36（9）：121－122.

［3］趙苗，齊麗麗，李建晶.基于小生境技術(shù)的遺傳優(yōu)化算法改進(jìn)［J］.計算機(jī)科學(xué)，2009，28（3）：161－163.

［4］侯格賢，吳成柯.遺傳算法的性能分析［J］.控制與決策，1999，14（3）：257－260.

［5］Fang，X.W，C.J.Jiang，and X.Q.Fan.Independent global constraints－aware web service composition optimization［J］.Information Technology Journal，2009，8（2）：181－187.

［6］郝 冬，蔣昌俊，林 琳.Petri網(wǎng)和遺傳算法在FMS中的應(yīng)用［J］.中國計算機(jī)報，2005，28（2）：202－208.

［7］陳丁建.基于語義的 Web服務(wù)發(fā)現(xiàn)和組合的研究［D］.西北工業(yè)大學(xué)博士論文，2006，21（3）：23－24.

［8］I.Elgedawy，Z.Tari，and M.Winikoff.Exact Functional Context Matching for Web Services［R］.In Proceedings of the 2nd International Conference on Service Oriented Computing，pages，143－152，2004.

［9］N.Gooneratne，Z.Tari，and J.Harland.Matching Strictly Dependent Global Constraints for Composite Web Services［R］.In Proceedings of the European Conference on Web Services，pages 139－148，2007.

［10］Dong－Her Shih，Hsiu－Sen Chiang，and Binshan Lin.A Generalized Associative Petri Net for Reasoning［J］.IEEE Transactions Knowledge and Data Engineering，VOL.19（9）：1241－1251，2007.

Optimization Method of Independent Global Restriction Web Service Combination Based on Niche GA and FPN

Feng Yinghua1，3，Xu Zhicai2，Wang Juan1
（1.School of Science，Anhui University of Science and Technology，Huainan 232001，China；2.Department of Mathematics，Chuzhou University，Chuzhou 239012，China；3.Department of Basic Courses，Huainan Union College，Huainan 232001，China）

For independent global restriction Web service combination，the paper suggests using fuzzy Petri net（FPN）for modeling，which changes finding feasible service combination into finding the possible sequence in the FPN model，thus bringing seeking best service combination into finding the legal sequence of the largest trust value in the FPN model.Niche genetic algorithm（Niche GA）is then used to find the optimal legal sequence in order to obtain optimal combination service.The experimental results show that the method can not only reduce the computational time but also obtain more optimal solutions.

fuzzy Petri net；Niche genetic algorithm；Web service combination；optimization

TP391.9

：A

：1673－1794（2010）05－0023－04

馮英華（1979－），女，碩士生，講師，研究方向：Web服務(wù)，Petri網(wǎng)及應(yīng)用。

安徽省高校省級自然基金項(xiàng)目（KJ2010B310）。

2010－06－11