融合遺傳聚類的可靠Web服務組合優(yōu)化方法

張苑蕾，邵 清，李劉靜，魯建斌，張程斌

(上海理工大學 光電信息與計算機工程學院，上海 200093)

E-mail：sq_usst@126.com

1 引 言

近年來，隨著科學技術(shù)的不斷進步，互聯(lián)網(wǎng)早已成為人們?nèi)粘９ぷ魃钪胁豢扇鄙俚囊徊糠?為了能夠更好地解決網(wǎng)絡應用之間的互操作，提高數(shù)據(jù)的共享和存儲效率，Web服務組合技術(shù)應運而生.由于單個Web服務提供的功能有限，人們開始將現(xiàn)存的多個平臺獨立的Web服務進行靈活、快速組合，實現(xiàn)數(shù)據(jù)的相互交換或集成，滿足不同用戶的需求.而在大數(shù)據(jù)環(huán)境下，隨著用戶需求越來越復雜，單個Web服務的不確定性增加，導致服務組合的難度也越來越大，對Web服務組合技術(shù)的要求也越來越高.

現(xiàn)有的Web服務組合優(yōu)化方法主要分為兩類：傳統(tǒng)優(yōu)化方法和智能優(yōu)化方法.傳統(tǒng)的優(yōu)化方法由于存在可擴展性差、靈活性低等弊端，已經(jīng)漸漸被智能優(yōu)化算法所代替.智能優(yōu)化算法主要融入了遺傳算法、蟻群算法、模擬退火算法、混沌算法、煙花算法、聚類算法等[1-13]，這些算法能夠較好地利用任務資源尋求服務組合的最優(yōu)解，從而提高算法的綜合性能和資源利用率.例如，文獻[5,6]將混沌思想和遺傳算法結(jié)合，實現(xiàn)種群的選擇優(yōu)化，提高了服務組合的效率，但服務組合的可靠性沒有明顯改善；文獻[7]針對融合網(wǎng)絡環(huán)境中出現(xiàn)的兩類故障(臨時性故障和永久性故障)，將模糊邏輯、多屬性決策理論和改進的粒子群算法應用其中，三個主要模塊之間相互作用，能夠有效降低故障處理時間、故障排除率和組合最優(yōu)度，但是針對臨時性故障，所提方法中設(shè)置的固定重試頻率在實際應用中不能完全適用；文獻[8]將改進的煙花算法首次應用于離散服務的組合優(yōu)化問題，并在建模過程中引入高斯變異概率和精英選擇策略，有效降低算法的時間開銷，但服務組合的可靠性沒有得到驗證；文獻[13]通過利用Mashup服務相似性的K-means算法進行服務聚類，大大提高了Web服務搜索引擎檢索相關(guān)服務的能力，但沒有改善服務組合的可靠性.除上述研究算法之外，還有一些智能優(yōu)化方法[14-16]將容錯思想應用其中，以提高可靠性.例如，文獻[14]采用一種面向事務性Web服務組合的FT模式推薦方法，在模式選擇過程中引入4個組合級QoS因子進行優(yōu)化，同時采用多目標優(yōu)化算法，提高復合服務中的可靠性，但該方法在實際應用中的成功與否，很大程度上取決于服務所選QoS值的可用性和精確性；為了構(gòu)建可靠的面向服務的體系結(jié)構(gòu)/應用程序SOA，文獻[15]利用服務復制策略進行容錯，同時建立分布式的評估與選擇框架，但由于缺乏用于研究Web服務性能和各種復制策略的實際數(shù)據(jù)，該模型框架只能在無狀態(tài)Web服務上工作；文獻[16]針對具有事務性特性的組合服務，建立了容錯組合框架FACTS，能有效提高組合服務的容錯性，但在動態(tài)網(wǎng)絡環(huán)境中服務組合的可靠性無法驗證.

綜上分析，為了提高候選Web服務集的可靠性，改善組合優(yōu)化性能，本文提出一種基于混合遺傳聚類的可靠Web服務組合優(yōu)化模型(IHGCA).該模型首先通過混沌映射產(chǎn)生初始組合服務集，并借助置信度表對服務集進行一次篩選，以提高組合可靠性.在此基礎(chǔ)上利用遺傳算法優(yōu)化服務集，并以二次聚類為基礎(chǔ)建立服務組合優(yōu)化模型，最終收斂于全局最優(yōu)解.實驗結(jié)果表明，與傳統(tǒng)優(yōu)化方法相比，所提模型在提高可靠性指標的同時改善了組合優(yōu)化度.

2 問題描述

假設(shè)一個Web服務組合SC=(W1，W2，…，Wm)由m個抽象服務組成，每個抽象服務都有一個候選服務集合Wi=(wi1，wi2，…，wij)，j個具體服務的功能屬性相同，非功能屬性不同，每個具體服務wij有s個QoS屬性(q1，q2，…，qs).根據(jù)用戶所提交的任務信息，從每個候選服務集合Wi中選擇一個具體服務wij即可組成一個Web服務組合SC.

Web服務組合包括4種類型結(jié)構(gòu)：順序、選擇、循環(huán)和并列，由于后3種類型均可轉(zhuǎn)為順序類型，因此本文只討論順序類型.

本文選用一個6元組表示QoS=(rt，pr，cr，re，av，th).其中，rt代表響應時間，pr代表價格，cr代表信譽度，re代表可靠性，av代表可用性，th代表吞吐量.根據(jù)屬性對任務的影響效果，可將屬性分為兩類：一類是積極屬性(正向指標)，如信譽度cr、可靠性re、可用性av、吞吐量th；另一類是消級屬性(反向指標)，如響應時間rt、價格pr.

同時，為了能夠更好地對Web服務組合進行評估，本文設(shè)置了一個適應度函數(shù)fitness，通過將單個Web服務組合的QoS屬性按照下列公式進行計算，最終得出整體Web服務組合的QoS指標.適應度函數(shù)的計算如公式(1)所示：

(1)

3 可靠Web服務組合優(yōu)化模型

3.1 樣本數(shù)據(jù)預處理

在建立服務組合優(yōu)化模型之前，需要先對Web服務組合集合、參數(shù)以及QoS屬性指標進行歸一化預處理，以消除不同指標之間的量綱影響，減少不必要的分析誤差，確定統(tǒng)一的標準.

數(shù)據(jù)預處理主要包括初始化控制參數(shù)、初始化QoS屬性指標以及初始化組合服務集三部分.

3.1.1 初始化控制參數(shù)

進行初始化的控制參數(shù)符號意義詳見表1.

表1 控制參數(shù)符號代表的意義

3.1.2 初始化QoS屬性指標

針對Web服務組合的非功能屬性QoS=(rt，pr，cr，re，av，th)，根據(jù)“同一指標內(nèi)部相對差距不同，不同指標之間歸一化后極大值相等”的原則對其進行歸一化預處理，即正向指標和反向指標分別采用公式(2)進行歸一化：

(2)

需要注意的是，對于積極屬性(正向指標)來說，數(shù)值越大，服務質(zhì)量越好；對于消極屬性(反向指標)來說，數(shù)值越小，服務質(zhì)量越好.

3.1.3 初始化組合服務集

在遺傳算法優(yōu)化初始聚類中心之前，考慮到標準遺傳算法GA本身具有反饋信息少、收斂速度慢、對初始組合服務集的選擇有一定的依賴性以及容易陷入局部最優(yōu)等缺點，本文首先通過混沌映射對Web服務組合集合Pw進行歸一化預處理，并將其按照一定的規(guī)則或者潛在內(nèi)在規(guī)律進行隨機遍歷搜索，獲得全局最優(yōu)解，從而產(chǎn)生初始組合服務集P(0).

混沌映射的計算如公式(3)所示：

(3)

3.2 基于置信度的初始組合服務集篩選

為了提高Web服務組合的可靠性，對初始組合服務集P(0)作進一步的篩選，本文選用置信度描述Web服務組合的可靠性.置信度定義為服務組合成功次數(shù)c在所有服務組合執(zhí)行次數(shù)sum中所占的比例，用R表示，如公式(4)所示：

(4)

由公式可知，置信度越大，Web服務組合的可靠性越高.

由于不同的Web服務有著不同的置信度，將各Web服務的引用地址按照置信度進行排序，形成一張置信度表.根據(jù)置信度表對初始組合服務集P(0)進行一次篩選，得到t代規(guī)模為N的Web服務組合集P(t)={a1(t)，a2(t)，…aN(t)}，以提高服務組合的可靠性.置信度表的定義如下：

Typedef struct WebServiceNode{

Struct WebServiceNode *nextwsn；

//指向下一個服務的指針

Agent *info；

//該服務相關(guān)信息的指針

}WebServiceNode，AdjList[MAX]；

其中，服務Agent的屬性用來描述Web服務的執(zhí)行狀態(tài)，WebServiceNode代表中間變量指針，AdjList則為置信度表的生成和更新過程中所采用的鏈表結(jié)構(gòu).在置信度表的生成過程中，對于一個已經(jīng)存在的Web服務，根據(jù)其置信度，通過一個中間的WebServiceNode完成其插入操作.隨著置信度的變化，Web服務在置信度表中的位置會及時更新.

算法1.置信度表的生成算法

CreateCreditTable(WebServiceNode Node，AdjList &adjList){

if adjList.length==0 then{//置信表為空

adjList[0]=Node；}

else{//置信表不為空

if Node.Agent.WSDL=adjList[i].Agent.WSDL then

{//置信表中有該服務，插入到對應的位置

WebServiceNode current；

Current=adjList[i]；

if current.next=null then{

Current.nextwsn=Node；}

else{

WebServiceNode temp；

Temp=current；

Current=Node；

Temp.nextwsn=Node.nextwsn；

Node.nextwsn=temp；}}

else{//置信表中沒有該服務

Length++；

adjList[length]=Node；}}}

算法2.置信度表的更新算法

UpdateCreditTable(WebServiceNode Node，AdjList &adjList){

WebServiceNode current；

for(i=0；i

if(adjList[i].Agent.WSDL==Node.Agent.WSDL){

Node.Agent.R=Node.Agent.credit/

(adjList[i].Agent.credit/adjList[i].Agent.R+1)；

Break；}}

Current1=adjList[i]；

Current2=adjList[i]；

while(current1.nextwsn.Agent.key!=Node.Agent.key&¤t.nextwsn!=null){

Current1=current1.nextwsn；

Current2=current2.nextwsn；}

while(Node.Agent.R

{Current2=current2.nextwsn；}

Node.nextwsn=current2.nextwsn；

Current2.nextwsn=Node；}

3.3 可靠Web服務組合優(yōu)化模型的建立

在對初始組合服務集P(0)進行一次篩選的基礎(chǔ)上，建立滿足用戶需求的可靠Web服務組合優(yōu)化模型.首先采用遺傳算法優(yōu)化初始聚類中心，再根據(jù)K-means算法對組合服務集進行粗略劃分，最后利用AGNES層次聚類實現(xiàn)精確劃分.

3.3.1 基于遺傳算法的初始聚類

Web服務組合集初始聚類中心的選擇對聚類結(jié)果影響較大.一旦初始值選擇不好，可能導致其過早收斂于次優(yōu)解，無法得到有效的聚類結(jié)果.因此在聚類之前首先通過遺傳算法優(yōu)化初始聚類中心，具體步驟如下：

Step1.選擇操作.對于經(jīng)過一次篩選后的Web服務組合集P(t)，采用如下操作進行選擇：

fmax(t)=max{f(a1(t))，f(a2(t))，…，f(aN(t))}

fmax(t+1)=max{f(a1(t+1))，f(a2(t+1))，…，f(aN(t+1))}

iffmax(t)>fmax(t+1)then

(k=1，ork=1，2，…，K)

(j=1，orj=1，2，…，K)

endif

Step2.交叉、變異操作.本文采用一種自適應的交叉變異操作，以提高進化的穩(wěn)定性.其中，自適應交叉、變異概率計算分別如公式(5)、公式(6)所示：

(5)

(6)

式中，fmax為組合服務集中最優(yōu)Web服務的適應度；favg為集合的平均適應度；f′為要交叉的兩個Web服務中較大的適應度；f″為要變異的Web服務的適應度.

Step3.上述組合服務集經(jīng)過選擇、交叉、變異運算后得到含p個Web服務的組合服務集Xi(i=1，2，3，…，p).經(jīng)過實驗驗證，p取值一般為[30，150]，同時將進化最為活躍且交叉概率Pc和變異概率Pm分別在[0.6，0.9]和[0.001，0.05]范圍內(nèi)的q個組合服務集Yi(i=1，2，3，…，q)作為遺傳優(yōu)化后的初始聚類中心.

3.3.2 基于K-means的一次聚類

將組合服務集Yi(i=1，2，3，…，q)劃分成k個互補相交的Web服務組合子集Si(i=1，2，3，…，k).

將選取類內(nèi)距極小化而類間距極大化的組合服務集Ti(i=1，2，3，…，z)作為一次聚類的結(jié)果.

算法3.一次聚類的實現(xiàn)步驟

將選出的k個點作為初始質(zhì)心

Repeat

將每個點分配到最近的質(zhì)心，形成k個組合服務集；

計算測度函數(shù)f(k)；

重新計算每個組合服務集的質(zhì)心

Until組合服務集不發(fā)生變化或達到最大迭代次數(shù)

算法采用的測度函數(shù)f(k)用來描述在類別數(shù)盡可能小的情況下所得數(shù)據(jù)的緊湊度和分離度，具體定義如公式(7)所示：

(7)

式中，Dk為類間距，Ek為類內(nèi)距.

3.3.3 基于AGNES的二次聚類

在一次聚類的基礎(chǔ)利用AGNES層次聚類對服務集Ti(i=1，2，3，…，z)進行精確的劃分.

算法4.二次聚類的算法描述

輸入：將K-means一次聚類的結(jié)果作為輸入，終止條件組合服務集的數(shù)目設(shè)為K

輸出：K個組合服務集Zi(i=1，2，3，…，K)

過程：

將每個對象當成一個初始組合服務集

Repeat

根據(jù)兩個組合服務集中最近的數(shù)據(jù)點找到最近的兩個組合服務集；

合并兩個組合服務集，生成新的Web服務組合集合

Until達到定義的組合服務集的數(shù)目

綜上，IHGCA模型整體結(jié)構(gòu)如圖1所示.

圖1 服務組合優(yōu)化模型

4 仿真實驗

4.1 實驗數(shù)據(jù)

為驗證IHGCA模型能有效提高候選組合服務集的可靠性，本文以模擬用戶設(shè)定的旅游計劃的Web服務組合為例，進行仿真實驗分析.實驗采用11個原子服務組成的模擬旅游查詢組合服務.具體解釋如下：

w1：用戶注冊

w2：登錄

w3：出發(fā)地和目的地信息確認

w4，1：目的地天氣信息查詢

w4，2：出發(fā)地到目的地車票信息查詢

w4，3：目的地旅館信息查詢

w5：旅行社信息查詢服務

w5，1：跟團游線路推薦

w5，2：半自助游線路推薦

w6：自由行線路推薦

w7：支付確認

該旅游查詢系統(tǒng)的服務關(guān)系圖如圖2所示.由圖2可知，首先將各個旅游地點的相關(guān)信息進行混沌初始化；然后根據(jù)用戶的個人基本信息及旅游喜好進行初始組合服務集的一次篩選，確定出發(fā)地和目的地；接著根據(jù)用戶的個人旅游習慣進行遺傳優(yōu)化，選擇合適的出行方式；最后通過成功訂單信息及用戶反饋評價進行一次聚類，篩選出用戶出行最高的旅游地點和好評最佳的旅游信息服務，通過未完成支付訂單和差評訂單進行二次聚類，篩選出仍有待改進的旅游信息服務，進一步完善旅游查詢系統(tǒng)的功能.

圖2 旅游查詢系統(tǒng)服務關(guān)系圖

服務組合包含的任務數(shù)目設(shè)置為10-50，候選服務的數(shù)量設(shè)置為50.實驗一共進行50次，每類實驗分別按照任務數(shù)量從5開始，以5遞增的規(guī)律進行，最終結(jié)果是以實驗數(shù)據(jù)在50次仿真實驗所得結(jié)果的基礎(chǔ)上取平均值.實驗相關(guān)參數(shù)及QoS屬性取值范圍詳見表 2、表3.

表2 實驗參數(shù)設(shè)置表

表3 QoS屬性的取值范圍

4.2 評價指標

1)平均故障間隔時間MTBF：在服務組合的執(zhí)行過程中，相鄰兩次故障之間的平均工作時間.它反映Web服務組合產(chǎn)品在規(guī)定時間內(nèi)保持功能的能力.

設(shè)有一個可修復的Web服務組合產(chǎn)品在使用過程中，共發(fā)生N0次故障，并且每次故障經(jīng)過修復后又和新產(chǎn)品一樣繼續(xù)投入使用，其工作時間為T1、T2、T3、T4、T5、T6……T0.那么，平均故障間隔時間的計算如公式(8)所示：

(8)

由公式可知，MTBF的值越大，可靠性越高，正確工作能力越強.

2)故障排除率FRR：能被排除的Web服務組合故障次數(shù)和在服務組合的執(zhí)行過程中出現(xiàn)的總故障次數(shù)之比.設(shè)NT為組合服務執(zhí)行過程中出現(xiàn)的總故障次數(shù)，NP為能被排除的Web服務組合故障次數(shù)，故障排除率的計算如公式(9)所示：

(9)

由公式可知，F(xiàn)RR的值越大，故障排除能力越高，可靠性越高.

3)組合最優(yōu)度CO：組合服務的效用函數(shù)值.其值的大小可以代表組合服務的QoS屬性的優(yōu)劣.為了簡化效用函數(shù)的計算，本文只考慮原子服務的響應時間和吞吐率這兩個QoS屬性，并將它們的權(quán)重均設(shè)定為0.5.組合最優(yōu)度的計算如公式(10)所示：

(10)

其中，Nε為組合服務包含的原子服務個數(shù)，rε和thε分別為進行歸一化后的服務ε的響應時間和吞吐率.

由公式可知，CO的值越大，代表QoS屬性越優(yōu).

4)響應時間RT：從用戶發(fā)出請求或指令到Web服務組合系統(tǒng)做出反應的時間.響應時間的計算如公式(11)所示：

(11)

其中，wi為單個Web服務執(zhí)行的響應時間，n為系統(tǒng)中Web服務組合的數(shù)量.

由公式可知，RT的值越大，系統(tǒng)響應時間越長.

4.3 仿真結(jié)果及分析

為了驗證模型的有效性，本文選取ChaosGA[5]、FCluster[13]、RS[15]、FACTS[16]四種方法進行對比實驗.實驗采用java語言進行仿真模擬，具體運行環(huán)境為JDK1.8，Win10操作系統(tǒng)，i5-7300U處理器.實驗結(jié)果如圖3-圖6和表4所示.

圖3 平均故障間隔時間對比圖

從圖3可以看出，當任務數(shù)量較小(小于25)時，IHGCA模型雖然較其他4種方法的MTBF值高，但整體優(yōu)勢不明顯，這是由于建模過程中對組合服務集進行多次篩選和劃分所導致的時間資源浪費.而當任務數(shù)量增大(大于25)時，IHGCA模型在MTBF上的優(yōu)勢開始凸顯，其原因是建模前期對服務組合集的多次篩選減少了故障次數(shù)，可靠性得到增強.

圖4 故障排除率對比圖

從圖4可以看出，隨著任務數(shù)量的增加，IHGCA模型計算的FRR值逐漸增大.當任務數(shù)量小于20時，F(xiàn)RR值并不高，當任務數(shù)量大于20時，所提方法的FRR值開始高于其他4種方法.原因在于IHGCA模型在建模過程中，不僅借助置信度表對初始組合服務集進行一次篩選，而且還利用遺傳算法優(yōu)化初始聚類中心，以上兩種舉措均提高了服務組合的故障排除能力.

圖5 組合最優(yōu)度對比圖

從圖5可以看出，隨著任務數(shù)量的增加，本文所提方法的組合最優(yōu)度逐漸增大，并且高于其他4種方法.這是因為IHGCA模型引入混沌理論，彌補了遺傳算法收斂速度慢、易陷入局部最優(yōu)的缺點，同時加快了搜索速度，也易于實現(xiàn)全局漸進收斂，從而獲得全局最優(yōu)解.此外通過二次聚類減少了對初始值的選擇依賴，提高整體聚類效果.

圖6 響應時間對比圖

從圖6可以看出，隨著任務數(shù)量的增加，5種方法的響應時間均逐漸增大.其中ChaosGA的平均響應時間最短，F(xiàn)ACTS則最長.而IHGCA模型的優(yōu)勢不明顯，這是由于建模過程中對組合服務集進行多次篩選和劃分所導致的時間資源浪費.

表4 主要評價指標對比結(jié)果(任務數(shù)量=50)

5 結(jié)束語

為了提高Web服務組合可靠性和組合效率，本文提出一種基于混合遺傳聚類的可靠Web服務組合優(yōu)化方法.該方法在混合聚類算法的基礎(chǔ)上建立可靠服務組合優(yōu)化模型，并獲取全局最優(yōu)解.該模型在最初設(shè)計時，充分考慮了遺傳算法GA易于陷入“早熟”和K-means算法比較依賴于初始聚類中心的弱點，并且在實施階段，分別引入混沌思想和遺傳算法進行優(yōu)化，同時利用置信度表和二次聚類的方法對組合服務集進行多次篩選和劃分.仿真實驗充分驗證了本文所提出的Web服務組合優(yōu)化模型在可靠性方面具有一定的優(yōu)勢.

但是，由于互聯(lián)網(wǎng)環(huán)境的多變性和Web服務組合的不確定性，導致組合服務的非功能特性QoS也在不斷發(fā)生變化.設(shè)計一個面向動態(tài)的組合Web服務的自適應算法，并以此來適應用戶多變的需求條件，將是我們未來需要進行研究的工作.