基于自適應多目標強化學習的服務集成方法

郭瀟，李春山，張宇躍，初佃輝

基于自適應多目標強化學習的服務集成方法

郭瀟，李春山*，張宇躍，初佃輝

（哈爾濱工業大學（威海） 計算機科學與技術學院，山東 威海 264209）（?通信作者電子郵箱lics@hit.edu.cn）

當前服務互聯網（IoS）中的服務資源呈現精細化、專業化的趨勢，功能單一的服務無法滿足用戶復雜多變的需求，服務集成調度方法已經成為服務計算領域的熱點。現有的服務集成調度方法大都只考慮用戶需求的滿足，未考慮IoS生態系統的可持續性。針對上述問題，提出一種基于自適應多目標強化學習的服務集成方法，該方法在異步優勢演員評論家（A3C）算法的框架下引入多目標優化策略，從而在滿足用戶需求的同時保證IoS生態系統的健康發展。所提方法可以根據遺憾值對多目標值集成權重進行動態調整，改善多目標強化學習中子目標值不平衡的現象。在真實大規模服務環境下進行了服務集成驗證，實驗結果表明所提方法相對于傳統機器學習方法在大規模服務環境下求解速度更快；相較于權重固定的強化學習（RL），各目標的求解質量更均衡。

服務集成；強化學習；異步優勢演員評論家算法；多目標優化；自適應權重

0 引言

服務互聯網（Internet of Services， IoS）是由跨網跨域跨世界的服務構成的復雜服務網絡形態。通過互聯網與新一代信息技術感知大規模個性化顧客需求，IoS可以高效聚合互聯網中的異構跨域服務，形成適應性的綜合服務解決方案和價值鏈，為顧客及相關參與方帶來價值［1-2］。本質上，IoS是基于各種服務網絡疊聚，由海量異質跨界跨域的服務組成的、動態演化的復雜系統。每個服務能夠解決或部分解決客戶需求，都有對應的服務提供商，并可根據服務功能的相似性聚集形成一定的服務種群。

由于IoS中的服務精細化、專業化的趨勢，導致服務提供商將服務的功能具體化、單一化。明顯地，功能單一的服務無法滿足用戶復雜多變的需求。例如，某用戶提出個人的服務需求“2021年8月在威海短期旅游一周”，這個需求包含了衣、食、住、行、景點、安全等多方面的要求。然而在真實服務場景中不存在一個服務能滿足上述所有需求，需要第三方服務平臺對服務資源進行集成和調度，形成服務資源的集合來滿足用戶需求。因此，許多科學家提出了服務集成調度方法，將多個服務組合成為一個服務集來滿足用戶需求。

上述方法存在兩個缺陷：首先，傳統方法大都只考慮用戶需求的滿足，未考慮IoS生態系統的可持續性。采用這些方法進行服務集成，會導致某些服務被頻繁地調用，其他服務處于空閑狀態。長此以往，IoS生態將會萎縮，變成少數服務提供商的自留地。其次，傳統的多目標優化模型需要在初始階段人工設定各個目標的權重，如果權重設置不當，會導致最終服務決策質量的降低。

針對上述問題，本文提出了基于自適應多目標強化學習的服務集成模型。該模型首先在基于馬爾可夫決策過程（Markov Decision Process， MDP）的強化學習（Reinforcement Learning， RL）框架下對服務集成調度問題進行建模和形式化；然后選擇異步優勢演員評論家（Asynchronous Advantage Actor?Critic， A3C）算法框架下的RL算法作為模型的主體算法，再結合多目標優化策略使集成模型可以在滿足用戶功能需求的同時促進服務生態網絡健康發展；最后引入權重自適應方法平衡各子目標回報值，使每個子目標回報值在循環迭代的過程中保持增長。

1 相關工作

隨著IoS的不斷發展，更多的服務組合方法被提出。張龍昌等［3］利用服務之間的余弦相似性，根據服務質量（Quality of Service， QoS）屬性對Web服務進行組合。他們提出了一種基于多屬性決策理論的混合QoS組合的Web服務組合算法CHQoS?WSCA，可用于評價由實數、區間值、三角模糊數和直覺模糊數描述的QoS信息。朱志良等［4］建立了Web服務的QoS屬性相似度模型和功能屬性相似度模型。服務之間的相似性可以從不同的角度來度量，Web服務的組合是通過語義相似性實現的。Tripathy等［5］提出了一種基于圖的服務組合多粒度組合和選擇模型。在該模型中，每個節點被表示為一個服務簇，通過Bellman-Ford算法找到最短路徑，從而得到最優組合結果。Wu等［6］對所有滿足用戶需求的服務進行了組合，然后查找服務集群以找到合適的服務來替換組合過程中不可用的服務。Abdullah等［7］通過人工智能編程提出了一種新的服務組合模型。該模型生成了一個基于I/O集群技術的分層任務網絡（Hierarchical Task Network， HTN），以實現服務集群規劃。他們還提出了一種基于功能屬性類的Web服務聚合方法，可以有效地生成HTN問題域。Cai等［8］首先根據輸入和輸出參數的相似性對所有功能相似的服務進行組合；然后使用服務日志決定要選擇的服務；最后，通過反饋機制返回用戶的反饋，提高下一個用戶的滿意度。Bianchini等［9］基于本體論將服務分為三個不同的級別，從服務描述中獲取語義關系，通過語義關系生成本體結構，通過輸入、輸出和功能相似性建立服務發現模型，實現服務的發現和組合。Wang等［10］提出了一種半經驗的組合方法，以實現規則組合和實時組合，通過相似性度量將具體服務和歷史需求劃分為不同的簇，然后通過統計分析確定服務簇和需求簇之間的對應概率。

上述研究大多從QoS角度考慮服務組合，這導致QoS高的服務被大量使用，使整個服務生態系統出現寡占性強的特性，不利于IoS的健康發展。而且在多個目標值（QoS值）集成時需要用到先驗知識設定各目標權重，而大多數情況下服務提供平臺缺少這種先驗知識。因此需要一種既能夠滿足用戶功能需求又可以保證服務生態系統健康發展且可以自適應調整多目標值權重的方法。

2 基于自適應多目標強化學習的服務集成

本文提出的基于自適應多目標強化學習的服務集成方法首先使用基于MDP的強化學習對服務集成問題集成形式化定義，然后選擇A3C框架下的強化學習算法作為模型的主體算法，再結合多目標優化算法使該模型集成的服務組合可以在滿足用戶功能需求的同時促進服務生態網絡健康發展，最后引入權重自適應方法平衡各子目標回報值，使每個子目標回報值增速在循環迭代的過程中保持增長。

2.1　形式化定義

由于在開放和動態環境中使用RL進行服務集成具有明顯的優勢，首先在基于MDP的RL框架下形式化定義IoS環境中的服務集成問題。MDP是離散時間隨機控制過程，特別用于對不確定域中的順序決策進行建模。MDP的關鍵組成部分正式定義［11］如下：

在IoS環境下，需要在MDP框架下形式化定義服務集成：

2.2　面向多目標強化學習的服務集成方法

完成服務集成問題的形式化定義后，需要選取具體的RL框架解決服務集成問題。基于價值的RL方法可以單步更新網絡的超參數，但該方法通過預測動作的價值間接得到最優動作，適用于離散有限動作的RL任務。基于策略的RL方法雖然可以直接預測動作，但是一個情節結束之后才能夠逆向更新網絡的超參數，導致超參數更新較慢。相較于基于價值的RL方法，基于策略梯度的RL方法更適用于連續動作決策的RL任務。演員評論家（Actor?Critic， AC）模型結合了上述兩種方法的優點，既能夠有限步更新網絡的超參數，也能夠直接預測狀態的動作［13］。AC模型框架如圖1所示。

圖1　AC模型框架

本文選擇A3C算法作為服務集成問題的基礎算法，該方法是目前基于AC模型表現得最好的框架之一。

多目標強化學習不同于傳統RL的點在于學習Agent同時要優化多個目標，每一步學習Agent得到一個回報向量，而不是一個標量值［14］。

權重向量本身應該滿足方程：

在IoS中，同時考慮用戶本身的功能需求以及服務生態系統的健康發展，將用戶需求的功能匹配和服務網絡系統的復雜性作為多目標優化的子目標值。目前對網絡系統的復雜性的研究主要體現在結構復雜性、節點復雜性以及各種復雜性因素之間的相互影響等領域上，包括小世界特性、無標度特性、度匹配特性等。本節主要借鑒文獻［15］的定義與Qi等［16］構建的服務生態系統演化指標體系，在該體系下對服務生態系統的組織結構的復雜度進行分析。

2.2.1小世界特性

小世界網絡模型主要包括Watts和Strogatz提出的WS小世界模型［17］和Newman和Watts提出的NW小世界模型［18］。小世界網絡的核心特征為特征路徑長度短而集聚系數高。其中特征路徑長度（Characteristic Path Length， CPL）表示網絡的平均路徑長度，其定義為：

集聚系數描述網絡當中節點的鄰接節點之間也互相鄰接的比例，因此可以定義為：

為了對網絡的小世界特性進行量化，Watts和Strogtz進一步將小世界網絡與具有相同連邊概率的ER隨機網絡進行比較，并將具有與隨機網絡相似的特征路徑長度但是比隨機網絡高得多的集聚系數的網絡定義為小世界網絡。因此小世界特性的量化標準為：

2.2.2無標度特性

無標度特性指網絡當中的分布滿足冪律分布特征，由Barabasi和Albert于1999年提出［19］。在無標度網絡當中絕大多數的節點的度非常低，而少部分的節點的度則非常高，在整個網絡當中占據核心的位置。目前對網絡的無標度特性進行量化分析主要有兩種方法：

2.2.3度匹配特性

Newman［21］對于識別網絡節點之間的匹配關系進行了量化，進一步提出了網絡整體的匹配系數：

本文將利用Pastor?Satorras等的方法識別網絡的匹配性，利用Newman的匹配系統量化網絡的匹配程度。

2.3　權重自適應多目標服務集成算法

在單個Agent中只需要考慮到自己，把自己優化得最好就可以了，但是涉及多Agent，研究多個Agent之間的關系以提升整體效果或者完成多Agent的目標任務時，需要參考博弈論的成果［22-24］：

遺憾的是指學習器現實的收益與學習器使用某種固定策略獲得的最大收益之間的差異，即

再根據式（16）保證權重總和為1：

最終服務集成算法如算法1所示。

算法1 權重自適應A3C多目標強化學習算法。

13） End for

17） End while

24） End for

26） End while

3 實驗與結果分析

3.1　實驗設置

本文提出的服務集成方法在連續迭代循環中運行，直到達到收斂點。由于傳統機器學習算法無法在連續狀態空間中運行，而自適應權重會導致狀態空間連續，因此分別將基于蟻群算法的多目標服務集成算法和基于A3C強化學習算法的多目標自適應權重服務集成算法與基于A3C強化學習算法的多目標集成算法進行對比，比較它們的求解速度、求解質量以及各目標求解質量。

所有模擬實驗都于搭載四核心Intel Core i5?6300HQ CPU的個人計算機上運行，內存為16 GB，采用Windows系統運行Pycharm軟件，利用Python語言編寫程序。蟻群算法與A3C強化學習算法各項參數如表1所示。

表1　蟻群算法與強化學習算法參數設置

3.2　實驗數據

測試環境中子目標數量固定為四個，分別為：功能匹配、小世界特性、無標度特性和度匹配特性，其可用的具體服務共946個。

3.3　實驗結果

將通過兩組實驗分別對比三種算法的求解速度和求解質量與子目標求解質量，其中總目標值為各子目標值加權相加。

三種算法總目標值與迭代次數的關系如圖2所示；三種算法總目標值與收斂時間的關系如圖3所示。由圖2、3可以看出，由于環境規模較大，傳統機器學習算法收斂速度比A3C強化學習算法慢得多。從迭代次數來看，強化學習算法在40次迭代以內便可收斂，而蟻群算法則需要至少220次迭代，從收斂時間來看強化學習算法也有著明顯的優勢。而兩種算法在整個學習過程中獲得的累計回報基本相同，說明A3C強化學習算法在保證求解質量的同時能夠保證較快的求解速度。而對于權重固定與自適應的多目標強化學習算法的收斂速度相近、總回報值相近，說明權重自適應的多目標優化算法不會影響算法的整體求解速度與求解質量。

圖2　三種算法總目標值?迭代次數圖

圖3　三種算法總目標值?時間圖

三種算法子目標回報值與迭代次數的關系如圖4所示。在這里選取功能匹配與小世界特性兩個子目標進行分析，其中圖4（b）表示小世界特性目標回報值，圖4（c）表示功能匹配目標回報值。

圖4　三種算法子目標值?迭代次數圖

由圖4可以看出，在三種算法總目標求解質量相近的基礎上，在冪率分布特性這一子目標下也有相同的求解質量，整體上來看權重固定的強化學習算法與蟻群算法除了收斂速度不同外有著相似的結果。這兩種算法雖然在小世界特性這一子目標下有著更優的效果，但是在功能匹配與度匹配特性這一子目標下卻出現了累計子目標回報值隨迭代次數增加反而減小的現象，這說明在訓練過程中出現了犧牲該目標換取全局最優的情況，但本文算法并未出現這一情況，說明本文算法能夠保證每個子目標都隨著循環迭代而增加，可以更好地平衡各個目標的回報值之間的比重，盡管一部分子目標沒有達到最好的效果，但每一個子目標的回報值都隨著迭代次數的增加而增加，結合圖2、3可知，引入權重自適應的多目標優化算法沒有影響總體目標值。

4 結語

本文提出了一種基于自適應多目標A3C強化學習的服務集成方法，該方法利用MDP對服務集成優化問題進行建模，并引入了強化學習的組合優化模型，簡化了組合優化過程。同時基于遺憾值對多目標權重進行動態調整，在保證總體目標回報值最大的情況下不犧牲各個子目標回報值，使每一個子目標回報值都能隨著訓練增大。在數據集Programable Web上與傳統機器學習算法中的蟻群算法和權重固定多目標強化學習算法進行對比分析的結果表明，本文方法相較于其他兩種方法在大規模服務環境下對于服務集成收斂更快、耗時更短，在整體求解質量相近的情況下保證了各子目標的求解質量。然而多目標優化的應用場景一般較為復雜，尤其是子目標之間的關系更加復雜，本文方法將子目標平等對待，有時不能很好地體現子目標之間的優先關系，因此今后我們將針對這類問題做進一步的研究。

[1] FLETCHER K K. A quality?based web api selection for mashup development using affinity propagation［C］// Proceedings of the 2018 International Conference on Services Computing. Cham： Springer， 2018： 153-165.

[2] ALMARIMI N， OUNI A， BOUKTIF S， et al. Web service API recommendation for automated mashup creation using multi? objective evolutionary search［J］. Applied Soft Computing， 2019， 85： No.105830.

[3] 張龍昌，張成文.混合QoS聚類的服務組合［J］.北京郵電大學學報，2011，34（5）：57-62.（ZHANG L C， ZHANG C W. Hybrid QoS?clustering web service composition［J］. Journal of Beijing University of Posts and Telecommunications， 2011， 34（5）： 57-62.）

[4] 朱志良，苑海濤，宋杰，等. Web服務聚類方法的研究和改進［J］. 小型微型計算機系統， 2012， 33（1）：96-101.（ZHU Z L， YUAN H T， SONG J， et al. Study and improvement on web services clustering approach［J］. Journal of Chinese Computer Systems， 2012， 33（1）： 96-101.）

[5] TRIPATHY A K， PATRA M R， KHAN M A， et al. Dynamic web service composition with QoS clustering［C］// Proceedings of the 2014 IEEE International Conference on Web Services. Piscataway： IEEE， 2014： 678-679.

[6] WU L， ZHANG Y， DI Z Y. A service?cluster based approach to service substitution of web service composition［C］// Proceedings of the IEEE 16th International Conference on Computer Supported Cooperative Work in Design. Piscataway： IEEE， 2012： 564-568.

[7] ABDULLAH A， LI X N. An efficient I/O based clustering HTN in Web Service Composition［C］// Proceedings of the 2013 International Conference on Computing， Management and Telecommunications. Piscataway：IEEE， 2013： 252-257.

[8] CAI H H， CUI L Z. Cloud service composition based on multi? granularity clustering［J］. Journal of Algorithms and Computational Technology， 2014， 8（2）： 143-161.

[9] BIANCHINI D， DE ANTONELLIS V， MELCHIORI M. An ontology?based method for classifying and searching?Services［C］// Proceedings of the Forum of First International Conference on Service Oriented Computing， LNCS 2910. Cham： Springer， 2003： 15-18.

[10] WANG X Z， WANG Z J， XU X F. Semi?empirical service composition： a clustering based approach［C］// Proceedings of the 2011 IEEE International Conference on Web Services. Piscataway： IEEE， 2011： 219-226.

[11] QUAN L， WANG Z L， LIU X. A real?time subtask?assistance strategy for adaptive services composition［J］. IEICE Transactions on Information and Systems， 2018， E101.D（5）： 1361-1369.

[12] GAO A Q， YANG D Q， TANG S W， et al. Web service composition using Markov decision processes［C］// Proceedings of the 2005 International Conference on Web?Age Information Management， LNCS 3739. Berlin： Springer， 2005： 308-319.

[13] ZHANG Y Z， CLAVERA I， TSAI B， et al. Asynchronous methods for model?based reinforcement learning［C］// Proceedings of the 3rd Conference on Robot Learning. New York： JMLR.org， 2020： 1338-1347.

[14] RUIZ?MONTIEL M， MANDOW L， PéREZ?DE?LA?CRUZ J L. A temporal difference method for multi?objective reinforcement learning［J］. Neurocomputing， 2017， 263： 15-25.

[15] IANSITI M， LEVIEN R. Strategy as ecology［J］. Harvard Business Review， 2004， 82（3）： 68-78， 126.

[16] QI Q， CAO J. Investigating the evolution of Web API cooperative communities in the mashup ecosystem［C］// Proceedings of the 2020 IEEE International Conference on Web Services. Piscataway： IEEE， 2020： 413-417.

[17] WATTS D J， STROGATZ S H. Collective dynamics of ‘small?world’ networks［J］. Nature， 1998， 393（6684）： 440-442.

[18] NEWMAN M， BARABáSI A L， WATTS D J. The Structure and Dynamics of Networks［M］. Princeton， NJ： Princeton University Press， 2006： 304-308.

[19] BARABáSI A L， ALBERT R. Emergence of scaling in random networks［J］. Science， 1999， 286（5439）： 509-512.

[20] VáZQUEZ A， PASTOR?SATORRAS R， VESPIGNANI A. Internet topology at the router and autonomous system level［EB/OL］. ［2021-12-05］.https：//arxiv.org/pdf/cond?mat/0206084.pdf.

[21] NEWMAN M E J. Scientific collaboration networks. Ⅰ. Network construction and fundamental results［J］. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2001， 64（1）： No.016131.

[22] FOSTER D P， YOUNG H P. Regret testing： a simple payoff? based procedure for learning Nash equilibrium［D］. Baltimore， MD： University of Pennsylvania， 2003： 341-367.

[23] HART S， MAS?COLELL A. A reinforcement procedure leading to correlated equilibrium［M］// Economics Essays： A Festschrift for Werner Hildenbrand. Berlin： Springer， 2001： 181-200.

[24] ORTNER R. Regret bounds for reinforcement learning via Markov chain concentration［J］. Journal of Artificial Intelligence Research， 2020， 67： 115-128.

Service integration method based on adaptive multi?objective reinforcement learning

GUO Xiao， LI Chunshan*， ZHANG Yuyue， CHU Dianhui

（，（），264209，）

The current service resources in Internet of Services （IoS） show a trend of refinement and specialization. Services with single function cannot meet the complex and changeable requirements of users. Service integrating and scheduling methods have become hot spots in the field of service computing. However， most existing service integrating and scheduling methods only consider the satisfaction of user requirements and do not consider the sustainability of the IoS ecosystem. In response to the above problems， a service integration method based on adaptive multi?objective reinforcement learning was proposed. In this method， a multi?objective optimization strategy was introduced into the framework of Asynchronous Advantage Actor?Critic （A3C） algorithm， so as to ensure the healthy development of the IoS ecosystem while satisfying user needs. The integrated weight of the multi?objective value was able to adjusted dynamically according to the regret value， which improved the imbalance of sub?objective values in multi?objective reinforcement learning. The service integration verification was carried out in a real large?scale service environment. Experimental results show that the proposed method is faster than traditional machine learning methods in large?scale service environment， and has a more balanced solution quality of each objective compared with Reinforcement Learning （RL） with fixed weights.

service integration; Reinforcement Learning (RL); Asynchronous Advantage Actor?Critic (A3C) algorithm; multi?objective optimization; adaptive weight

This work is partially supported by National Key Research and Development Program of China （2018YFB1402500）， National Natural Science Foundation of China （61902090， 61832004）， Natural Science Foundation of Shandong Province （ZR2020KF019）.

GUO Xiao， born in 1999， M. S. His research interests include service computing， knowledge engineering.

LI Chunshan， born in 1984， Ph. D.， professor. His research interests include service computing， knowledge engineering.

ZHANG Yuyue， born in 2000. His research interests include knowledge engineering.

CHU Dianhui， born in 1970， Ph. D.， professor. His research interests include service computing， intelligent manufacturing.

1001-9081（2022）11-3500-06

10.11772/j.issn.1001-9081.2021122041

2021?12?06；

2021?12?29；

2022?01?13。

國家重點研發計劃項目（2018YFB1402500）；國家自然科學基金資助項目（61902090， 61832004）；山東省自然科學基金資助項目（ZR2020KF019）。

TP315

A

郭瀟（1999—），男，黑龍江伊春人，碩士，主要研究方向：服務計算、知識工程；李春山（1984—），男，山西呂梁人，副教授，博士，CCF會員，主要研究方向：服務計算、知識工程；張宇躍（2000—），男，江西南昌人，主要研究方向：知識工程；初佃輝（1970—），男，山東濰坊人，教授，博士，CCF高級會員，主要研究方向：服務計算、智慧制造。