利用記憶單元改進DQN的Web服務組合優化方法

楊 波 胡國兵

1(南京信息職業技術學院信息服務學院 江蘇 南京 210023) 2(金陵科技學院電子信息工程學院 江蘇 南京 211169)

0 引 言

隨著網絡技術的發展，面向復雜環境的服務組合在現實生活中的應用越來越多，而面向復雜環境的Web服務組合的進一步應用會面臨難以優化的問題。面向服務計算(Service-Oriented Computing,SOC)的基本目標是實現在各種平臺上運行的不同軟件和數據應用程序之間的互操作性[1]。因此只有當存在眾多服務提供商和服務消費者彼此協作時，才能發揮SOC的全部潛力[2]。由于面向服務的環境中固有的動態性和復雜性，良好的服務組合解決方案需要適應這些動態服務環境的變化和波動。此外，功能等同服務數量的爆炸性增長迫切需要能夠處理此類任務的有效服務組合算法[3-4]。由于一個服務不能滿足所有用戶要求，因此需要將組件服務轉換成組合服務。在這方面，服務組合成為實現面向服務的體系結構(System of Archtecture，SOA)的最有效技術。

為了對面向復雜環境的Web服務組合進行優化，學者進行了大量的研究，在復雜環境下，從大量的滿足功能需求但是非功能需求的Web服務中，選擇出滿足用戶需求的組合服務所采取的服務選擇策略可以有多種，研究文獻可主要分為三種：群智能算法、人工智能(Artificial Intelligence，AI)方法和其他混合方法。群智能算法如文獻[5]提出的多目標服務組合優化推薦方法(Multi-Objective Service Combination Optimization Recommendation Method，MO-SCORM)，具有較好的可適應性和自組織性，通過將細粒度的Web服務粗粒化實現了面向個性化客戶的體系結構，其協作性和健壯性較好，但效率較低；文獻[6]從功能等同的具體服務集合中選擇了滿足消費者強加的服務質量(Quality of Service，QoS)，對最佳服務集合進行約束，提高了服務組合的服務質量，但在服務效率方面還需進一步提高。在大數據背景下為改善算法效率，智能算法得到了廣泛應用：文獻[7]提出了一種結合順序決策過程的強化學習方法(Sequential Decision-Making Process-Reinforce Learning，SDMP-RL)并將其應用在Web服務組合的優化問題中，使代理與環境交互，通過反復實驗提高了Web組合服務的學習最優解，但該方法在面對可擴展性的服務環境時表現較差；文獻[8]采用深度Q學習(Deep Q-Learning，DQL)解決了Web服務組合效率低的問題，但是沒能兼顧Web組合服務對復雜環境的適用性和可擴展性。現有的Web服務組合方法在面對復雜的服務環境時，難以同時在服務環境的適應性、可擴展性和動態性這幾個指標上獲得良好的綜合性能。針對面向高可擴展性、復雜性和異構性服務環境的Web服務組合難以進行優化的問題，本文提出一種利用記憶單元改進DQN的Web服務組合優化方法。其創新點主要體現為以下兩點：

(1) 引入LSTM-DQN方法進行優化，提升了DQN算法的全局尋優能力；

(2) 利用強化學習的組合優化模型簡化組合優化過程，并將LSTM-DQN方法應用于Web服務組合優化問題，提升了Web服務組合的處理效率。

1 基于Markov的組合優化模型

組合優化模型采用馬爾可夫決策過程MDP作為一般方案，以描述動態環境中的服務組合和適應過程。MDP是離散時間隨機控制過程，用于對不確定域中的順序決策進行建模。MDP的關鍵組成部分正式定義如下[9]：

定義1Markov 決策過程(MDP)。一個MDP可以定義為一個五元組MDP=，其中：S是一組有限狀態；A(s)是一個有限的動作集合，取決于當前狀態s∈S;P是一個概率值，也就是當動作a∈A被執行時，發生一個從當前狀態s到結果狀態s′的一個狀態轉移，其轉移概率分布為P(s′|s,a)；R是獎勵函數。類似地，當執行操作a時，從狀態s轉移到s′，將收到一個實際值的獎勵r，其預期值為r=E(R(s′|s,a))；γ∈[0,1]是區分未來獎勵和即時獎勵重要性的折扣因素。

MDP的解決方案是一個決策策略，通常決策策略π是從狀態到操作的概率分布的映射，定義為π:S→A如果MDP是偶發性的，即狀態在長度t的每一場景后重置，則一個場景中的狀態、行動和獎勵序列構成策略的軌跡或推出[10]。策略的每個推出都會從環境中累積一個獎勵，從而返回R。解決方案中算法的目標是找到一個最佳策略，該策略累積了所有狀態的最大預期回報。

2 基于強化學習的組合優化模型

RL的目的是設計算法，通過這些算法，代理可以學習在某些環境中的自主操作，從他們與該環境的交互或從環境中收集的觀測值中學習。此環境通常作為MDP制定。與傳統的動態編程技術不同，強化學習算法不需要有關MDP的知識，它們針對的是精確方法變得不可行的大型MMDP。在此背景下，RL旨在根據它們與環境的交互來確定最佳控制策略[11]。此策略可以通過基于一組四元組(st,at,rt,st+1)近似所謂的Q函數來實現。其中：st表示t時刻的環境狀態；at表示所執行的控制操作；rt表示所獲得的瞬時獎勵；st+1表示環境的后續狀態，并通過Q函數決定控制策略。

最適合RL的問題類型是復雜的控制問題，其中似乎沒有明顯或易于編程的解決方案。因此，在開放和動態環境中使用RL進行自適應服務組合具有明顯的優勢。通過在組合模型中使用RL，它可以以自適應的方法學習最佳服務選擇策略[11]。基于MDP的動態服務組合中使用的關鍵概念定義如下：

獎勵值r可以使用操作值函數計算：

Qi(s,a)←Qi(s,a)+α[r+γmaxa′Qi(s′,a′)-

Qi(s,a)]

(1)

式中：s表示狀態空間(即抽象服務)，表示代理i遍歷所有可能的工作流時全部狀態的集合；α是學習率，它控制收斂；當代理i選擇一個Web服務ws時，代理i收到一個獎勵，這是一個聚合值的QoS的ws屬性。此獎勵值可以根據下式計算：

(2)

在此模型中，采用ε-貪婪策略，使學習代理能夠在選擇過去嘗試過的Web服務(即利用)和隨機選擇可能提供更好的結果的新Web服務之間進行權衡(即探索)。對于代理i，給定狀態和一組可用的Web服務Ai(s)，代理i選擇下一個 Web 服務j的概率為：

(3)

式中：ε是單個 Web 服務的概率分布,[·]表示對中括號內的內容進行記分。代理i根據ε-貪婪策略的概率(1-ε)選擇最佳的Web服務，否則以概率ε選擇一個統一隨機的Web服務[12]。

3 LSTM-DQN的Web服務組合優化方法

3.1 深度Q神經網絡算法

深度Q神經網絡(Deep Q-Network，DQN)是基于深度學習和強化學習思想而提出的無監督學習方法。在高維度狀態或動作空間中，深度強化學習存在難以估計每個大型狀態和操作空間所對應的Q值問題。為了解決該問題，引入了深度Q神經網絡，使深度強化學習代理的各個組成部分利用梯度下降對參數進行訓練，以盡量減少一些不必要的損失函數[13]。DQN算法原理如圖1所示。

圖1 DQN算法原理

在深度學習計算Q值的過程中，DQN 算法通過權重為θ的神經網絡近似器來估計Q值，該神經網絡的輸入為狀態，經過卷積、池化、全連接等操作，輸出該狀態下每個動作的Q的估計值。智能體的目標是找到一種未來反饋值最大的動作選擇方式，利用該動作選擇方式與環境進行交互。因此定義最優動作選擇函數為Q(s,a)，其算式為[14]：

(4)

式中：s為狀態；a為該狀態下執行的動作；π為動作和狀態映射；st為t時間步時的狀態；at為st狀態下執行的動作；Rt為狀態時s執行動作a得到的反饋值；T為總時間步；t′為求和過程變量；rt為第t個時間步的反饋值[15]。

綜上所述，根據深度學習和強化學習計算的Q值，通過對損失函數Le(θe)使用梯度下降法更新權重θ，來優化 Q神經網絡：

Le(θe)=Es,a～p(·)[(ye-Q(s,a;θe))2]ye=Es′[r+γmaxa′Qe(s′,a′;θe)|s,a]

(5)

式中：Q(s,a;θe)為Q(s,a)的估計值；e為迭代次數；s為當前狀態；a為當前動作；s′為下一個狀態；a′為下一個動作；p(s,a)為狀態s和動作a的概率分布。

3.2 LSTM改進的深度Q神經網絡算法

為了在大型服務環境中啟用自適應服務組合，提出一種基于改進DQN的模型，該模型包括生成器φR和動作記分器φA，模型的整體架構如圖2所示。

圖2 改進DQN模型框架

為了更好地描述模型，采用長-短期記憶網絡(Long Short-Term Memory Network，LSTM)表示生成器。LSTM是遞歸神經網絡，能夠連接和識別輸入向量之間的長程模式，在一定程度上可捕捉潛在信息。所提模型中，LSTM網絡將輸入向量嵌入潛在因子wk，并在每個步驟生成輸出向量xk。為了得到最終的狀態vs，添加了一個平均池層，用于計算輸出向量xk上的元素平均值[16]：

(6)

生成器的輸出向量作為動作記分器的輸入，即vs=φR(s),輸出是所有動作的分數。同時預測所有動作的分數，這比分別對每個狀態動作進行分數計算更有效。通過生成器和動作記分器，可得到Q函數的近似值Q(s,a)≈φA(φR(s))[a]。

由于計算上的限制，所提LSTM-DQN方法將命令視為由一個操作和一個參數對象組成[17]。考慮到所有可能的動作和對象，使用同一個網絡對每個狀態進行預測。該法使用隨機梯度下降和RMSprop學習表示生成器的參數r和動作記分器的參數a，完整的訓練過程如算法1所示。在每次迭代e中，更新參數以減少當前狀態Q(st,at;θe)(θe=[θR;θA]e)的預測值與給定獎勵rt的預期q值和下一狀態maxaQ(st+1,a;θe-1)的值之間的差異[18]。

▽θeQ(s,a;θe)]

(7)

式中：▽θe表示對θe求導。

算法1LSTM-DQN訓練程序

1. 輸入經驗記憶D

2. 初始化表示生成器φR和動作記分器φA的隨機的初始化參數

3. forj=1; 最大迭代次數Mdo

4. 初始化游戲并獲得開始狀態描述s1

5. fort=1;Tdo

6. 用φR轉換st以表示vst

7. if 隨機數random()<迭代次數ethen

8. 選擇隨機一個動作at

9. else

10. 對所有動作，通過φA(vst)計算Q(st;a)

11. 選擇at=argmaxQ(st;a)

12. 執行動作at并獲得獎勵rt和新狀態st+1

13. ifrt>0，設置優先權pt=1,elsept=0

14. 存儲轉移量(st;at;rt;st+1;pt)到D中

15. 從D中隨機采樣小數量的轉換(sj;aj;rj;sj+1;pj)

16. 設置

17. 對損失執行梯度下降步驟L(θ)=yi-Q(sj,aj;θ)2

18. 輸出Web服務組合優化方案

4 實 驗

4.1 實驗設置

本文提出的方法在連續迭代循環中運行，直到達到收斂點。一旦學習代理收到了若干個連續時間的累積獎勵的相同值，代理則將收斂到最優策略。這些累積獎勵按節進行比較，差異根據閾值進行預測。所有模擬實驗都在六核心Intel Xeon 3.2 GHz iMac Pro上進行，具有32 GB的RAM和8 MB的GPU；采用Windows系統運行MATLAB仿真軟件，利用MATLAB語言進行程序編寫，閾值設置為0.001，迭代次數設置為1 000。

在以下實驗中，基于QWS數據集考慮了三個QoS屬性，即可用性、可靠性和響應時間。通過使用表1聚合其成員Web服務的QoS向量，計算每個工作流的平均累積獎勵r。

表1 聚合參數

在學習質量、選擇策略和消耗時間性能方面，將本文方法與文獻[5]提出的MO-SCORM方法、文獻[7]提出的SDMP-RL方法和文獻[8]提出的DQL方法進行比較。學習參數是根據文獻[13]中的第一次經驗模擬建立的，具體設置如表2所示。

表2 參數設置

4.2 學習質量

本節主要驗證所提方法在大型環境中尋找高質量服務組合的能力。當解決方案收斂到最佳服務選擇策略時，使用學習代理獲得的平均累積獎勵來衡量方法能力，此獎勵值表示最佳工作流的聚合QoS。

測試分成兩次。測試1中，測試環境抽象任務數量固定為150個和250個，其可用的具體Web服務的數量范圍為600到900。在此環境下，運行四種方法并將結果統計于圖3中。

圖3 不同抽象服務任務數量下的積累獎勵對比

可以看出，雖然環境規模較大，但本文提出的LSTM-DQN方法的運行結果優于文獻[5]、文獻[7]和文獻[8]方法，LSTM-DQN方法顯然在整個學習過程中獲得更高的累積回報，并帶來更高質量的解決方案。

測試2中，將具體服務的數量固定為700和900，并將抽象任務服務的數量范圍設置為100到400，實驗結果如圖4所示。

圖4 不同具體服務任務數量下的積累獎勵對比

無論每個工作流的抽象任務的數量大小為多少，LSTM-DQN服務組合方法的結果均優于文獻[5]、文獻[7]及文獻[8]方法。隨著抽象任務服務數量的增加，方法性能差距會越來越大，由此驗證了LSTM-DQN方法可以找到更好的服務組合、在大型環境中的可擴展性及其查找高質量服務的能力。

4.3 最佳服務選擇策略

本節驗證所提出的學習方法在動態服務環境中找到最佳服務選擇策略的能力，該能力由獲得的累積獎勵來衡量的。服務環境中的動態更改取決于參與者具體服務的QoS值變化。QoS值動態變化會影響學習代理收到的獎勵值r。本實驗中用兩個因素來衡量服務環境的動態變化，即更改的規模和變化的頻率。

為驗證變化規模這一因素的影響，考慮一個每個任務包含200個抽象任務服務和700個具體服務的工作流，改變參與者具體服務的QoS值，變化百分比分別為1%、5%和10%。實驗結果如圖5所示。其中：x軸表示參與者具體服務的QoS值的更改百分比；y軸表示學習代理在收斂到最佳值之前所獲得的累積獎勵。

圖5 變化尺度對比1

可以看出，LSTM-DQN方法在服務環境中匯聚到最佳策略之前，分別累積了162和111個單位的獎勵，而服務環境在其參與者的具體QoS值中經歷1%和5%的周期性變化服務。與DQN和RL方法在同一環境下分別獲得的85和77個單位的獎勵，以及64和56個單位的獎勵相比，在復雜動態的環境中學習最佳服務選擇策略時，LSTM-DQN方法的效率不高。

為驗證更改頻率這一因素，本文考慮一個每個任務包含200個抽象任務服務和700個具體服務的工作流，參與者具體服務的5%的QoS值每1 000、500和250段落按順序定期變化。結果如圖6所示。其中：x軸表示段落數；y軸表示學習代理在收斂到最佳值之前所獲得的累積獎勵。

圖6 變換頻率對比

可以看出，LSTM-DQN方法在匯合到服務環境中的最佳策略，每個1 000段和500段的參與者服務的QoS值分別經歷5%的周期性更改。這與DQN方法和RL方法在相同服務環境中分別獲得的80和67個獎勵單位以及57和53個單位的獎勵相比更好。

4.4 服務組合成功率

本文方法在大規模服務數量下效果明顯，為了驗證這一點，采用不同的任務數對四種方法進行對比實驗，實驗結果如圖7所示。

圖7 變化尺度對比2

可以看出，使用LSTM-DQN方法能夠得到相對高的服務組合成功率。并且服務組合時，組合成功率與任務數有關系，隨著任務數的增加，組合成功率會降低，但使用LSTM-DQN方法組合成功率變化緩慢，說明候選服務數越多，系統的性能越穩定，但系統的代價也會增大，這與實際是相符合的。

4.5 消耗時間

對20個服務組合要求進行20次取樣，將LSTM-DQN方法與文獻[5]、文獻[7]、文獻[8]方法進行實驗對比，服務組合消耗的時間如圖8所示。

圖8 服務組合消耗的時間對比

可以看出，隨著參與組合服務數目的增加，在網絡環境經常變動的情形下，服務組合所耗費時間明顯都在增加，但是LSTM-DQN方法與其他兩種方法相比，其消耗的時間相對較少，服務組合的數目越多，其優勢越明顯。

5 結 語

本文提出一種利用記憶單元和改進DQN的Web服務組合優化方法，該法利用Markov對Web服務組合優化問題進行建模，并引入了強化學習的組合優化模型，簡化了組合優化過程。并且基于記憶單元對深 度Q網絡算法進行優化，提出LSTM-DQN方法，極大地提升了DQN算法的全局尋優能力。為驗證所提方法的性能，將其基于QWS數據集與DQN和RL方法進行對比分析，結果表明，本文方法相對于其他兩種方法在大規模服務環境下對Web服務組合優化所消耗時間更短，服務組合成功率更高，具有更強的處理能力和處理效率。

本文方法只考慮一個代理的Web服務數量，在未來的工作中，可以考慮將LSTM-DQN方法擴展到多代理設置，并針對學習代理數量與服務環境規模之間的權衡問題作進一步的研究。