基于麻雀算法的Web服務組合

楊宏偉，薛富城，李 莉

(長春理工大學 計算機學院，吉林 長春 130022)

0 引 言

目前解決Web服務組合問題的方法可以分為兩類：一類是根據服務質量屬性值(QoS)通過智能算法進行尋優求解模型[1]；另一種是通過Petri網工具進行建模求解[2]。如果單純采用Petri對服務組合進行求解，當服務數量過于龐大時，復雜度過高；如果單純采用智能算法對QoS模型進行求解時，智能算法大都會在接近最優值時陷入局部最優值并且不能具體表達出各組合服務間的邏輯關系。

在本文中，我們將介紹一種基于Petri網的Web服務組合模型，并通過麻雀算法對模型進行求解，該方法對解決Web服務組合問題有良好的效率和準確度，并且在面對復雜問題時能更清晰表現出各組合服務之間的邏輯關系。本文的主要貢獻如下：

(1)為了清楚地描述服務之間約束關系和執行邏輯，本文提出了基于Petri的服務組合模型對組合過程進行建模，將服務組合所有邏輯關系在Petri網進行映射，對Petri網的結構和行為進行分析驗證，可對服務組合的可行性、有效性、邏輯合法性進行驗證以及沖突解決，獲得服務質量更優的組合序列；

(2)如果單純采用Petri對服務組合進行求解，當服務數量過于龐大時，復雜度過高，因此在Petri網模型基礎上，本文提出了麻雀(SSA)算法的服務組合模型，采用自適應步長調節的方法，避免了算法陷入局部收斂導致局部最優的結果。考慮服務質量可靠性、可用性、執行時間、性能和成功率對服務組合進行多目標優化，通過Petri網對服務組合的合法性進行驗證，得出最優服務組合序列。

1 相關工作

根據服務質量屬性(QoS)的方法已經受到廣泛的研究關注。解決大規模服務組合問題時，改進的遺傳算法(GA)[3-5]、改進的蟻群優化算法(ACO)[6-8]和改進的粒子群優化算法[9,10]可以高效解決服務組合問題。但是這些算法都是將多目標問題轉化為單目標問題，會出現局部最優值情況。文獻[11]提出了一種多目標蜂群算法的Web服務組合優化方法，文獻[12]中的作者使用改進的萬有引力搜索算法解決問題，文獻[13]提出了一種融合遺傳聚類的可靠Web服務組合優化方法。文獻[14]對基于QoS的Web服務組合多目標算法進行了比較分析。huo等[15]提出了一種Eliteguided多目標人工蜂群算法有效解決了Web服務組合問題。一種改進的遺傳算法(CGA)[16]使用一種真正的編碼方法來解決基于QoS的服務選擇問題，避免了算法中長染色體的負面影響。

Petri網建模和模擬的能力非常強大，能夠直觀地表示出系統中的關系，可以通過網的運行對系統的可達性、活性、有界性進行分析。所以目前很多學者使用Petri網理論來解決Web服務組合問題。Groefsema H等[17]使用有色Petri網將服務組合映射到Kripke結構。Entezari-Maleki等[18]提出了一種基于定時彩色Petri網(TCPN)的模型，用于評估多云環境中的服務組合，同時最大程度地減少服務于組合服務請求的云數量。Sha等[19]為了提高服務發現的準確性和效率，提出了一種基于Petri網的面向用戶需求的Web服務發現方法。

對于現有的研究，服務組合問題已取得了一定的成果，但大部分的研究都很少考慮到服務QoS屬性計算方式與組合順序有密切關系，較少地考慮了基于QoS屬性評估的同時對服務組合的合法性、可行性以及服務執行的邏輯合理性的分析驗證。因此本文針對這些問題在基于Petri網的服務組合方法基礎上結合改進的麻雀算法對服務組合進行合法性判斷，并通過邏輯順序對服務組合的QoS進行計算，選擇出最優的服務組合序列。

2 基于Petri網的服務組合模型

Petri網[20]的概念是德國科學家Carl Adam提出的，用于描述系統結構及執行邏輯的一種網狀模型。云環境中存在很多應用，通過這些應用能夠高效率地完成用戶所提出的請求。所以本文以其中某服務作為例子，用戶發出請求R，首先將其分解為多個子任務R=(Task1,Task2,…,Taskn)完成，其中每個子任務Taski，(i=1,2,…n)完成某一特定功能。任務R由該子任務集合按照一定業務邏輯完成任務，在執行每個子任務的過程中，通過服務發現，每個子任務Taski，(i=1,2,…n)都可由多個候選原子服務來完成，假設子任務Task有m個候選原子服務表示為Si=(si1,si2,…,sim)，在這些候選服務集合中，通過對比服務非功能屬性選擇一個綜合性能最優的Web服務Sik，(k=1,2,…,m)來執行子任務Task。當所有的子任務都選擇了對應的原子服務，則可進行服務組合。通過服務選擇，計算每個組合服務的QoS值，最終選擇出性能最優的服務組合方案，最后的組合方案按照請求的一定邏輯順序執行。為了完成用戶的請求，需通過服務組合將每個任務的相關特定功能的原子服務集合進行集成。由于不同服務之間存在著執行邏輯關系，為了能夠了解服務之間的相互關系，本文采用Petri網進行建模對網系統進行動態分析和驗證。

定義1 定義一個原子服務，其可表示為四元組cs={s_id,s_function,s_type,s_status,s_constr}。其中s_id表示服務的標識，s_function表示服務具有的執行功能，s_type表示服務類型，s_status表示該服務狀態，s_constr表示服務之間約束關系或者評價指標值。

定義2 定義一個服務組合優化Petri網(service composition petri net，SCPN)，其由十一元組P={P,T,E,L,I,O,F,Eth,Lth,S,Mcs} 組成，其中當且僅當：

(1)P={p1,p2,…,pm} 表示庫所的有限集合，其中，pi,(i=1,2,…,m)表示候選原子服務集合的第i個原子服務；

(2)T={t1,t2,…,tn},(n>0)表示變遷的有限集合，其中P∩T=?，P∪T≠?；

(3)E={e1,e2,…,em},(m>0)表示原子服務響應時間評估值的有限集合，表現出服務組合中原子服務的執行效率；

(4)L={l1,l2,…,lm},(m>0)表示原子服務失效頻率的有限集合；

(7)F?(P×T)∪(P×T)表示SCPN網有向弧的有限集合；

(8)Eth={eth_1,eth_2,…,eth_m} 表示服務響應時間臨界值的有限集合；

(9)Lth={lth_1,lth_2,…,lth_m} 表示服務失效頻率臨界值的有限集合；

(11)dom(F)∪cod(F)=P∪T；

3 基于麻雀搜索算法的Web服務組合

3.1 標準的麻雀搜索算法

麻雀搜索算法(sparrow search algortihm，SSA)是一種受到麻雀覓食和被捕食預警的新的群體智能算法，它的搜索精度和收斂速度等比其它群體智能算法更為優秀，并且其參數較少，穩定性高[21]。麻雀算法可根據其覓食的過程表示為發現者-加入者模型，在此基礎模型中還加入預警報告機制。

在SSA中，模擬麻雀覓食過程獲得優化問題的解。由n只麻雀組成的種群可表示為如下形式

(1)

其中，d為問題維數，n是麻雀的數量，所有麻雀的適應度值如下

(2)

其中，f表示適應度值。

發現者一般占到種群的10%～20%，位置更新公式如下

(3)

其中，t代表當前迭代次數；α為0到1之間取值的隨機數；T為最大的迭代次數；L表示大小為1*d的單位陣；Q是服從標準正態分布的隨機數；R0∈[0,1]和YJ∈[0.5,1]分別表示預警值和安全值。當R0

除了發現者，其余的麻雀都為加入者，并根據下式進行位置更新

(4)

偵察預警麻雀占到種群的10%～20%，其位置更新公式如下

(5)

其中，β表示步長參數，取值為一個正態分布的隨機數，并且均值為0，方差為1；e是無限接近于0的一個常數；K的值在[-1,1]之間隨機確定，表示麻雀飛行的方向；fi表示第i只麻雀的適應度值，fg是當前種群最佳適應度值；fw表示當前種群最低適應度值。預警麻雀的位置更新可分為兩種情況：①當fi≠fg時，表示當前麻雀的位置偏離群體，容易被捕食者獵食，應當發出警告，此時算法容易陷入局部最優，可根據公式進行調整；②當fi=fg時，表明當前麻雀的位置在群體之中，可以通過預警，及時調整覓食的搜索路線，避免被捕食者獵食。

3.2 自適應步長調節的麻雀搜索算法

步長因子是控制算法收斂的關鍵。如果步長衰減過快，麻雀搜索算法可能無法獲取最優解；反之，麻雀算法可能陷入局部最優解。為了使算法獲得更好的優化能力，本研究提出了一種動態改變步長因子的改進方法。在麻雀算法前期，采用較大的步長控制因子來擴大解空間中的整體搜索范圍并加快搜索速度；在優化的后期，解空間趨于穩定，此時應該提高解的精度，減小步長控制因子。基于以上的考慮，本研究對麻雀搜索算法的步長控制因子β進行改進

β=α-0.2·((i+1)/5·Gmax)+0.5),fi

(6)

β=α,fi≥fpbest

(7)

其中，Gmax為最大迭代次數，fi是當前適應度值，fpbest是歷史最佳適應度值，i是當前迭代次數，α是默認步長因子，β是當前步長。

算法流程如圖1所示。

圖1 自適應步長麻雀算法流程

3.3 適應度函數設計

服務組合的評價標準主要是通過服務各個屬性指標對服務組合性能進行綜合評價。根據Petri網SCPN的變遷規則以及各個指標計算方法來確定麻雀搜索算法的適應度函數。但在確定適應度函數之前，由于不同的指標其標準不同，需對各個指標進行標準化。Web服務QoS的多個屬性對QoS綜合值的正負影響不同，因此提出了兩種服務屬性：正服務屬性和負服務屬性。

正服務屬性：針對本文所考慮的QoS屬性，其中可用性、可靠性、性能以及成功率都屬于正服務屬性。對于用戶而言，Web服務的可靠性越高，其QoS值越高，更值得用戶信任。

負服務屬性：負服務屬性表示屬性的取值與服務質量成反比，比如執行時間，執行時間越長，用戶的體驗度就會越差，服務質量越低。

為了能夠統一標準，便于計算，對QoS各個屬性進行標準化處理，將其值轉換至區間[0,1]，其QoS值越大服務質量就越高，標準化處理后的服務質量QoS的二維矩陣表示如式(8)所示

(8)

其中，Qt表示標準化后的矩陣，矩陣的行代表各種QoS屬性值，矩陣的列代表各個屬性的值。矩陣可以適當擴展。每當添加屬性時，都應在矩陣中添加一列。

QoS屬性標準化公式如下

(9)

(10)

通過對各個服務質量屬性進行了標準化后，可得到適應度函數公式如式(11)所示

(11)

3.4 編碼方式

對于服務組合的問題中，采用二進制編碼會使得問題更加復雜，假設有R個服務需要進行組合，每個服務都具有K個候選原子服務，采用二進制編碼的解將有R×K個二進制位，表示成SV={r11,r12,…,r1k;r21,r22,…,r2k;…;rr1,rr2…,rrk}。其解空間過于龐大，對于系統來說在計算的過程中太浪費內存和時間。因此本文采用十進制進行編碼大大縮減了解空間，具體編碼方式如下：

假設Web請求R需要W個子任務(Task1,Task2,…,Taskw)一起完成，其每個子任務都需要一個服務完成，其每個服務都有一個候選服務集合Si=(si1,si2,…,sim),(i=1,2,…,w)，則編碼方式可表示成SV={r1,r2,…,rk…,rw}，由W個整數組成的解空間，其中，rk∈{1,2,…,m},m∈N*，每個服務的候選服務數量可能不同，因此m的取值也可能不同。

4 實驗與結果分析

4.1 實驗環境

為了驗證本文提出的Petri網模型的可行性，本文采用了Petri的可達標識圖分析方法[21]對Petri網TBPN進行動態性能分析，對于系統服務執行邏輯進行死鎖判斷。為了能夠獲得全局最優的服務組合，本文在Petri網SCPN描述多約束的基礎上，結合本文提出的SSA算法有效避免了出現復雜度高或者隨機性大的問題。本研究的作者使用QWS真實數據集對順序結構進行了大量實驗[22]。QWS數據集是由Guelph大學的Eyhab Al-Masri教授收集的Web服務數據集。QWS中的所有數據集都是從各個服務網站收集的真實數據集。該數據集包含2507個實際服務和9個QoS值。實驗環境如下：Intel(R)Core(TM)i5-8300H CPU@2.30 GHz 2.30 GHz，16 GB ddr4 2666 MHz memory,64 bit Windows 10 OS,and MATLAB R2015b。

4.2 Petri網系統的服務組合驗證與分析

通過可達標識圖對SCPN網絡可達狀態進行分析。該實例的初始標識狀態為M0={1,0,0,0,0,0,0,0,0}，其可達集見表1，其中所有狀態標識供9種，模型標識為PBTPN={p1,p2,p3,p4,p5,p6,p7,p8,p9}，其每一行代表一個標識。

表1 SCPN網可達集合

網絡可達狀態分析結果如圖2所示。

圖2 可達狀態分析結果

對BTPN的可達狀態標識圖進行分析，以狀態序列(M0,M1,M4,M6,M7,M8)為例進行分析，其結果如下。其中，Stat表示狀態，Tran表示變遷。

(1)M0={1,0,0,0,0,0,0,0,0},Stat={M0},Tran=?；

(2)M1={0,1,0,0,0,0,1,0,0},Stat={M0,M1},Tran={t1}；

(3)M4={0,0,0,1,0,0,0,0,0},Stat={M0,M1,M4},Trasition={t1,t4}；

(4)M6={0,0,0,0,0,0,1,0,0},Status={M0,M1,M4,M6},Trasition={t1,t4,t6}；

(5)M7={0,0,0,0,0,0,0,1,0},Status={M0,M1,M4,M6,M7},Trasition={t1,t4,t6,t7}；

(6)M8={0,0,0,0,0,0,0,0,1},Status={M0,M1,M4,M6,M7,M8},Trasition={t1,t4,t6,t7,t10}。

從運行結果可知，從系統最初狀態M0通過變遷序列總能到達系統結束狀態M8，因此網系統不存在死鎖，所有的狀態都包含所有庫所和變遷，因此該網系統具有活性和全覆蓋性，服務組合之間邏輯結構具有正確性以及有效性。

4.3 用戶偏好設置

本節實驗用來驗證不同用戶偏好對服務組合評估的影響，用來對比本文提出的方法在服務組合優化領域的有效性，排除用戶偏好對算法進行組合服務選擇的干擾性。本文將提出的SSA算法與DPSO算法和文獻[16]中的CGA算法進行對比。本文選取文獻[23]給出20組的不同的用戶偏好進行了實驗對比，實驗參數為：選取可用性、吞吐量、響應時間和可靠性4種QoS屬性，迭代次數500次，子任務數為10，候選服務集的規模為100個，用戶偏好的具體值見表2。

表2 用戶體驗

具體實驗結果見表3，根據組合服務的目標函數計算方式，在不同的用戶偏好下，使用改進的SSA算法尋找的組合服務適應度值高于其它算法，本節實驗可以排除用戶偏好對于SSA算法進行服務組合的影響。

表3 每個用戶體驗的適應度值

4.4 有效性分析

本節將對所提出算法解決服務組合問題的有效性進行分析。對比使用SSA、DPSO和CGA這3種算法計算適應度函數100次求得的適應度值的平均值，適應度值大的算法有效性高。選取服務規模為n*m，n為服務請求數，m為候選服務數。分別取n為10，20，50；分別選取m為50，100，200，400，800。迭代次數設置為100。實驗結果如圖3～圖5所示。

圖3 n=10時3種算法的平均適應度值

圖4 n=20時3種算法的平均適應度值

圖5 n=50時3種算法的平均適應度值

從實驗結果圖中得出，無論服務組合規模如何增長，SSA始終保持著比另外兩種算法高的平均適應度值，說明SSA算法解決服務組合問題的有效性；當問題維度升高時，在n達到50時，SSA仍然有著比另外兩種算法高的平均適應度值，表明SSA算法在面對高維度問題時的有效性和高精確性。

4.5 收斂性

智能算法的重要性能指標之一就是其收斂性[24]。算法的收斂是指經過多步迭代之后得出的數值不應該無限增大, 而是趨于某個數值，不能收斂的算法是沒有使用價值的。本節將分析實驗結果，重點討論SSA算法的收斂性。

為了更清晰表現算法的收斂性，本節將迭代次數設為100，服務規模n*m設為：10*10，20*20，50*50；選取不同規模服務組合50次實驗后的平均適應度值。實驗結果如圖6～圖8所示。

圖6 10*10服務規模

圖7 20*20服務規模

圖8 50*50服務規模

從圖6～圖8中可以看出，當服務規模為10*10、迭代次數為10時，SSA算法的平均適應度值已經明顯高于另外兩種算法；隨著迭代次數的增加，SSA開始收斂，當迭代次數到達50時，SSA算法已經收斂。同理，隨著服務規模的增長，SSA在迭代50代左右，同樣會趨于最優值。這表明SSA算法有著良好的收斂性能。

4.6 算法穩定性

智能算法的穩定性是在面對復雜問題時能否準確得出最優值的關鍵。本節為了驗證SSA算法解決不同規模的Web 服務組合的穩定性，將SSA、DPSO和CGA算法在問題維度為10*10、20*20、30*30、40*40和50*50這5種情況下運行50次，記錄各算法所得適應度值并計算其標準差。在同等情況下，平均適應度值標準差低的，算法穩定性強。

從圖9中可以看出，SSA算法的標準差明顯小于另外兩種算法。隨著服務規模的增長，3種算法的標準差都在增長，這是因為問題的維度在不斷擴大，算法的穩定性都受到了影響。在50*50規模時，算法的標準差明顯高于在10*10規模時，但SSA算法仍然低于另外兩種算法，并保持在較低的水平。這表明SSA的算法穩定性良好。

圖9 算法標準差

5 結束語

針對Web服務組合現有的模型單一、無法清楚表示出各服務組合間的邏輯關系和當問題規模變復雜時智能算法效率低下等問題，本文首先提出了基于Petri網的服務組合模型SCPN網，并對所提出的模型進行了可行性驗證。然后提出了基于自適應步長調節的麻雀搜索算法對模型進行了求解。通過實驗驗證了所提出的SCPN網模型對解決服務組合問題的可行性，同時驗證了所提出改進的SSA算法具有收斂速度快、搜索精度高、算法性能穩定和解決服務組合問題的有效性。