張 曄，鮑 亮

(1.中國電子科技集團公司第三十研究所，四川 成都 610041；2.西安電子科技大學 計算機科學與技術學院，陜西 西安 710071)

互聯(lián)網的應用開發(fā)中已經出現(xiàn)了大量的Web服務，每個服務提供特定的功能。單獨的個體服務已經無法滿足日益復雜的用戶需求，越來越多的實際項目需要將Web服務組合進行集成，以便提供更優(yōu)的功能。服務組合技術可將現(xiàn)有的多個服務以特定的方式組合成一個高質量、高性能的邏輯整體，來滿足用戶的功能需求。服務組合技術在原有服務的基礎上生成新的增值服務，使得系統(tǒng)功能可以靈活地擴展。不同服務提供商提供的功能相似的服務一般具有不同的服務質量(Quality of Service，QoS)，包括價格、吞吐量、傳輸延遲、錯誤率等。服務組合需要生成既滿足相應QoS約束，又能實現(xiàn)用戶需求功能的最優(yōu)或者接近最優(yōu)的組合服務[1]。

計算機技術與人工智能的飛速發(fā)展間接性帶動了服務組合領域的進步。研究人員將人工智能領域的知識與傳統(tǒng)服務組合技術結合起來，將智能化的思想引入服務組合中，推動服務組合的發(fā)展。機器學習使得服務組合算法擁有了一定的自主學習能力，從而使其能夠更好地適應愈加復雜的環(huán)境。

互聯(lián)網的高速發(fā)展使得服務的數(shù)量規(guī)模日益增大，服務組合的方法也需要與時俱進來適應不斷變化的復雜環(huán)境。本文將對服務組合問題進行系統(tǒng)性的介紹：首先，介紹服務組合的分類、服務組合問題所面臨的挑戰(zhàn)以及最新的人工智能在服務組合上的應用；然后，對服務組合的問題進行總結；最后，對今后的發(fā)展方向進行展望。

1 服務組合問題的分類

服務組合問題是服務計算領域中的經典問題，其經過數(shù)十年的發(fā)展，已產生了多種分支。根據(jù)不同的劃分標準，可將現(xiàn)有的服務組合問題劃分為不同種類。本章節(jié)簡要介紹了3種常見的劃分標準：(1)是否已知業(yè)務的工作流；(2)優(yōu)化目標的種類；(3)多目標優(yōu)化方式。

1.1 是否已知組合服務的工作流

組合服務的工作流是指多個子功能按照它們之間的數(shù)據(jù)流構成的工作流程，此工作流程滿足用戶提供的輸入輸出需求。目前已有多種方法可用于生成組合服務的抽象工作流，例如路徑查找策略[2]。已知用戶所需組合服務的工作流，目的是在子功能對應的候選服務集內挑選出具體服務以優(yōu)化其組合目標的問題，被稱為半自動服務組合問題[3]。目前，針對半自動服務組合問題已有大量研究[4-6]。然而，在實踐中通常難以提供這樣的工作流程，這也限制了半自動服務組合方法的適用性。服務組合問題的另一分支，即全自動服務組合問題[3]，逐漸受到了關注。全自動服務組合問題根據(jù)用戶提供的輸入輸出參數(shù)挑選具體服務進行連接，并在此過程中同時進行目標的優(yōu)化[7-9]。

1.2 優(yōu)化目標的種類

服務組合問題具有不同的應用背景，例如云上服務組合、物聯(lián)網中的服務組合等，因此也具有不同的優(yōu)化目標。本文將優(yōu)化目標分為兩類：(1)基于QoS的服務組合問題。QoS是對服務非功能質量的定性或定量通用評價標準，包括服務響應時間、成本、可用性、成功執(zhí)行率、吞吐率等?；赒oS的服務組合問題旨在得出一個整體QoS較好的服務組合方案[10]；(2)基于其它優(yōu)化目標的服務組合問題。除了QoS之外，基于不同的應用背景，還需考慮額外的優(yōu)化目標，例如組合服務的子服務數(shù)量[11]、組合服務的網絡QoS[12]、服務運行資源[13]等。

1.3 目標優(yōu)化方式

服務組合問題往往需要同時優(yōu)化多個目標。基于不同的考量，不同研究使用了不同方式進行目標優(yōu)化：(1)多目標優(yōu)化[14]。最直觀的方式是將服務組合問題直接建模為多目標優(yōu)化問題，并利用多目標優(yōu)化算法尋找帕累托最優(yōu)解集；(2)轉化為單目標進行優(yōu)化[15]。多目標算法的求解難度往往較大，因此有許多研究為每個優(yōu)化目標賦予不同權重，并將多個目標根據(jù)權重加權形成一個單一指標，從而將多目標優(yōu)化問題簡化為單目標優(yōu)化問題。但是，這種做法在簡化問題求解難度的同時，也帶來了局限性。在實際應用中，使用該方法無法給出相應權重。

2 服務組合問題面臨的挑戰(zhàn)

隨著人工智能、互聯(lián)網等領域的飛速發(fā)展，“服務組合智能化”成為了研究人員新的目標方向。服務組合雖然在過去的數(shù)十年間取得了一定的成果，但受制于傳統(tǒng)思想方法的局限性，有關服務組合的理論體系、工程方法、應用技術等方面還不夠成熟，服務組合智能化道路仍有較多的問題需要解決，其中的主要問題為：

(1)動態(tài)的Web環(huán)境。服務是應用于網絡層面的，而網絡是不穩(wěn)定的，因此網絡的波動會導致QoS產生一定的變化，有些服務會因為環(huán)境的變化而失效，同時又會有新的服務出現(xiàn)。因此，需使服務組合算法具有動態(tài)性和可擴展性，以便適應復雜的環(huán)境；

(2)大規(guī)模的服務組合問題。隨著互聯(lián)網行業(yè)的飛速發(fā)展，服務的數(shù)目也在迅速增多，從過去的數(shù)十個擴增到如今的數(shù)萬規(guī)模。從海量的候選服務中挑選出滿足用戶需求的組合服務，不僅需要提高算法的準確性，更要降低計算時間，減少服務成本；

(3)QoS約束。服務組合問題不僅要求構建出功能滿足用戶需求的增值服務，還需要滿足用戶的QoS需求，例如用戶若對服務的實時性需求較高，則其可能會要求整體響應時間小于某一閾值；

(4)QoS依賴。在許多情況下，服務的 QoS 與其他服務相關。當可以從多個系統(tǒng)調用服務時，選擇來自同一個系統(tǒng)的服務進行調用，能夠在一定程度上降低工作成本。當調用了某一個系統(tǒng)的服務時，再次調用其系統(tǒng)的其它服務則會降低操作難度；

(5)QoS的數(shù)目?，F(xiàn)有的研究考慮QoS較少，大多數(shù)的研究僅挑選少數(shù)QoS進行實驗比較，目前缺少考慮了大量QoS的實驗；

(6)現(xiàn)實物理環(huán)境。服務組合除了要考慮動態(tài)的虛擬環(huán)境，某些情況下也受到現(xiàn)實物理環(huán)境的限制。在物聯(lián)網中，實際的物理環(huán)境、物理地址也會影響到服務的QoS。在處理這種服務組合問題時，將現(xiàn)實環(huán)境的影響因素結合起來也是一個難點。

3 機器學習在服務組合問題中的應用

伴隨著網絡技術的飛速發(fā)展，Web服務組合的環(huán)境也越來越復雜。人工智能的飛速發(fā)展使得智能化的思想被越來越多地應用于服務組合，機器學習與服務組合的結合已成為該領域的發(fā)展潮流。機器學習就是讓計算機擁有像人類一樣的學習能力，能夠從過往的經驗中總結規(guī)律形成某種認知，從而對未來的新事物進行判斷。計算機通過機器學習算法對大量原始數(shù)據(jù)訓練總結出模型，用模型來對新的情景進行判斷處理。強化學習是機器學習的一個分支，不需要預先的指導，能夠在無標記的數(shù)據(jù)中展現(xiàn)有效的學習能力，通過接收環(huán)境狀態(tài)對動作的反饋從而獲得學習信息，更加接近于人的學習行為。對比某些傳統(tǒng)的算法，強化學習可以實現(xiàn)無模型的、端對端的、狀態(tài)到動作的高維映射關系的自學習，它的自學習能力可以泛化到各種各樣的情況中。深度學習是用于建立、模擬人腦進行分析學習的神經網絡，并模仿人腦的機制來解釋數(shù)據(jù)的一種機器學習技術，對比與傳統(tǒng)方法，其具有效率高、可塑性強、普適性好的特點。將強化學習、深度學習等機器學習算法與服務組合結合起來，已經成為了當下研究的主流方向。

根據(jù)機器學習算法在服務組合問題中起到的作用，可以將其劃分為兩類：(1)求解組合方案的算法。這些算法中，機器學習是算法的主體部分，為用戶提供最終的組合方案；(2)起到輔助增強作用的算法。這些算法中，機器學習是服務組合算法的子步驟，為主體算法提供前置條件或輔助增強主體算法。

3.1 求解組合方案的算法

強化學習算法是最常被用于解決服務組合問題的機器學習算法。該算法中，代理通過不斷地與環(huán)境交互，試圖找到累計回報最大的策略，進而得出最優(yōu)組合方案。近年來，基于強化學習的服務組合方向不斷有新的研究出現(xiàn)，是一個重要的研究方向。

文獻[16]為提升強化學習算法的效率，并使其適用于大規(guī)模服務環(huán)境，提出了一種在動態(tài)和大規(guī)模環(huán)境中自適應服務組合的方法。該方法采用基于平鋪卷積濾波器的Double Q-Learning網絡，逐步建立了大規(guī)模服務環(huán)境的準確抽象。文獻[17]將離散哈密頓力學、分布式多智能體控制、最優(yōu)控制理論和博弈論結合起來，提出了一種多主體強化學習算法。文獻[18]設計了基于馬爾可夫決策過程的Web服務組合優(yōu)化模型(Web Service Composition Markov Decision Processes，WSC-MDP)，提出了多目標智能體強化學習的分布式Q-learning算法。文獻[19]提出了一種多代理的分布式Q-learning算法，將服務組合任務分解為多個子任務，使每個代理專注于自己的子任務，以加快收斂速度，此外該算法還引入了經驗分享策略以提高效率，從而增加對不斷變化環(huán)境的適應能力。文獻[20]記錄了服務每一次實際運行的QoS，利用歷史QoS模擬動態(tài)環(huán)境，針對QoS的不確定性提出了一種具有自適應性的Q-Learning算法，滿足了用戶的QoS約束。文獻[21]提出了一種利用長短期記憶網絡(Long Short-Term Memory，LSTM)改進Deep Q-Learning的服務組合優(yōu)化方法。相對于傳統(tǒng)方法，該方法在大規(guī)模服務環(huán)境下計算速度更快，服務組合成功率更高，具有更強的處理能力和處理效率。文獻[22]將循環(huán)神經網絡(Recurrent Neural Network，RNN)與強化學習結合起來，提出了基于LSTM的自適應深度Q-Learning框架，用深度學習模擬服務組合狀態(tài)問題，以形成擬合的Q值曲面，用作在線啟發(fā)式函數(shù)以啟發(fā)后續(xù)的強化學習。文獻[23]也將深度學習與強化學習相結合，用深度強化學習來解決大規(guī)模服務組合問題。文獻[24]將服務組合問題建模為部分可觀察的馬爾可夫決策過程，提出了一狀態(tài)一網絡(One State One Network，OSON-WSC)框架，通過啟發(fā)式方式將狀態(tài)分為隱藏狀態(tài)和完全可觀測狀態(tài)，為兩種狀態(tài)分別訓練不同的策略。為了能夠在用戶無需太多手動說明的情況下組合個性化服務，文獻[25]使用排名學習算法RankBoost，根據(jù)用戶的歷史數(shù)據(jù)自動學習用戶偏好并確定偏好的優(yōu)先級。隨后，該研究使用多目標強化學習(Multi-Objective Reinforcement Learning，MORL)算法在用戶偏好之間進行權衡，并推薦一組服務以實現(xiàn)最高目標。文獻[1]將天際線技術與強化學習相結合，通過從候選服務中提前選用高質量的服務，減少了搜索空間，降低了時間復雜度，并使用Q-Learning來進行服務選擇。這種方法提高了搜索效率，使得服務組合在面對大規(guī)模問題時有了更好的解決效果。

求解組合方案的機器學習算法的相關應用如表1所示。

表1 求解組合方案的算法總結

由表1可以看出，近年來，強化學習是機器學習算法中最常被用于服務組合問題的算法。無模型的強化學習算法中，代理與環(huán)境不斷交互得到立即回報并發(fā)生狀態(tài)的轉移。通過這種交互信息，代理能夠捕捉到環(huán)境的變化，并通過調整模型參數(shù)自動適應環(huán)境的動態(tài)性。因此，強化學習適用于解決服務組合問題所面臨的服務及QoS不穩(wěn)定的問題。

3.2 起到輔助增強作用的算法

除了直接將機器學習算法用于求解組合方案外，研究人員還將機器學習算法與其他算法結合起來。在這種聯(lián)合算法中，機器學習算法不直接承擔求解組合方案的功能，而是作為一個輔助增強環(huán)節(jié)，或是作為主算法的預處理步驟，來幫助減小主算法的求解難度，提升求解效果。

聚類算法是服務組合中常用的算法，主要用于對服務進行聚簇，從而在服務組合算法開始前過濾出無需考慮的服務，減小搜索空間，降低求解難度，提高求解速度；該算法還可根據(jù)服務的功能屬性對服務進行聚簇，形成候選服務集，進而構建出組合服務的工作流等。文獻[26]使用基于信任的k均值聚類算法(k-means)集群化搜索空間，并使用蜜蜂交配優(yōu)化算法實現(xiàn)全局優(yōu)化，不僅改善了算法的響應時間，還能夠選擇出更多受信任的服務。文獻[27]使用基于概念的相似度對服務進行聚類，隨后根據(jù)每個聚類簇的輸入輸出參數(shù)，構建抽象服務網絡；然后，針對用戶請求從后往前查詢合適的路徑，并在尋找的過程中，進一步過濾候選服務集；最終，得出候選服務集及工作流。文獻[28]用聚類的方法來考慮全局QoS約束，通過k-means聚類的方法將各個候選服務分組到各個集群當中，不同集群代表不同QoS級別。該研究提出了一種基于所得群集特征的效用函數(shù)公式來消除不滿足用戶需求的候選服務方法，通過減少候選服務的數(shù)量來縮短組合服務的合成時間。文獻[29]提出了一種集群指導遺傳算法(Genetic Algorithm，GA)的算法，解決了數(shù)據(jù)密集型服務組合問題。該方法根據(jù)Web服務的成對距離，采用k-means聚類將其分組到集群中獲得初始群落，減少了局部最優(yōu)的影響；然后，對每個集群計算平均適應度值，根據(jù)平均適應度值對集群重新排序，進而迭代后代，生成更優(yōu)服務集[30]。文獻[4]借鑒了聚類的思路，使用孿生支撐向量機(Twin Support Vector Machine，TWSVM)來劃分候選服務，用大腦風暴優(yōu)化作為搜索方案，并采用自適應對偶策略來生成高質量的組合服務。

由于服務組合是一種長期的經濟策略，而服務QoS又具有不穩(wěn)定性，因此很多研究試圖預測出服務的未來QoS變化趨勢，從而構建出長期有效的服務組合方案。文獻[31]提出了一種基于深度學習的服務組合(Deep Learning Service Composition，DLSC)框架，應用LSTM網絡來預測未來一段時間內的服務QoS，并使用粒子群優(yōu)化算法組成最佳的組合服務，以便最大程度地降低消費者成本。文獻[32]同樣使用LSTM網絡預測服務未來的QoS，并使用預測的QoS值和用戶對QoS的可接受及偏好范圍，在長期服務組合中準確推薦服務和替換服務，增強了任何現(xiàn)有的組合和替換技術。文獻[33]在馬爾可夫決策的基礎上新定義了動態(tài)Web服務組合模型，并使用LSTM通過過去的數(shù)據(jù)預測出未來的QoS，繼而采用Q學習進行服務選擇。

除了直接使用強化學習進行服務組合外，強化學習也常用于作為元啟發(fā)式方法的增強步驟。文獻[34]認為GA的性能很大程度上取決于初始種群，因此研究人員利用Q-Learning算法生成初始種群以提升GA的效率。

本文將起到輔助增強作用的機器學習算法的應用進行了總結。由表 2可以看出，機器學習中聚類和序列預測算法是最常被用于解決服務組合問題的方法。

表2 起到輔助增強作用的算法總結

4 結束語

本文首先介紹了服務組合問題的幾種分類標準和目前服務組合問題主要面臨的挑戰(zhàn)，隨后總結了機器學習算法在服務組合問題中的兩種應用方向。由上述介紹可以看出，機器學習算法在服務組合領域中具有良好的應用前景，同時也面臨著一些問題：(1)缺乏高質量的數(shù)據(jù)集。許多研究在解決環(huán)境的動態(tài)性問題時，由于缺乏真實的歷史記錄數(shù)據(jù)，只能人工假設數(shù)據(jù)的分布，進而模擬環(huán)境的變化。但這種操作缺乏真實性，且收集數(shù)據(jù)集也增加了工作量；(2)對動態(tài)環(huán)境的自適應性不強?，F(xiàn)有基于強化學習的服務組合算法中，許多算法通過實際執(zhí)行服務獲取立即回報，從而調整參數(shù)。但該操作會降低算法的實時性和實用性；(3)算法運行效率較低。在現(xiàn)有基于強化學習的服務組合算法中，許多算法無法學習組合的經驗，對于新的組合需求，總需要重新進行訓練，與傳統(tǒng)方法相比，效率并沒有顯著提高。

基于以上問題，機器學習算法在服務組合領域上的發(fā)展方向主要為：(1)收集數(shù)據(jù)，在服務組合領域內形成公認的有效數(shù)據(jù)集；(2)利用服務的歷史QoS信息構造長期可用的服務組合，或改進強化學習模型，使其通過與模擬環(huán)境進行離線訓練，學習針對部分執(zhí)行完畢的服務組合做下一步行動；(3)設計強化學習中代理的狀態(tài)表示，使狀態(tài)中包含盡量多的服務組合全局信息，從而使強化學習學到服務組合問題的通用策略。

機器學習算法在服務組合領域中仍然具有較大的發(fā)展空間與潛力，在服務組合領域中也將出現(xiàn)更多實用性與創(chuàng)新性并存的研究。