張鑫雯
(新疆工程學(xué)院 工程技能實訓(xùn)學(xué)院,烏魯木齊 830023)
隨著Web服務(wù)數(shù)量的急劇增加,網(wǎng)絡(luò)數(shù)據(jù)請求日益增多,且呈現(xiàn)出復(fù)雜化的趨勢,Web服務(wù)組合的優(yōu)化難度越來越大,要求也越來越高。如何從眾多的候選服務(wù)中快速地選擇出滿足用戶要求的可靠服務(wù),在服務(wù)計算機方面帶來了一定的技術(shù)障礙。面向服務(wù)計算(SOC,service-oriented computing)的應(yīng)用主要是用來解決多款軟件在多個平臺中的相互協(xié)作,在不同服務(wù)提供商以及消費者能夠合作的系統(tǒng)上,才可以更好的將SOC的作用發(fā)揮出來。由于單一服務(wù)無法確保符合人們對實際要求,多個服務(wù)開展合作就成了必然需求。服務(wù)組合的目的就是未來能夠進(jìn)一步制定面向服務(wù)架構(gòu)(SOA,service-oriented architecture)。在該過程中,最大的挑戰(zhàn)是,如何從一組功能等效的服務(wù)組合中選擇滿足服務(wù)質(zhì)量(QoS,quality of service)約束的最佳集合。雖然滿足QoS的服務(wù)組合在SOC和SOA領(lǐng)域得到了廣泛研究,但大多數(shù)現(xiàn)有的服務(wù)組合方法都建立于確定性環(huán)境中,當(dāng)面對動態(tài)服務(wù)環(huán)境時,這些方法大多會失效。因為SOC本就具有動態(tài)特征,并且十分復(fù)雜,所以服務(wù)組合方法就要確保能夠更好地滿足服務(wù)環(huán)境將會發(fā)生變化的可能。除此之外,功能等效服務(wù)數(shù)量呈現(xiàn)幾何倍數(shù)遞增,所以這就要求要設(shè)計更加高效的算法,以便能夠快速在候選服務(wù)組合中進(jìn)行選擇的問題。
強化學(xué)習(xí)(RL,reinforcement learning)通過一系列順序決策來達(dá)到特定目標(biāo),在該策略過程中,智能體與環(huán)境進(jìn)行交互,通過反復(fù)試驗來獲得最佳學(xué)習(xí)方案,目前,RL已經(jīng)成為處理自適應(yīng)服務(wù)組合的強大工具,通過與動態(tài)服務(wù)環(huán)境的交互進(jìn)行反復(fù)學(xué)習(xí),RL可以動態(tài)地選擇最佳服務(wù)集,無需對服務(wù)環(huán)境的完整性和充分性進(jìn)行了解。近年來,基于RL的自適應(yīng)服務(wù)組合算法受到越來越多的關(guān)注,如Q學(xué)習(xí)及其相關(guān)的算法。這些算法通常將服務(wù)組合建模為一個隨機過程,在該過程中,智能體通過在動態(tài)環(huán)境中與這些服務(wù)的順序交互和迭代交互,選擇具有最高QoS值的Web服務(wù)集。雖然這些算法已經(jīng)成功應(yīng)用于中小型Web服務(wù)環(huán)境,但當(dāng)部署到大規(guī)模服務(wù)環(huán)境時,其難以獲得良好的狀態(tài)空間和行為空間,影響了學(xué)習(xí)過程的穩(wěn)定性。
針對上述問題,本文將探討采取Web服務(wù)組合方法,該方法能夠真正實現(xiàn)深度學(xué)習(xí)。首先,要通過利用特定的馬爾科夫決策過程(POMDP)進(jìn)行建模。然后,在POMDP基礎(chǔ)上,結(jié)合雙重深度強化學(xué)習(xí)方法對優(yōu)化策略進(jìn)行分層重構(gòu)并求得最優(yōu)解。通過該方法能夠提高服務(wù)組合在可變服務(wù)環(huán)境下的可靠性、準(zhǔn)確度和決策效率。該方法的主要創(chuàng)新點在于:
1)基于POMDP針對大規(guī)模Web服務(wù)組合不同策略建立相應(yīng)的數(shù)學(xué)模型,不僅減少了分析的過程,同時能夠?qū)崿F(xiàn)效率對優(yōu)化。
2)在POMDP基礎(chǔ)上,結(jié)合優(yōu)先級雙重深度強化學(xué)習(xí)方法對優(yōu)化策略進(jìn)行分層重構(gòu)并求得最優(yōu)解,提高了組合服務(wù)對動態(tài)服務(wù)環(huán)境的適應(yīng)能力。
POMDP是一個離散時間的隨機決策過程,用于對不確定決策進(jìn)行建模、描述動態(tài)環(huán)境下服務(wù)組合和自適應(yīng)過程。POMDP定義如下:
定義1:POMDP模型。
組合優(yōu)化模型的基礎(chǔ)是POMDP模型,POMDP模型是一個5元組,即POMDP=(S
,A
,P
,R
,Y
)。其中:S
為一組有限狀態(tài)集合,S
∈S
,S
表示第i
步的狀態(tài);A
為一組有限動作集合,有a
∈A
,a
表示第i
步的動作。P
是狀態(tài)轉(zhuǎn)換概率,表示智能體在經(jīng)過動作a
的作用后,從狀態(tài)s
轉(zhuǎn)移到S
′的概率可以表示為P
(s
′|s
,a
)。R
是獎勵函數(shù),在狀態(tài)S
條件下,采取動作a
,到達(dá)下一狀態(tài)所能獲得的回報值γ
定義為γ
=R
(s
′|s
,a
);γ
為折扣因子,γ
∈[0,1]表示的是區(qū)分未來獎勵與即時獎勵重要性的影響因素。POMDP屬于一種典型的決策策略。π
反映的是一種概率分布,一般為從狀態(tài)到動作所產(chǎn)生的概率。π
是從狀態(tài)到動作的映射,表示為π
:s
→A
。若POMDP是偶發(fā)性的,即狀態(tài)在每個長度為t
的事件之后重置,則每個事件中的狀態(tài)、動作和回報序列將構(gòu)成策略軌跡或策略制定。每次策略制定都會從環(huán)境中獲得回報R
。因此,針對POMDP模型做出優(yōu)化的最終目標(biāo)就是要發(fā)現(xiàn)其中的最優(yōu)策略,該策略幾乎可以涵蓋全部的最大預(yù)期回報值。由于動態(tài)環(huán)境的復(fù)雜性,當(dāng)前缺乏有效的解決方案。所以如果在具有動態(tài)性特點且無法準(zhǔn)確確定的環(huán)境中使用RL實現(xiàn)自適應(yīng)服務(wù)組合能夠起到很好的效果。在組合模型中通過RL,在基于自適應(yīng)方法進(jìn)而確定最優(yōu)秀的服務(wù)策略。
RL通過順序決策來達(dá)到特定目標(biāo),智能體能夠利用上述算法從其他智能體在動態(tài)、復(fù)雜環(huán)境表現(xiàn)進(jìn)行學(xué)習(xí),比如學(xué)習(xí)它們?nèi)绾芜M(jìn)行交互,如何在環(huán)境中實現(xiàn)信息的獲取。通常將這種環(huán)境定義為POMDP。在此條件下,RL能夠利用它與環(huán)境的協(xié)作進(jìn)一步得到最優(yōu)策略。該策略能夠利用四元組(s
,a
,γ
,s
+1)的近似Q函數(shù)得到,其中,s
反映的是在t
時間的環(huán)境狀態(tài)情況,a
反映的是選擇的控制動作,γ
反映的是獲得的即時獎勵,s
+1反映的是后繼的環(huán)境狀態(tài),基于以上四元組能夠通過Q函數(shù)得到相應(yīng)的控制策略。RL算法應(yīng)用效果最為明顯的場景是復(fù)雜控制場景,并且短時間內(nèi)無法確定最佳控制方案。對于一些動態(tài)環(huán)境,通過在自適應(yīng)服務(wù)組合中使用這一算法將會發(fā)揮更好的效果。所以,如果模型中涉及到RL算法就可以確保模型的學(xué)習(xí)效果,進(jìn)而得到相對優(yōu)秀從而得到一個最佳的策略。利用POMDP具體如下。定義2:基于POMDP的Web服務(wù)組合(POMDP-WSC)。
這個回報值可用如下方法來計算:
Q
(s
,a
)=Q
(s
,a
)+a
[r
+γ
max·Q
(s
′-a
′)-Q
(s
,a
)](1)
式中,s
表示狀態(tài)空間(即抽象服務(wù)),為了滿足用戶請求智能體i
遍歷的所有可能工作流;α
代表可用Web服務(wù)的動作向量;r
表示選擇特定服務(wù)而獲得的回報值;α
是控制收斂性的學(xué)習(xí)速率;γ
是反映學(xué)習(xí)策略的折扣因子。當(dāng)智能i
體選擇Web服務(wù)ws
時,它會收到回報,該回報值是ws
的 QoS屬性的累計值。能夠利用下面計算公式進(jìn)行計算:(2)
ε
-貪婪策略,確保任意一個智能體在過去體驗過的Web服務(wù)與當(dāng)前隨機選擇的新Web服務(wù)做出對比。如果智能體i
,確定了狀態(tài)以及一組能夠使用的Web服務(wù)A
(s
),那么智能體i
選擇下一個Web服務(wù)α
的概率可以表示為如下公式:(3)
其中:ε
反映的是一個Web服務(wù)的概率。所有的智能體i
按照它的策略以(1-ε
)的概率確定最優(yōu)的Web服務(wù),不然將通過ε
概率任意從中選擇一個Web服務(wù)。深度學(xué)習(xí)是機器學(xué)習(xí)算法的一個領(lǐng)域,旨在學(xué)習(xí)多層次的表示和抽象,以幫助理解圖像、聲音和文本等復(fù)雜數(shù)據(jù)。深度學(xué)習(xí)采用多層非線性處理單元進(jìn)行特征提取和轉(zhuǎn)換,當(dāng)前層使用前一層的輸出作為輸入。在學(xué)習(xí)過程中,不同的抽象層次對應(yīng)不同的表征層次,這些層次的形成最終變成了層次結(jié)構(gòu),即,深度學(xué)習(xí)的結(jié)構(gòu)。
π
(s
,a
)和狀態(tài)動作映射空間Q
(s
,a
)。對這些深度神經(jīng)網(wǎng)絡(luò)的參數(shù)使用梯度下降法進(jìn)行訓(xùn)練,以便使其損失最小化。學(xué)習(xí)過程具體如下:首先,智能體從環(huán)境中獲得一個觀察結(jié)果,并將其作為輸入傳遞給深度神經(jīng)網(wǎng)絡(luò)。然后,深度神經(jīng)網(wǎng)絡(luò)從高維輸入或觀察中學(xué)習(xí)抽象表示,接著評估動作空間并根據(jù)當(dāng)前觀察結(jié)果映射合適的動作。最后,環(huán)境對這個動作給出反應(yīng),并過渡到下一個環(huán)節(jié)。針對大規(guī)模環(huán)境下的服務(wù)組合問題,提出了一種基于DRL的服務(wù)組合方法。為了在大規(guī)模服務(wù)環(huán)境中實現(xiàn)自適應(yīng)服務(wù)組合,本文提出了一種將DRL應(yīng)用到服務(wù)組合的方法,采用DQN作為基準(zhǔn),使用雙Q學(xué)習(xí)對提出的方法進(jìn)行強化,以解決Q學(xué)習(xí)過程中出現(xiàn)的高估偏差問題。通過將引導(dǎo)操作的選擇步驟和評價步驟進(jìn)行分離,消除Q學(xué)習(xí)的高估偏差;此外,還實施了優(yōu)先體驗重播方案,通過更頻繁地重播需要學(xué)習(xí)的數(shù)據(jù)來提高轉(zhuǎn)換效率。每個強化措施都大大提升了學(xué)習(xí)方法的性能,采用的強化措施也解決了幾個具有挑戰(zhàn)性的問題,所提方法如下。
3.2.1 DQN
為了估算給定狀態(tài)S
的動作值,將其作為神經(jīng)網(wǎng)絡(luò)的輸入(以原始像素幀的堆棧形式),深度神經(jīng)網(wǎng)絡(luò)和強化學(xué)習(xí)通過使用卷積神經(jīng)網(wǎng)絡(luò)在DQN中成功組合。在每個步驟中,根據(jù)當(dāng)前狀態(tài),智能體會根據(jù)動作值選擇一個動作,并根據(jù)動作值應(yīng)用貪婪策略添加一個轉(zhuǎn)換值到重播存儲緩沖區(qū)(S
,A
,R
+1,γ
+1,S
+1)。此重播存儲緩沖區(qū)保存最后一百萬次轉(zhuǎn)換值。然后,使用隨機梯度下降法來優(yōu)化神經(jīng)網(wǎng)絡(luò)的參數(shù),使其損失最小化,如下所示:(4)
3.2.2 雙Q學(xué)習(xí)
如式(1)所示,由于Q學(xué)習(xí)會受到高估偏差的影響,這種高估偏差反過來又會導(dǎo)致差異,影響學(xué)習(xí)過程的穩(wěn)定性。為了解決這種高估偏差,采用了一種分離方案,該方案將動作的選擇與對動作的評估分開。這種分離方案可以有效地與DQN結(jié)合,其損失表示如下:
(5)
如此,可有效減少DQN中存在的不利高估偏差,有助于提高學(xué)習(xí)過程的穩(wěn)定性。
3.2.3 優(yōu)先重播
優(yōu)先重播的基本思想是先保存某個智能體的經(jīng)驗,然后統(tǒng)一提取這些已經(jīng)保存的經(jīng)驗,從而有效地訓(xùn)練神經(jīng)網(wǎng)絡(luò)。通過不斷保存和提取經(jīng)驗,智能體能夠在具體任務(wù)中更加有效地學(xué)習(xí)。然而在實踐中,智能體需要頻繁地從具有更高優(yōu)先級的經(jīng)驗庫中取樣,即從中學(xué)習(xí)更多的經(jīng)驗。為此,在所提方法中設(shè)計了一個經(jīng)驗優(yōu)先重播方案,該方案能夠以概率P
進(jìn)行轉(zhuǎn)換采樣,P
與最后遇到的絕對時間差有關(guān),表示如下:(6)
式中,ω
是確定分布形狀的超參數(shù)。優(yōu)先重播方案以最大優(yōu)先級將新轉(zhuǎn)換的經(jīng)驗插入到經(jīng)驗庫中。為了從不同的角度評價所提方法,進(jìn)行了兩個實驗。第一個實驗研究了環(huán)境規(guī)模對該方法學(xué)習(xí)高質(zhì)量服務(wù)組合策略的影響。第二個實驗評估了該方法在動態(tài)服務(wù)環(huán)境中的性能以及動態(tài)變化對學(xué)習(xí)過程的影響。
所提方法在連續(xù)迭代的單集中運行,直到達(dá)到收斂點。當(dāng)智能體在連續(xù)數(shù)個事件中獲得相同的累積回報值時,它就能夠進(jìn)一步得出相應(yīng)的最佳策略。然后將累積回報值再作對比,同時利用閾值對差異進(jìn)行預(yù)測。閾值參數(shù)一般設(shè)定成0.001,連續(xù)次數(shù)一般設(shè)定成1 000。
在實驗中,利用Web 服務(wù)質(zhì)量的數(shù)據(jù)集合需要用到QoS的3個參數(shù),一是可用性,二是可靠性,三是響應(yīng)時間。再通過QoS向量就能夠計算出每個工作流的平均累積回報,具體如表1所示。
表1 聚合參數(shù)設(shè)置
為了驗證所提學(xué)習(xí)方法的可行性和效率,將其與文獻(xiàn)[4]、文獻(xiàn)[7]、文獻(xiàn)[9]提出方法進(jìn)行比較。實驗中的參數(shù)設(shè)置是根據(jù)文獻(xiàn)[13]中的模擬實驗建立,如表2所示。
表2 對比實驗參數(shù)設(shè)置
4.2.1 大型環(huán)境中的Web服務(wù)組合能力分析
4.2.1.1 學(xué)習(xí)質(zhì)量
實驗開展的作用是對理論的驗證與評估,如果解決方案最終能夠獲得最好的一個服務(wù)選擇策略,那么通過智能體得到對平均累積回報就可以用于量化評價該方法的學(xué)習(xí)能力。不同服務(wù)數(shù)量下,所提方法、文獻(xiàn)[4]、文獻(xiàn)[7]和文獻(xiàn)[9]提出的方法所得回報數(shù)的對比結(jié)果如圖1所示。
圖1 回報數(shù)實驗結(jié)果對比圖
從圖1中可以看出,當(dāng)服務(wù)數(shù)量為100時,所提方法所得回報數(shù)約為86,文獻(xiàn)[4]、文獻(xiàn)[7]、文獻(xiàn)[9]所得回報數(shù)分別約為54、67、84,所提方法所得回報數(shù)最高。當(dāng)服務(wù)數(shù)量為1 000時,所提方法所得回報數(shù)約為1 393,其他對比方法所得回報數(shù)分別為542、743、1 023。由此可見,所提方法的總回報數(shù)高于其他幾種對比方法,具有更好的服務(wù)組合能力。隨著服務(wù)數(shù)量的增加,4種方法所得回報數(shù)都會增加,但所提方法所得回報數(shù)增加速度最快。該結(jié)果表明,所提方法更適合大規(guī)模Web服務(wù)組合的應(yīng)用。
4.2.1.2 可伸縮性
為了便于比較,將所提方法得到的可伸縮性作為基準(zhǔn)量,將其他幾種方法得到的可伸縮性與所提方法的比值(即相對可伸縮性)進(jìn)行對比,結(jié)果如圖2所示。
圖2 可伸縮性實驗對比結(jié)果圖
從圖2中看出,當(dāng)服務(wù)數(shù)量為100時,文獻(xiàn)[4]、文獻(xiàn)[7]、文獻(xiàn)[9]得到的可伸縮性分別約為0.36、0.84、0.86,可伸縮性均小于1.0,可見所提方法的可伸縮性較高,更加有能力面對可變服務(wù)環(huán)境。當(dāng)服務(wù)數(shù)量為2 000時,文獻(xiàn)[9]提出的方法得到的可伸縮性約為1.02,大于1.0,其可伸縮性優(yōu)于所提方法。但在大部分實驗環(huán)境下,所提方法的可伸縮性優(yōu)于其他幾種對比方法,在處理可變服務(wù)環(huán)境時的綜合表現(xiàn)最為理想。
4.2.2 動態(tài)服務(wù)環(huán)境中的Web服務(wù)組合能力分析
4.2.2.1 摘要服務(wù)對象的總回報
實驗?zāi)康氖窃u估所提學(xué)習(xí)方法在動態(tài)服務(wù)環(huán)境中找到最佳服務(wù)選擇策略的能力,通過智能體在動態(tài)服務(wù)環(huán)境中收斂到最佳服務(wù)選擇策略時獲得的累積回報進(jìn)行衡量。在不同的摘要服務(wù)數(shù)量情況下,4種方法的累積回報結(jié)果如圖3所示。
圖3 摘要服務(wù)數(shù)量與總回報的關(guān)系
從圖3中可以看出,當(dāng)摘要服務(wù)量為500時,所提方法得到的總回報為632,文獻(xiàn)[4]、文獻(xiàn)[7]、文獻(xiàn)[9]中方法所得到的總回報分別約為254、302、304,因此,所提方法所得到的總回報最高。同樣,當(dāng)摘要服務(wù)量為1 000時,所提方法所得的總回報也是最高的。因此,相比于其他幾種對比方法,所提方法在面對動態(tài)服務(wù)對象時具有明顯優(yōu)勢。
4.2.2.2 可靠性
在不同服務(wù)數(shù)量下,所提方法和文獻(xiàn)[4]、文獻(xiàn)[7]和文獻(xiàn)[9]的可靠性結(jié)果如圖4所示。將所提方法的可靠性作為基準(zhǔn)比較量,其他方法的可靠性與所提方法的可靠性的比例為相對可靠性。
從圖4中可以看出,當(dāng)服務(wù)量為100時,所提方法的可靠性為1.0,其他對比方法分別是0.83、0.9、0.95。因此,所提方法得到的相對可靠性最高,求解質(zhì)量最好。當(dāng)服務(wù)數(shù)量為2 000時,所提方法得到的相對可靠性仍然最高,求解質(zhì)量最好,文獻(xiàn)[9]所提方法次之,文獻(xiàn)[7]所提方法略差,文獻(xiàn)[4]所提方法在可靠性方面表現(xiàn)最差。
圖4 可靠性的實驗結(jié)果
4.2.2.3 動態(tài)環(huán)境適應(yīng)能力
在不同服務(wù)數(shù)量下,所提方法和文獻(xiàn)[4]、文獻(xiàn)[7]、文獻(xiàn)[9]的動態(tài)環(huán)境適應(yīng)能力如圖5所示。為了便于分析,將所提方法的動態(tài)環(huán)境適應(yīng)能力作為基準(zhǔn)比較量,將其他方法與所提方法之間的可靠性比值(相對動態(tài)環(huán)境適應(yīng)能力)進(jìn)行對比。
圖5 動態(tài)環(huán)境適應(yīng)能力的實驗結(jié)果
從圖5中可以看出,當(dāng)服務(wù)數(shù)量為100時,所提方法得到的動態(tài)環(huán)境適應(yīng)能力最高,對環(huán)境的適應(yīng)能力最強,文獻(xiàn)[9]與文獻(xiàn)[7]所提方法次之,文獻(xiàn)[4]所提方法的動態(tài)環(huán)境適應(yīng)能力最差,且差距較大。當(dāng)服務(wù)量為2 000時,所提方法得到的相對動態(tài)環(huán)境適應(yīng)能力為1.0,文獻(xiàn)[4]、文獻(xiàn)[7]、文獻(xiàn)[9]提出的方法所得相對動態(tài)環(huán)境適應(yīng)能力分別為0.83、0.90和0.95。此外,當(dāng)服務(wù)數(shù)量增加時,相對動態(tài)適應(yīng)能力都會隨之減弱,這說明服務(wù)數(shù)量越多,對動態(tài)環(huán)境的適應(yīng)能力越弱。然而,相比文獻(xiàn)[4]、文獻(xiàn)[7]和文獻(xiàn)[9]提出的方法,所提方法的相對動態(tài)適應(yīng)能力較強,在動態(tài)環(huán)境適應(yīng)方面表現(xiàn)最好。
針對大規(guī)模Web服務(wù)組合在動態(tài)環(huán)境下難以實現(xiàn)高可靠性、高動態(tài)適應(yīng)能力的問題,探討了一種采取Web服務(wù)組合的方法,該方法充分發(fā)揮了深度學(xué)習(xí)的優(yōu)勢以及POMDP模型的作用,通過模型能夠獲得更加的策略,不僅簡化了組合步驟,顯著提高了大規(guī)模Web組合服務(wù)的計算效率。該方法利用優(yōu)先級雙重深度強化學(xué)習(xí)對優(yōu)化策略進(jìn)行分層重構(gòu)并求取最優(yōu)解,有效提升了組合服務(wù)在動態(tài)服務(wù)環(huán)境下的適應(yīng)能力。實驗結(jié)果表明,相比其他幾種現(xiàn)有方法,所提方法在Web服務(wù)組合應(yīng)用中具有更高的可靠性和更高的效率。
未來,將會引入“協(xié)同效應(yīng)值”,將服務(wù)質(zhì)量作為信息素,以求解并行服務(wù)的協(xié)同效應(yīng)值,從而獲得綜合評價值最高的服務(wù)組合方法。