基于優化的灰狼算法的大規模Web服務組合

徐雪敏，張秀國，肖媛元，曹志英

（大連海事大學 信息科學技術學院，遼寧 大連 116026）

0 引言

隨著Web 2.0、云計算、大數據、移動互聯網和物聯網等技術的迅猛發展，越來越多的企業以開放Web 服務的形式在不同的云計算平臺上發布自己的服務，這使得互聯網上不同領域的開放Web 服務資源數量呈爆炸式增長［1］。與此同時，用戶的需求也朝著個性化、復雜化的趨勢發展。當用戶的復雜需求無法采用單一服務滿足時，就需要整合和協調來自不同領域的不同服務，將多個功能各異的Web 服務按照服務組合方案進行組合，形成大粒度的服務提供給用戶［2］。服務數量的迅速增加和服務的多樣性使得服務環境具有大規模的特點，如何在大規模服務環境中組合出滿足用戶需求的組合服務成為服務計算的研究熱點。

目前，研究者已經從不同角度對大規模Web 服務組合進行了研究，主要有以下三種方法：

1）服務組合空間縮減。通過對服務組合空間的縮減可以有效地去除冗余服務，提高服務組合的效率。Wang等［3］將Skyline 計算與Q-learning 結合用于服務組合，利用Skyline計算，選取服務質量（Quality of Service，QoS）不被支配的服務減少候選服務數量，提高組合的效率，并結合能反映用戶偏好的強化學習方法來解決動態環境下的服務組合問題；但這種篩選方法會隨著QoS 的增多而遇到維度災難的問題。Fan等［4］將大規模Web 服務組合問題轉化為從服務依賴圖提取最優組合，通過全局和局部的剪枝策略，去除冗余服務和無用的搜索空間，提出了一種鏈式動態規劃算法（Chained Dynamic Programming algorithm，Chain-DP）；但這種算法在構建服務之間的拓撲關系時需要消耗大量的時間，并且動態規劃的運行時間仍然是偽多項式的。

2）基于服務質量感知的大規模Web 服務組合優化。張苑蕾等［5］提出一種融合遺傳聚類的可靠Web 服務組合優化模型，利用置信度表對服務進行篩選，使用聚類和遺傳算法對組合服務集合進行多次劃分，不但提高了組合可靠性，而且模型最終收斂于全局最優解。Zhang等［6］在果蠅優化算法的基礎上引入動態步長、信息共享和精英策略，提高了算法的全局搜索能力和搜索效率，增加了算法在解決服務組合問題上的穩定性。然而這些優化算法在實際應用時也存在著明顯的不足，例如煙花算法實現復雜、收斂速度緩慢而且穩定性較差；果蠅優化算法依賴參數的設定，容易陷入局部最優。

3）采用MapReduce 并行編程模型提高大規模Web 服務組合的計算效率。Jatoth等［7］提出了一種基于MapReduce 的并行引導變異的遺傳算法（Evolutionary Algorithm with Guided mutation，EA/G）來求解大服務組合問題，該算法引入Skyline 算子從QoS 層面篩選候選服務，利用分布估計算法（Estimation of Distribution Algorithm，EDA）改進遺傳算法，通過仿真實驗在大服務環境下證明了該算法的可行性和優異性。Zhang等［8］利用改進的離散粒子群算法和MapReduce 來解決大規模動態服務組合問題，引入Skyline 算子剔除冗余的Web 服務，采用混沌序列初始化粒子群，用Chaos-Process擾動機制處理粒子的早熟收斂狀態。并行算法在解決服務組合問題上體現了比串行算法更好的性能，但在面對海量的服務時仍具有較大的搜索空間。以上的算法都是仿真實驗，沒有給出具體的需求描述和真實世界的Web 服務。

本文聚焦大規模Web 服務組合問題，以面向用戶需求的服務功能選擇為基礎，結合群體智能算法，提出一種基于服務主題模型和灰狼算法（Grey Wolf Optimizer，GWO）的Web服務組合方法。

1 大規模Web服務組合問題定義

1.1 相關定義

定義1Web 服務組合

本文用一個三元組CWC=(T，CTRs，W)表示一個具體的Web 服務組合，其中，T={t1，t2，…，tN}表示抽象Web 服務，N表示抽象Web 服務的個數；CTRs是一系列控制結構，包括順序、并行、選擇和循環四種控制結構；W=(w1，w2，…，wk)表示不同QoS 對應的權值（所有權值之和為1），k表示QoS 屬性的個數。

定義2候選服務集

候選服務集是一組功能上等價但QoS 屬性值不同的具體Web 服務的集合，表示為WSs=其中，是第i個抽象Web 服務的第j個具體Web 服務，i∈{1，2，…，N}表示一個組合服務由N個抽象Web 服務組成，j∈{1，2，…，k}表示一個抽象Web 服務的候選服務集中有k個具體Web 服務是服務的QoS 屬性值。

定義3服務質量

Web 服務質量是指Web 服務的非功能屬性，本文用一個五元組QoS=(C，R，A，RT，TP)來表示，其中C表示價格，R表示可靠性，A表示可用性，RT表示響應時間，TP表示吞吐量。

由于一個Web 服務具有多個QoS 屬性，通常根據其對服務選擇的影響效果劃分為積極屬性和消極屬性兩類。為了消除不同量綱的影響，需要對QoS 進行歸一化處理。對于積極屬性如可用性、可靠性等，它們的值越高對服務效能越有益；對于消極屬性如時間、費用等，它們的值越低對服務效能越有益。積極屬性和消極屬性分別按照式（1）～（2）進行歸一化計算：

1.2 組合服務的QoS計算

在實際應用中，不同控制結構下的組合服務的QoS 有不同的計算方法，本文將組合服務各個QoS 屬性用集合CWQ表示，具體形式如下：

其中，CWqC、CWqR、CWqA、CWqRT、CWqTP分別表示組合服務的價格、可靠性、可用性、響應時間和吞吐量，根據組成組合服務的各個Web 服務的QoS 屬性值和服務組合的控制結構計算組合服務的QoS。

本文以響應時間和吞吐量為例說明在四種控制結構下QoS 的計算方法，如表1 所示。其中：RTi、Ti、分別為第i個服務的響應時間和吞吐量，m表示抽象服務組合中包含的抽象服務的數量，pi為選擇某分支的概率，c為循環次數。

表1 組合服務QoS計算方法Tab.1 QoS calculation methods of composite service

本文將大規模Web 服務組合問題歸納為一個多目標優化問題，使用線性加權的方式將其轉為單目標優化問題，通過計算組合服務的服務質量表征組合服務的優劣，服務質量越大，組合服務越佳。大規模服務組合的目標函數如式（3）所示：

其中：fit（）表示組合服務的服務質量；maxfit（）表示組合服務服務質量的最大值；CWqi表示組合服務第i個QoS 屬性值；wi表示第i個QoS 屬性所占權重且=1，Q表示QoS 屬性的個數。

2 基于優化的灰狼算法的服務組合方法

為了解決大規模Web 服務組合問題，文本提出一種基于優化的灰狼算法和MapReduce 框架的大規模Web 服務組合方法。本文方法的框架如圖1 所示。

如圖1 所示，該方法首先采用文檔對象模型（Document Object Model，DOM）對XML 描述的用戶需求文檔進行解析；然后基于服務主題模型進行服務篩選，即通過度量用戶功能需求描述和服務描述文檔的概率主題相似度篩選出各抽象Web 服務的候選服務集；最后利用MapReduce 框架并行實現優化的灰狼算法以選出最佳服務組合方案。

2.1 基于DOM的用戶需求文檔解析

對用戶需求文檔解析可以得到抽象服務組合序列和每個抽象Web 服務的功能需求，抽象服務組合序列包含了服務之間的組合結構信息。本文采用DOM 對XML 格式的用戶需求文檔進行解析，獲得抽象服務組合序列和各個抽象Web 服務的功能需求。

以一個簡單的旅游需求為例，用戶需求描述文檔中主要包含以下功能：位置查詢（t1）、酒店預定（t2）、餐廳預定（t3）、在線支付（t4）、旅游計劃（t5）、照片上傳（t6）。首先用戶查詢自己所在的位置，根據自己的位置預定周圍的酒店，同時查找和預定附近的餐廳，用在線支付功能對酒店和餐廳的訂單進行支付，然后通過旅游計劃服務進行旅游計劃的制定，最后將在旅游過程中拍攝的照片上傳到社交平臺上進行分享。XML 格式的用戶需求文檔格式如下：

用戶需求文檔經過解析后得到的抽象服務組合序列如圖2 所示。其中，ts表示開始，tf表示結束，t2和t3是并行結構，其他服務是順序結構。

2.2 基于服務主題模型的服務篩選

為了縮小候選服務規模，在獲取到抽象服務組合序列后，根據得到的各個抽象Web 服務的功能描述，對服務候選集進行基于服務主題模型的服務篩選。

2.2.1 服務主題模型建立

概率主題模型是一種可以挖掘大規模文檔集合潛在主題的文本信息特征抽取技術，已被廣泛開發和用于主題提取和文檔建模［9］。針對服務描述文檔，使用潛在狄利克雷分布（Latent Dirichlet Allocation，LDA）主題建模技術獲取服務描述文檔的隱含主題，能夠更加準確地度量Web 服務描述文檔的語義相似度。

本文首先將Web 服務描述文檔進行預處理，經過文本令牌化、小寫轉換、去除停用詞、詞形還原和抽取名詞動詞之后，最終得到的服務描述文檔可抽象表達為dtext={w1，w2，…，wn}，其中n表示服務描述文檔中詞的個數，然后采用Bigrams 模型對服務功能描述進行詞向量建模，將得到的詞向量輸入到LDA 主題模型中進行服務主題模型的訓練。針對服務描述文檔的LDA 主題建模過程如圖3 所示，相關符號及含義如表2 所示。

表2 LDA主題模型符號Tab.2 Symbols of LDA topic model

針對服務描述文檔的LDA 主題建模過程如下：

1）對每個主題k∈{1，2，…，K}采樣生成主題k的詞分布：φk～{Dirichlet(β)}。

2）對每篇Web 服務描述文檔m∈{1，2，…，M}采樣生成文檔m的主題分布：θm～{Dirichlet(α)}。

3）對文檔m中每個詞n∈{1，2，…，Nm}，其生成過程為：①選擇主題，從θm中抽樣生成文檔m的第n個詞的主題Zm，n～Multinomial(θm)；②生成一個詞，從所選主題中抽樣生成詞wm，n～Multinomial()。

表3 為LDA 主題模型生成的服務文檔-主題矩陣，其中：di表示服務文檔集的第i個文檔；Ti表示服務文檔集共享的第i個主題。

表3 服務文檔-主題矩陣Tab.3 Service document-topic matrix

2.2.2 服務篩選

表4 為在線支付功能需求與部分服務描述文檔的JS 散度，其中di表示服務文檔集的第i個文檔。

表4 在線支付功能需求與部分服務文檔的JS散度Tab.4 JS divergence of online payment function requirement and part of service documents

本文根據抽象Web 服務的功能需求和服務描述文檔的JS 散度和經驗或者實際情況選定閾值th，為每個抽象Web 服務選出Top-k個服務構成服務組合的候選服務集合。

綜上，基于服務主題模型的服務篩選算法見算法1。

算法1 基于服務主題模型的服務篩選算法。

2.3 基于OGWO/LN的大規模Web服務組合求解

由于大規模Web 服務組合面對的候選服務數量巨大且對時間性能要求較高，為了保證服務系統能在合理的時間里組成組合服務返回給用戶，本文利用MapReduce 框架將優化的灰狼算法并行化，提高算法在解決大規模服務組合問題時的效率。

2.3.1 對灰狼算法的優化

灰狼算法（GWO）是由Mirjalili等［10］于2014 年提出的一種新型群體智能優化算法，源于對自然界中灰狼種群等級機制和捕獵行為的模擬。GWO 具有參數設置少、原理簡單等優點，在參數調整、經濟調度、成本預估等問題中已經得到廣泛的應用［11］。GWO 將灰狼按照其社會地位從高到低劃分為α狼、β狼、δ狼、ω狼四種類型來模擬自然界灰狼的領導層級，同時定義了三種灰狼的狩獵行為：包圍獵物、追捕獵物和攻擊獵物。

GWO 具有全局搜索能力強、參數設置少、收斂速度快等特點，但也存在著易陷入局部最優的問題。為了使GWO 能更好地應用到服務組合問題中，本文對GWO 進行優化。由于服務組合本質上是一個搜索問題，需要盡可能地進行全局搜索，為此，本文提出一種基于Logistic 混沌映射和非線性收斂因子的優化的灰狼算法（Optimized Grey Wolf Optimizer based on Logistic chaotic map and Nonlinear convergence factor，OGWO/LN），該算法采用談發明等［12］對灰狼算法初始種群的優化策略，用Logistic 混沌映射生成初始種群，使灰狼種群盡可能地在搜索空間中均勻分布；同時，為了提高GWO的尋優性能，提出一種非線性收斂因子來平衡算法的開發能力和探索能力。

1）混沌生成初始種群。

GWO 以初始種群為基礎，通過領導層的灰狼位置和適應度函數進行迭代運算生成新的狼群，因此初始種群的好壞會影響算法的收斂速度和生成結果的優劣［13］。GWO 是通過隨機生成的方式完成種群的初始化，這種方式生成的初始種群無法保證灰狼個體在搜索空間的均勻分布［14］，使得初始種群缺乏多樣性，算法容易陷入局部最優。

為了避免隨機生成初始種群產生的問題，本文采用Logistic 混沌映射生成初始種群，這樣可以在初始化種群階段讓個體盡可能地均勻分布在搜索空間里，提高算法的搜索效率。

Logistic 混沌映射被用于生成混沌序列，是一種由簡單的確定性系統產生的隨機性序列，映射方程如式（6）所示：

其中：∈[0，1]為在i維上的混沌變量，i=1，2，…，n表示混沌變量的序號，n表示搜索空間的維數；j=1，2，…，M表示種群序號，M表示種群規模；μ為控制變量，當μ=4時，進入完全混沌狀態。

其中：ui是第j只灰狼位置第i維的解空間大小，在服務組合問題中表示第i個服務類的候選服務規模。

2）非線性收斂因子。

群體智能算法的性能優劣體現在兩方面：一方面是探索能力即全局搜索能力；另一方面是開發能力即局部搜索能力。探索能力能夠盡可能地發現全局最優解，而開發能力能提高算法的求解精度和收斂速度［15］。如何在兩種能力之間達到平衡是群體智能算法獲得較高尋優性能的關鍵。

由于GWO 的搜索能力主要取決于A和C兩個隨機參數進行調節，而A的取值決定于收斂因子a，a在［0，2］里隨迭代次數線性遞減，這種線性遞減與算法實際收斂過程不相符［16］，所以，本文提出一種非線性收斂因子更新方式，如式（8）所示：

其中：a表示收斂因子；t表示當前迭代次數；tmax表示最大迭代次數。

收斂因子隨迭代次數的變化如圖4 所示。從圖4 中可以看出，本文提出的非線性收斂因子前期收斂速度較慢，在迭代前期可以擴大搜索范圍，易于全局搜索；后期收斂速度快，在迭代后期可以提高算法的求解效率，能夠有效地平衡全局搜索和局部搜索能力。

3）狩獵行為。

當灰狼判斷出獵物所在位置時，由灰狼α引導，灰狼β和灰狼δ作出配合進行追捕行為，其他灰狼個體ω根據灰狼α、灰狼β和灰狼δ的位置來更新自己的位置。其數學描述如式（9）～（13）所示：

其中：t表示當前的迭代次數；D表示灰狼與獵物之間的距離；A和C是系數向量；Xp（t）表示獵物的位置；X（t）表示灰狼的位置；r1和r2的模取區間［0，1］的隨機數；a為收斂因子；X1、X2、X3分別表示灰狼α、β、δ追捕獵物后的更新位置；X（t+1）表示灰狼個體ω更新后的位置。

2.3.2 MapReduce框架下基于OGWO/LN的服務組合求解

1）編碼方式。本文采用整數編碼方式表示離散的服務，每個Web 服務組合方案相當于一只灰狼，則灰狼i在空間中的位置可以定義為Xi=(xi1，xi2，…，xin)，將尋找最優組合服務問題轉化為Xi尋求最優解問題。其中，n=(1，2，…，N)，每只灰狼的位置有N維，分別對應服務組合路徑中的N個抽象Web 服務，xij表示灰狼i在第j維的位置，在服務組合過程中對應一個抽象Web 服務從候選服務集中選擇的服務編號。計算每個灰狼個體的適應度值，對該灰狼對應的服務組合方案進行評估，判斷組合服務的優劣。具體編碼模式如圖5所示。

灰狼迭代尋優過程中，其位置常有越出邊界的現象，為此本文按式（14）對超出搜索范圍的灰狼個體進行越界處理。

2）基于MapReduce 框架的大規模Web 服務組合算法求解。MapReduce 是由L?mmel［17］提出的用于處理海量數據的并行編程模型，它主要有兩個核心函數：Map 函數和Reduce函數。本文用MapReduce 模型將OGWO/LN 并行化以解決大規模服務組合問題。

在種群初始化階段，用Logistic 混沌映射生成N只灰狼的初始種群并計算出每只灰狼的適應度值，找出適應度排名前三的三只灰狼，將初始狼群以文件的形式存儲在分布式文件系統HDFS中，作為第一個MapReduce Job 的輸入。文件中的灰狼信息以鍵值對的形式存放，每只灰狼占一行，Key 是灰狼的編號，Value 是灰狼的相關信息，灰狼的結構如表5 所示。

表5 鍵值對結構Tab.5 Structure of key-value pair

其中，灰狼的位置Xi=(xi1，xi2，…，xin)，n表示抽象Web服務的個數，排名前三的灰狼及其適應度值分別為lbestagent，fitness（lbestagent），lsecondagent，fitness（lsecondagent），lthirdagent，fitness（lthirdagent）。

在MapReduce 階段，每個Job 代表OGWO/LN 的一次迭代過程，一次Job 的輸出結果為更新位置后的新狼群，該狼群作為下次迭代的輸入。

在Map 階段，每個Map 任務完成每一代狼群的位置更新操作，并更新每個子群的適應度前三的灰狼信息。Map 函數如算法2 所示。

算法2 Map Procedure。

在Reduce 階段，Reduce 任務從各個Map 階段得到的局部前三只灰狼中找出當前種群的全局前三，然后更新種群中所有灰狼的信息，輸出完整更新后的種群，新種群代替舊種群作為下一次迭代的輸入。Reduce 函數如算法3 所示。

算法3 Reduce Procedure。

3 實驗與結果分析

3.1 數據集與實驗設置

3.1.1 數據集

本文采用WSDream［18］和API_PGW 的混合數據集。WSDream 數據集記錄了142 個用戶每15 min調用4 500 個Web 服務的真實響應時間和吞吐量兩個屬性值。API_PGW數據集是由石敏等［19］2016 年從ProgrammableWeb 網站爬取的12 920 個服務和本文從ProgrammableWeb 網站爬取的5 345 個服務組成，共18 265 個服務，每個服務都有服務名稱、服務描述和所屬類別。

本文按照以下規則將QoS 數據填充到API_PGW 數據集中。QoS 數據來自WSDream 數據集，并且經過了歸一化以減少波動性，服務描述來自API_PGW 數據集。

1）對于API_PGW 中同一類的服務，本文從WSDream 數據集中獲取一個用戶調用不同服務的QoS 數據。

2）不同類別的服務獲取不同用戶調用的QoS 數據。

根據上述數據混合規則，得到了一個新的混合數據集，同時包含QoS 數據和服務描述。

3.1.2 實驗環境

操作系統為Windows10 64位，Intel Core i5-8265U GPU@1.60 GHz，RAM 16.0 GB，PyCharm 2019，Python 3.6.1。Hadoop 平臺是由3 臺虛擬機搭建的小型集群，其中一臺作為Master 節點，其他兩臺為Slaver 節點，虛擬機的配置為CentOS7，RAM 2 GB，Intel Core i5-8265U GPU@ 1.60 GHz，Hadoop 2.9.2，Java 運行環境是JDK1.8。

3.1.3 參數設置

1）主題數目K的確定。

本文使用Stevens等［20］的方法通過主題一致性來確定主題K的個數。圖6 為不同主題數的主題一致性值，選取曲線趨于平穩前的最大值作為K值，故選取K為60 對服務主題模型進行訓練。

2）JS 散度閾值th的確定。

本文根據圖2 的抽象服務組合序列進行實驗，序列中含有6 個抽象Web 服務。根據本文基于服務主題模型的服務篩選方法，需要確定JS 散度的閾值th。

精確率（Precision）是服務發現中最常用的度量指標，所以本文通過比較不同JS 散度閾值th下的查找服務的準確率情況來確定閾值。Precision@n表示檢索返回的文檔集中與查詢語句相關的文檔所占比例，如式（15）所示：

其中：L表示查詢到的正確的服務條數；n表示查詢到的服務條數。

不同JS 散度閾值對服務發現精確率的影響如圖7 所示。當JS 散度閾值在0.04 到0.08 之間時精確率呈上升趨勢，當JS 散度閾值在0.08 到0.10 之間時，精確率呈下降趨勢。綜合考慮不同JS 散度閾值對精確率的影響，本文實驗將JS 散度閾值th設置為0.08，從而根據主題相似度確定6 個抽象Web 服務的候選服務數量分別為285、146、163、374、46、147。可組合的服務組合方案超過1011種，可以稱得上是大規模Web 服務組合。

3）對比算法參數設置。

為了驗證OGWO/LN 在服務組合優化中的性能，將本文與算法IFOA4WSC（Improved Fruit Fly Optimization Algorithm for Web Service Composition，IFOA4WSC）［6］、MR-IDPSO（MapReduce based on Improved Discrete Particle Swarm Optimization，MR-IDPSO）［8］、MR-GA（MapReduce based on Genetic Algorithm，MR-GA）［21］進行比較。在所有的實驗中，種群的數量都固定為100。在IFOA4WSC中，學習因子c1和c2的取值范圍均為［0.5，2］，慣性權重取值范圍為［0.1，0.3］，δ、η在［0，1］上隨機選取。在MR-GA中，參數設置采用隨機選擇方法，交叉和變異的概率分別設為0.8 和0.1。在MR-IDPSO中，慣性權重從0.9 到0.7 線性變化，學習因子c1和c2取2。由于智能算法的隨機性，每次實驗運行20 次并取平均值，最大迭代次數為100，兩種非功能屬性（響應時間、吞吐量）對應的權值分別設置為0.6、0.4。

3.2 實驗結果分析

為了驗證不同算法在解決大規模服務組合問題時的尋優性能表現，比較4 種算法在不同迭代次數下的組合服務質量。通過計算服務組合的適應度值來對比分析4 種算法的尋優性能，根據本文實驗定義的適應度值表示組合服務的服務質量，適應度值越大時表示組合服務的質量越好。實驗結果如圖8 和表6 所示。

表6 四種算法的性能比較Tab.6 Performance comparison of four algorithms

圖8 中縱坐標表示運行20 次的平均適應度值。從圖8中可以看出，隨著迭代次數的增加，服務組合的平均適應度值逐漸提高，并且OGWO/LN 的平均適應度值在不同迭代次數下都明顯高于其他3 種算法。

表6 表示不同算法在迭代100 次、運行20 次時的最大、最小、平均適應度值和均方差。平均適應度值越高，表示算法的尋優性能越高，均方差越低，表示算法的穩定性越好。從 表6 中可以看出，相較于IFOA4WSC［6］、MR-IDPSO［8］和MR-GA［21］，本文算法的平均適應度值分別提高了8.69%、7.94%和12.25%。因此，本文算法在相同服務類個數、服務組合規模下，OGWO/LN 在解決大規模服務組合問題上的整體性能優勢明顯，平均適應度值最佳且穩定性最好。

以上的實驗結果驗證了本文提出的大規模Web 服務組合方法可以有效地選出QoS 適應度值最優的組合，有效地解決大規模服務組合問題。

4 結語

本文分析了大規模Web 服務組合的特點和組合過程中面臨的海量規模、跨界環境等挑戰。為了應對以上挑戰，提出了一種在復雜環境下的大規模Web 服務組合方法，可以有效地應對服務的海量規模，同時實現組合服務的質量最優。該方法首先采用LDA 主題模型建立服務主題模型對服務進行篩選，以縮減服務組合的搜索空間；其次，采用MapReduce框架并行實現OGWO/LN，為每個抽象Web 服務選出合適的服務提高服務組合的整體質量。最后通過一系列對比實驗結果表明，OGWO/LN 相較于其他算法，在解決大規模場景中的Web 組合問題時，在質量上有著更優的效果，并且有著更強的穩定性。未來將進一步研究如何提高服務篩選的精度和復雜服務生態系統中服務質量的影響因素，從而更好地衡量服務質量，選出適合當今服務環境的組合服務。