基于深度強(qiáng)化學(xué)習(xí)的QoS感知Web服務(wù)組合

高文斌，王 睿，王田豐，祖家琛，胡谷雨

(陸軍工程大學(xué) 指揮控制工程學(xué)院，江蘇 南京 210007)

0 引 言

面向服務(wù)的計(jì)算(service-oriented computing，SOC)和面向服務(wù)的架構(gòu)(service-oriented architecture，SOA)的出現(xiàn)，為如何實(shí)現(xiàn)軟件模塊的解耦提供了新的思路[1]。Web服務(wù)具有獨(dú)立運(yùn)行、可互操作的特性[2]。步入云計(jì)算時(shí)代以后，相當(dāng)一部分企業(yè)以服務(wù)的形式在互聯(lián)網(wǎng)上發(fā)布產(chǎn)品供用戶使用，致使Web服務(wù)的數(shù)量迅速增長(zhǎng)。截至2020年12月，僅ProgrammableWeb網(wǎng)站上所提供的可用Web服務(wù)數(shù)量已經(jīng)達(dá)到了22 200個(gè)。這些Web服務(wù)根據(jù)功能不同進(jìn)行分類，如：支付類、查詢類、天氣類等。在功能相似的情況下，服務(wù)質(zhì)量(quality of service，QoS)成為衡量Web服務(wù)優(yōu)劣的重要指標(biāo)。用于衡量服務(wù)的QoS的指標(biāo)主要包括：響應(yīng)時(shí)間、可用性、可靠性、吞吐量、價(jià)格以及調(diào)用成功率等[3]。Web服務(wù)組合不需要完全重新開(kāi)發(fā)滿足用戶需求的新軟件，僅根據(jù)用戶的功能性需求，完成符合一定邏輯規(guī)律的現(xiàn)有服務(wù)組合。這種方法在有效降低開(kāi)發(fā)成本的同時(shí)，縮短開(kāi)發(fā)周期，進(jìn)而滿足用戶時(shí)效性要求。但是，如何在規(guī)模日趨龐大的服務(wù)組合場(chǎng)景下，提高組合服務(wù)的QoS，是服務(wù)組合問(wèn)題的研究熱點(diǎn)。

學(xué)術(shù)界對(duì)QoS感知的服務(wù)組合問(wèn)題已經(jīng)做了很多深入研究[4-10]，求解方法主要以進(jìn)化計(jì)算算法為主，包括改進(jìn)的遺傳算法及粒子群算法等。

郭星等人[11]提出了一種基于粒子群算法的動(dòng)態(tài)服務(wù)組合方法FWPSO。通過(guò)增加種群多樣性來(lái)提高搜索性能，并在此基礎(chǔ)上進(jìn)行了防止早熟收斂處理，實(shí)驗(yàn)證明該方法相比于傳統(tǒng)粒子群算法在搜索效率上有顯著提升；張以文等人[4]提出了一種融合Skyline技術(shù)的遺傳粒子群算法。通過(guò)Skyline技術(shù)降低問(wèn)題的求解空間。應(yīng)用種群相似性和遺傳操作避免早熟收斂，實(shí)驗(yàn)表明，該算法的收斂速度快于傳統(tǒng)粒子群算法；魯城華等[5]提出了一種基于遺傳算法的服務(wù)組合方法MADMAGA，通過(guò)局部搜索策略提高算法收斂速度，實(shí)驗(yàn)表明，該算法在應(yīng)對(duì)小規(guī)模服務(wù)組合場(chǎng)景時(shí)搜索效率高，模型收斂速度快；Sun等人[6]提出了基于時(shí)間序列預(yù)測(cè)和遺傳算法結(jié)合的模型ARIMA+GA解決服務(wù)組合問(wèn)題，通過(guò)對(duì)服務(wù)QoS記錄做預(yù)測(cè)來(lái)提升服務(wù)QoS的準(zhǔn)確性，并通過(guò)遺傳算法來(lái)求解模型。實(shí)驗(yàn)結(jié)果表明，組合服務(wù)的QoS優(yōu)于傳統(tǒng)遺傳算法；Rodrigo等人[9]考慮了服務(wù)QoS動(dòng)態(tài)性，提出一種基于自回歸積分移動(dòng)平均(ARIMA)的方法預(yù)測(cè)服務(wù)的QoS,然而ARIMA方法要求數(shù)據(jù)具有平穩(wěn)性[10]。當(dāng)QoS趨于高度動(dòng)態(tài)化后，該方法的預(yù)測(cè)能力可靠性有待驗(yàn)證。Wang等人[12]提出將強(qiáng)化學(xué)習(xí)應(yīng)用到服務(wù)組合場(chǎng)景中，將skyline技術(shù)與Q-learning算法結(jié)合，建立了一種強(qiáng)化學(xué)習(xí)服務(wù)組合模型以解決大規(guī)模服務(wù)組合問(wèn)題，但是該方法忽略了服務(wù)QoS的動(dòng)態(tài)性。

基于進(jìn)化計(jì)算算法的服務(wù)組合算法在應(yīng)對(duì)小規(guī)模服務(wù)組合問(wèn)題時(shí)，算法效率相對(duì)較高，但是面對(duì)大規(guī)模服務(wù)組合問(wèn)題時(shí)，仍然存在模型過(guò)早收斂、算法尋優(yōu)能力差的問(wèn)題，導(dǎo)致輸出的組合服務(wù)QoS性能低下。在歷史QoS數(shù)據(jù)利用方面，由于服務(wù)調(diào)用頻率不固定，歷史QoS數(shù)據(jù)在時(shí)序上不平穩(wěn)，現(xiàn)有基于預(yù)測(cè)的方法對(duì)于歷史數(shù)據(jù)的利用準(zhǔn)確性不高。該文針對(duì)大規(guī)模服務(wù)組合問(wèn)題提出一種基于深度強(qiáng)化學(xué)習(xí)的模型，同時(shí)，考慮到服務(wù)歷史QoS數(shù)據(jù)的利用問(wèn)題，提出一種基于卷積網(wǎng)絡(luò)的方法，將服務(wù)歷史QoS數(shù)據(jù)充分利用，以保證QoS數(shù)據(jù)的準(zhǔn)確性。

1 Web服務(wù)組合模型

1.1 服務(wù)組合的形式化表示

服務(wù)組合的目標(biāo)是對(duì)用戶需求進(jìn)行拆分，而后在服務(wù)庫(kù)中尋找合適的服務(wù)組件，并按照一定的邏輯順序組合成相應(yīng)的組合服務(wù)。用戶的輸入包括兩方面：功能性需求、非功能性需求。如：“功能需求：旅行計(jì)劃制定”，“非功能性需求：費(fèi)用低于5 000元”。拆分后的功能性需求被描述為一個(gè)工作流，工作流有多種結(jié)構(gòu)。如：順序、并行、循環(huán)、選擇等。圖1所示的是包含順序及并行兩種結(jié)構(gòu)的工作流，以及根據(jù)該工作流進(jìn)行服務(wù)組合的過(guò)程。

圖1 服務(wù)組合場(chǎng)景

定義1：Web服務(wù)。

Web服務(wù)定義為一個(gè)四元組：

ws=

其中，ID為Web服務(wù)的在互聯(lián)網(wǎng)上的唯一標(biāo)識(shí)。Inp,Outp分別表示服務(wù)的輸入規(guī)范和輸出結(jié)果。QoS=為一個(gè)五元組，其中rt(response time)為響應(yīng)時(shí)間，表示用戶發(fā)出調(diào)用請(qǐng)求至收到服務(wù)響應(yīng)所消耗的時(shí)間，單位為“s”；rl(reliability)表示服務(wù)可靠性，文中將可靠性定義為：{“1”，“2”，“3”，“4”},分別對(duì)應(yīng){“好”，“較好”，“一般”，“差”}四個(gè)級(jí)別。t(throughout)表示服務(wù)吞吐量，單位為“MB”。p(price)表示服務(wù)調(diào)用的價(jià)格，單位為“元”。av(availability)={“0”，“1”}，表示服務(wù)可用性，“1”表示服務(wù)可用，“0”表示不可用。

定義2：組合Web服務(wù)。

組合Web服務(wù)定義為一個(gè)四元組：

WSCS=

Web服務(wù)分布式部署在各個(gè)服務(wù)提供商的服務(wù)器上，用戶通過(guò)網(wǎng)絡(luò)訪問(wèn)部署在各個(gè)服務(wù)器上的服務(wù)。這樣的“部署-使用”方式帶來(lái)的問(wèn)題是部分QoS指標(biāo)會(huì)受到服務(wù)器負(fù)載、通信鏈路狀態(tài)的影響[12]。例如：當(dāng)服務(wù)器負(fù)載過(guò)大或者通信鏈路擁塞時(shí)，Web服務(wù)的響應(yīng)時(shí)間便會(huì)增加。因此，該文將服務(wù)組合問(wèn)題建模為一個(gè)不確定環(huán)境下的多階段決策優(yōu)化問(wèn)題。

表1 不同工作流順序組合服務(wù)QoS屬性計(jì)算方法

1.2 馬爾可夫決策過(guò)程

馬爾可夫決策過(guò)程(Markov decision process，MDP)是一種通過(guò)交互式學(xué)習(xí)來(lái)實(shí)現(xiàn)目標(biāo)的理論框架，也是強(qiáng)化學(xué)習(xí)(reinforcement learning，RL)問(wèn)題在數(shù)學(xué)上的理想化形式[13]。在一個(gè)馬爾可夫決策過(guò)程中，進(jìn)行學(xué)習(xí)及實(shí)施決策的對(duì)象稱為智能體(agent)；智能體之外，所有與其相互作用的事物都被稱為環(huán)境(environment)。智能體與環(huán)境持續(xù)進(jìn)行交互，根據(jù)從環(huán)境中獲得的反饋來(lái)不斷調(diào)整自身行動(dòng)策略，以此最大化長(zhǎng)期收益。一個(gè)馬爾可夫決策過(guò)程可以用圖2表示。

圖2 馬爾可夫決策過(guò)程抽象

定義3：馬爾可夫決策過(guò)程。

馬爾可夫決策過(guò)程可以形式化定義為一個(gè)五元組：

MDP=

(1)S={s1,s2,…,sn}表示狀態(tài)集，表示環(huán)境中智能體所能觀察到的所有狀態(tài)，n為狀態(tài)的總數(shù)。

(3)P為狀態(tài)轉(zhuǎn)移函數(shù)，P(s'|s,a)表示智能體在狀態(tài)s下執(zhí)行動(dòng)作a(a∈A)后，狀態(tài)轉(zhuǎn)移到s'的概率值；s表示智能體當(dāng)前狀態(tài)，s'表示智能體在執(zhí)行動(dòng)作后，跳轉(zhuǎn)到的下一個(gè)狀態(tài)。

(4)R為獎(jiǎng)勵(lì)函數(shù)，當(dāng)動(dòng)作a(a∈A)被執(zhí)行后，環(huán)境從狀態(tài)s轉(zhuǎn)移到后繼狀態(tài)s'，智能體所獲得的獎(jiǎng)勵(lì)值R=r(s'|s,a)。

(5)G表示回報(bào)，是智能體所能獲得的獎(jiǎng)勵(lì)的總和。

定義4：策略(policy)與值函數(shù)(value function)。

策略π是狀態(tài)S到動(dòng)作A的映射(S→A)。π(s)=a表示環(huán)境狀態(tài)為s條件下，智能體依據(jù)策略π進(jìn)行決策，執(zhí)行動(dòng)作a。

值函數(shù)表示在一個(gè)確定的策略π及給定獎(jiǎng)勵(lì)函數(shù)R的情況下，當(dāng)前狀態(tài)的獎(jiǎng)勵(lì)以及未來(lái)根據(jù)策略的決策所能得到的總獎(jiǎng)勵(lì)的期望。數(shù)學(xué)表達(dá)見(jiàn)公式(1)：

Vπ(s|R)=R(s)+γVπ(s')

(1)

其中，參數(shù)γ∈[0,1]被稱為折扣率，用來(lái)權(quán)衡未來(lái)獎(jiǎng)勵(lì)對(duì)累積獎(jiǎng)勵(lì)的影響。

馬爾可夫決策過(guò)程中，智能體的目標(biāo)就是在所有的策略中尋找出最優(yōu)策略以在每個(gè)狀態(tài)獲得最大的值函數(shù)值。形式化表達(dá)如公式(2)：

(2)

1.3 基于馬爾可夫決策的服務(wù)組合模型MDPWSC

基于馬爾可夫決策模型，服務(wù)組合可以抽象為一個(gè)五元組MDPWSC=。各參數(shù)定義如下：

T={t1,t2,…,tn}為工作流，是智能體的狀態(tài)集合。工作流是對(duì)用戶功能性需求拆分成n個(gè)子功能后的抽象描述，其中ti表示第i個(gè)子功能，n表示用戶功能性需求所拆分成的子功能的總數(shù)。例如：用戶功能性需求為“旅行計(jì)劃制定”?？蓪⑵洳鸱譃椋簍1=“訂車票”、t2=“訂酒店”、“t3=景點(diǎn)購(gòu)票”、t4=“訂車票”四個(gè)流程。

P(t'|ws,t)表示狀態(tài)轉(zhuǎn)移概率，表示智能體在狀態(tài)t下，選擇動(dòng)作ws，狀態(tài)轉(zhuǎn)移到t'的概率。t'表示智能體在執(zhí)行完任意動(dòng)作后跳轉(zhuǎn)到的后續(xù)狀態(tài)。

R=r(t'|ws,t)表示獎(jiǎng)勵(lì)函數(shù)，表示智能體在狀態(tài)t下，選擇動(dòng)作ws，狀態(tài)轉(zhuǎn)移到t'，環(huán)境給予智能體的獎(jiǎng)勵(lì)。

G表示組合服務(wù)的QoS，也是服務(wù)組合問(wèn)題的優(yōu)化目標(biāo)。

2 算法描述

在動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境中，服務(wù)的QoS指標(biāo)將隨著網(wǎng)絡(luò)的動(dòng)態(tài)性改變[14]。如何通過(guò)現(xiàn)有的調(diào)用記錄發(fā)掘服務(wù)最真實(shí)的QoS值是決定能否完成最符合用戶QoS需求的服務(wù)組合的關(guān)鍵。同時(shí)，隨著應(yīng)用場(chǎng)景越來(lái)越復(fù)雜，如何應(yīng)對(duì)大規(guī)模服務(wù)組合也是急需解決的問(wèn)題。

2.1 基于CNN的獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)

獎(jiǎng)勵(lì)函數(shù)是強(qiáng)化學(xué)習(xí)中非常重要的變量之一，獎(jiǎng)勵(lì)函數(shù)的設(shè)定對(duì)最終優(yōu)化的目標(biāo)起重要作用。在基于強(qiáng)化學(xué)習(xí)QoS感知的服務(wù)組合問(wèn)題中，為了最終得到最優(yōu)的組合服務(wù)QoS,常把獎(jiǎng)勵(lì)函數(shù)設(shè)定為先對(duì)子服務(wù)的QoS值歸一化，而后對(duì)歸一化后的QoS值加權(quán)求和[10]。由于不同的QoS屬性有不同的取值范圍，現(xiàn)有方法都是首先利用公式(3)對(duì)各個(gè)屬性值做歸一化處理，而后采用公式(4)對(duì)多個(gè)QoS屬性加權(quán)求和得到結(jié)果作為獎(jiǎng)勵(lì)值。

(3)

(a)：當(dāng)QoS和R成正相關(guān)；(b)當(dāng)QoS和R成負(fù)相關(guān)。

(4)

其中，ri為QoS指標(biāo)對(duì)應(yīng)的獎(jiǎng)勵(lì)值，ωi為指標(biāo)對(duì)應(yīng)的權(quán)值，k為QoS指標(biāo)總數(shù)。

這種方法存在的問(wèn)題是需要人為設(shè)定各個(gè)指標(biāo)之間的權(quán)重關(guān)系ωi，準(zhǔn)確性不高，不能反映各QoS之間的真實(shí)聯(lián)系。同時(shí)，Web服務(wù)的每次調(diào)用都會(huì)產(chǎn)生相應(yīng)的QoS記錄，傳統(tǒng)的方法只選取最近一條調(diào)用記錄作為計(jì)算獎(jiǎng)勵(lì)值的依據(jù)，對(duì)于服務(wù)歷史QoS數(shù)據(jù)的利用過(guò)于粗糙。以上兩點(diǎn)原因?qū)?dǎo)致計(jì)算出的獎(jiǎng)勵(lì)值可靠性不足，并最終導(dǎo)致組合服務(wù)的QoS可靠性差。

深度學(xué)習(xí)(deep learning，DL)和神經(jīng)網(wǎng)絡(luò)(neural network)是當(dāng)下學(xué)術(shù)研究的熱點(diǎn)，并且在多個(gè)領(lǐng)域取得了顯著的成果。深度學(xué)習(xí)算法通過(guò)多個(gè)神經(jīng)元組成神經(jīng)層，再由多個(gè)神經(jīng)層組成復(fù)雜的神經(jīng)網(wǎng)絡(luò)，進(jìn)而解決復(fù)雜的問(wèn)題。從數(shù)據(jù)集[15]中可以獲得單個(gè)服務(wù)關(guān)于多個(gè)QoS指標(biāo)的歷史數(shù)據(jù)。該文利用卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network，CNN)在特征提取上的突出優(yōu)勢(shì)[16]，將單個(gè)服務(wù)的多次調(diào)用記錄以及相應(yīng)QoS指標(biāo)組合成二維矩陣輸入網(wǎng)絡(luò)，通過(guò)卷積網(wǎng)絡(luò)提取服務(wù)多條調(diào)用記錄之間的相互聯(lián)系特征，以及各個(gè)QoS指標(biāo)之間的相互關(guān)系特征，進(jìn)而輸出服務(wù)對(duì)應(yīng)的真實(shí)QoS值。

網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示。

圖3 CNN網(wǎng)絡(luò)結(jié)構(gòu)

輸入層為在狀態(tài)t'下被選中的服務(wù)的多次調(diào)用記錄與QoS指標(biāo)組成的二維矩陣，實(shí)驗(yàn)中選擇30條服務(wù)調(diào)用記錄中五個(gè)QoS指標(biāo)的值組成30*5的輸入矩陣，經(jīng)過(guò)一層卷積核大小為9*1*1的卷積層提取多條記錄之間的特征和一層卷積核大小為5*3*1的卷積層進(jìn)一步提取多條記錄之間的特征以及提取各個(gè)QoS指標(biāo)之間的特征，而后經(jīng)過(guò)全連接層，最終輸出t'狀態(tài)下，被選中服務(wù)對(duì)應(yīng)的獎(jiǎng)勵(lì)值R。相比起傳統(tǒng)的利用某一條QoS記錄計(jì)算獎(jiǎng)勵(lì)值的方法，基于CNN的方法可以將多條QoS屬性信息利用起來(lái)，更加能反映服務(wù)的真實(shí)QoS情況。

2.2 基于深度強(qiáng)化學(xué)習(xí)的服務(wù)組合算法ADR-WSC

Q-Learning算法[12]是求解強(qiáng)化學(xué)習(xí)問(wèn)題的基本方法之一，其基本思想是通過(guò)一張Q表來(lái)存儲(chǔ)“動(dòng)作-值”函數(shù)Q(t,ws)的值。對(duì)應(yīng)的Q值是對(duì)真實(shí)獎(jiǎng)勵(lì)的評(píng)估。算法通過(guò)比較Q值的估計(jì)值和實(shí)際值，不斷更新Q表，直至估計(jì)值接近真實(shí)值。在服務(wù)組合問(wèn)題中，其迭代公式如下：

Q(t,ws)=Q(t,ws)+α(r(t'|t,ws)+γmaxQ(t',ws')-Q(t,ws))

(5)

其中，α為學(xué)習(xí)率，ws'為t'狀態(tài)下選擇的動(dòng)作。

當(dāng)面臨解決大規(guī)模離散空間或連續(xù)狀態(tài)空間的問(wèn)題時(shí)，例如：待解決問(wèn)題的狀態(tài)空間大小為5，每個(gè)狀態(tài)對(duì)應(yīng)的動(dòng)作空間大小為10時(shí)，這時(shí)的Q表是一個(gè)5*10的矩陣，計(jì)算和更新開(kāi)銷相對(duì)較小，訓(xùn)練和后續(xù)查表開(kāi)銷不大。但應(yīng)用到實(shí)際生產(chǎn)領(lǐng)域當(dāng)中，一個(gè)子功能對(duì)應(yīng)的可選服務(wù)往往成百上千個(gè),工作流的長(zhǎng)度也數(shù)以十甚至百計(jì)。對(duì)于一個(gè)工作流長(zhǎng)度為30，即狀態(tài)空間大小為30，每個(gè)狀態(tài)空間對(duì)應(yīng)的動(dòng)作空間大小為500時(shí)，將會(huì)形成50030種組合方案，這是個(gè)巨大的搜索空間。并且，一次訓(xùn)練過(guò)程就需要經(jīng)過(guò)50030次計(jì)算。在網(wǎng)絡(luò)波動(dòng)的情況下，光是計(jì)算開(kāi)銷就足以導(dǎo)致計(jì)算結(jié)果失效。因此，在Q-Learning的基礎(chǔ)上，加入了深度網(wǎng)絡(luò)(deep neural network，DNN)替代Q表，以解決Q-Learning在面對(duì)大規(guī)模問(wèn)題時(shí)的瓶頸[17]。

基于強(qiáng)化學(xué)習(xí)良好的決策能力和卷積網(wǎng)絡(luò)的特征提取能力以及神經(jīng)網(wǎng)絡(luò)本身強(qiáng)大的表征能力，該文提出了一種基于深度強(qiáng)化學(xué)習(xí)的QoS自適應(yīng)服務(wù)感知算法：“Adaptive Deep Reinforcement Learning-Web Service Composition(ADR-WSC)”。為了解決獎(jiǎng)勵(lì)值R的可靠性問(wèn)題，采用了卷積神經(jīng)網(wǎng)絡(luò)代替?zhèn)鹘y(tǒng)的直接對(duì)QoS記錄加權(quán)求和的方式；為了解決大規(guī)?！盃顟B(tài)-動(dòng)作”值存儲(chǔ)于Q表中導(dǎo)致算法性能低下的問(wèn)題，采用了深度神經(jīng)網(wǎng)絡(luò)替代傳統(tǒng)的Q表。綜合上述兩點(diǎn)改進(jìn)，傳統(tǒng)的Q-Learning中Q值的迭代更新公式應(yīng)轉(zhuǎn)化為：

Q(t,ws)=Q(t,ws)+α(CNN(t'|t,ws)+

γmaxDNN(t',ws')-Q(t,ws))

(6)

算法具體過(guò)程如下：

算法：服務(wù)組合算法ADR-WSC。

(1)初始化“動(dòng)作-值”函數(shù)Q(T,ws,ω)的參數(shù)ω、加載CNN(T,ws)網(wǎng)絡(luò)已保存的訓(xùn)練參數(shù)。加載隨機(jī)探索率ε、學(xué)習(xí)率α、工作流長(zhǎng)度T、初始化經(jīng)驗(yàn)回放區(qū)域D,確定訓(xùn)練輪數(shù)MAX_EPISODE，以及網(wǎng)絡(luò)訓(xùn)練的BATCH_SIZE

(2)For each episode in MAX_EPISODE：

(3)FortiinT：

(4)在工作流ti對(duì)應(yīng)的可用服務(wù)集A(ti)中根據(jù)ε-greedy策略選取出相應(yīng)的服務(wù)ws

(5)綁定服務(wù)，獲得下一個(gè)狀態(tài)t'，并根據(jù)CNN(ti,ws)網(wǎng)絡(luò)計(jì)算出對(duì)應(yīng)的獎(jiǎng)勵(lì)r(t'|ws,t)

(6)ti=t'，根據(jù)ti,ws計(jì)算Q值，公式如下:

y(ti,ws)=

(7)將[ti,ws,y(ti,ws)]存入經(jīng)驗(yàn)回放區(qū)

(8)判斷緩沖區(qū)長(zhǎng)度是否達(dá)到BATCH_SIZE，若達(dá)到，則將經(jīng)驗(yàn)區(qū)中的數(shù)據(jù)喂入網(wǎng)絡(luò)訓(xùn)練，利用梯度下降算法更新Q(T,ws,ω)中的所有參數(shù)。后清空緩沖區(qū)。否則，結(jié)束此次循環(huán)

(9)End for

(10)End for

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)數(shù)據(jù)集的基礎(chǔ)為公共有效數(shù)據(jù)集QWS[15]，QWS數(shù)據(jù)集中的所有數(shù)據(jù)均為真實(shí)網(wǎng)絡(luò)中可用Web服務(wù)被調(diào)用后獲得的統(tǒng)計(jì)數(shù)據(jù)。包含2 500個(gè)Web服務(wù)及其對(duì)應(yīng)的11個(gè)QoS屬性值，實(shí)驗(yàn)中選用了數(shù)據(jù)集中的四個(gè)QoS屬性：響應(yīng)時(shí)間、可用性、可靠性、吞吐量，并擴(kuò)充了服務(wù)的價(jià)格屬性。網(wǎng)絡(luò)使用深度學(xué)習(xí)框架Tensorflow搭建，實(shí)驗(yàn)在一臺(tái)操作系統(tǒng)為Win10，CPU為E3-1226，內(nèi)存為16G，GPU為NVDIA GT-1030的機(jī)器上運(yùn)行。

3.2 結(jié)果分析

(1)初始探索率對(duì)總收益的影響。

用于預(yù)測(cè)獎(jiǎng)勵(lì)R的CNN網(wǎng)絡(luò)是在ADR-WSC算法運(yùn)行之前就已經(jīng)完成訓(xùn)練的，因此算法迭代過(guò)程中，不需要再對(duì)其做額外的訓(xùn)練。而用于擬合‘動(dòng)作-價(jià)值’函數(shù)的DNN網(wǎng)絡(luò)則是在線訓(xùn)練的，經(jīng)驗(yàn)回放區(qū)域的容量大小、智能體的隨機(jī)探索率等超參數(shù)會(huì)很大程度上影響實(shí)驗(yàn)結(jié)果，因此，實(shí)驗(yàn)中先驗(yàn)證了初始探索率ε的大小對(duì)總收益(即組合模型的整體QoS)的影響。

圖4 探索率對(duì)總收益值的影響

圖4顯示的是服務(wù)組合模型中流程數(shù)為10，每個(gè)流程對(duì)應(yīng)有300個(gè)備選服務(wù)時(shí)，探索率ε=0.3、ε=0.5以及ε=0.8時(shí)，算法收斂時(shí)最大收益的對(duì)比。實(shí)驗(yàn)中固定了學(xué)習(xí)率α=0.9。經(jīng)驗(yàn)區(qū)容量為150。為了模型更快的收斂，實(shí)驗(yàn)中還采用了探索率遞減的方法。算法迭代的過(guò)程中，探索率會(huì)隨著迭代輪數(shù)逐漸降低，實(shí)驗(yàn)中設(shè)置的探索率值僅僅是算法開(kāi)始迭代時(shí)的探索率。結(jié)果表明，當(dāng)模型收斂時(shí)，在ε=0.3和ε=0.5情況下，智能體獲得的總的收益值只有不到17，而ε=0.8時(shí)，收益值達(dá)到18.5以上。筆者認(rèn)為，讓智能體前期更多地探索環(huán)境知識(shí)，積攢更多的訓(xùn)練數(shù)據(jù)，更加有利于模型的準(zhǔn)確性。因此，后續(xù)實(shí)驗(yàn)將采取探索率ε=0.8。

(2)經(jīng)驗(yàn)區(qū)容量對(duì)算法收斂速度的影響。

經(jīng)驗(yàn)區(qū)容量直接決定了喂入網(wǎng)絡(luò)的訓(xùn)練數(shù)據(jù)量，對(duì)算法收斂起了重要作用，因此，文中接著驗(yàn)證了經(jīng)驗(yàn)區(qū)容量大小對(duì)于模型收斂的影響。圖5顯示的是服務(wù)組合模型中流程數(shù)為10，每個(gè)流程對(duì)應(yīng)有300個(gè)備選服務(wù)時(shí)，不同經(jīng)驗(yàn)區(qū)容量對(duì)算法收斂過(guò)程的影響。實(shí)驗(yàn)中固定了探索率ε=0.8，學(xué)習(xí)率α=0.9。結(jié)果表明，在探索率為0.8的情況下，經(jīng)驗(yàn)區(qū)容量取150、200、250、300均可以保證算法收斂到最優(yōu)解。從節(jié)省資源的角度上來(lái)說(shuō)，選擇150更合適。因此，后續(xù)實(shí)驗(yàn)中，選擇經(jīng)驗(yàn)區(qū)容量為150。

圖5 經(jīng)驗(yàn)區(qū)容量對(duì)總收益的影響

(3)組合服務(wù)QoS對(duì)比。

在確定超參數(shù)以后，還對(duì)模型的整體性能做了驗(yàn)證。首先是算法收斂后的QoS值對(duì)比。算法的核心目的是提供QoS更優(yōu)的組合服務(wù)，因此組合服務(wù)的QoS是模型最重要的指標(biāo)。實(shí)驗(yàn)中選取了基于粒子群算法的FWPSO算法[11]、基于時(shí)間序列預(yù)測(cè)和遺傳算法的ARIMA+GA算法[6]做對(duì)比。同時(shí)，為了獲取實(shí)際最優(yōu)組合服務(wù)QoS，實(shí)驗(yàn)中還使用了窮舉法求解作為參照。

圖6 各算法在不同規(guī)模服務(wù)組合場(chǎng)景中 QoS值對(duì)比

圖6顯示的是ARIMA+GA、FWPSO、ADR-WSC以及窮舉算法在求解服務(wù)組合問(wèn)題模型后，輸出的組合服務(wù)QoS值。需要說(shuō)明的是：實(shí)驗(yàn)中對(duì)每種算法運(yùn)行了多次，取收斂后最低的QoS值作為對(duì)比數(shù)據(jù)，這樣做的好處是：可以明確獲知算法在最壞的情況下輸出的結(jié)果。從圖中可以看出，當(dāng)單個(gè)流程的候選服務(wù)數(shù)小于等于250時(shí)，ARIMA+GA、FWPSO、ADR-WSC均可以求得最優(yōu)解。當(dāng)備選服務(wù)大于250時(shí)，ARIMA+GA、FWPSO出現(xiàn)提前收斂至局部最優(yōu)的情況，無(wú)法找到全局最優(yōu)解。而ADR-WSC算法迭代的過(guò)程中，不斷更新網(wǎng)絡(luò)，即使問(wèn)題規(guī)模擴(kuò)大，也可以找出最優(yōu)解。

(4)算法時(shí)間開(kāi)銷對(duì)比。

由于每個(gè)算法收斂時(shí)迭代輪數(shù)不同，實(shí)驗(yàn)中對(duì)比的是當(dāng)模型收斂時(shí)，所需要的最小時(shí)間開(kāi)銷。實(shí)驗(yàn)中沒(méi)有將窮舉法的運(yùn)行時(shí)間繪制在圖上，因?yàn)槠鋾r(shí)間開(kāi)銷跟其他三種算法不在一個(gè)量級(jí)上。從圖7中可以看出，當(dāng)單個(gè)流程的備選服務(wù)數(shù)量越來(lái)越多的時(shí)候，三種算法的時(shí)間開(kāi)銷都是隨著問(wèn)題規(guī)模遞增的，但是ADR-WSC算法的時(shí)間開(kāi)銷均低于其他兩種算法，ADR-WSC算法運(yùn)行速度快可能的原因是：當(dāng)完成網(wǎng)絡(luò)訓(xùn)練以后，算法執(zhí)行過(guò)程中，只需要通過(guò)網(wǎng)絡(luò)完成特定數(shù)據(jù)的運(yùn)算即可，是針對(duì)固定數(shù)據(jù)的運(yùn)算，而不像其他兩種算法每次運(yùn)行都必須迭代所有數(shù)據(jù)。

圖7 GA,PSO,ADR-WSC運(yùn)行時(shí)間對(duì)比

4 結(jié)束語(yǔ)

提出了一種基于深度強(qiáng)化學(xué)習(xí)的自適應(yīng)優(yōu)化方法ADR-WSC來(lái)解決大規(guī)模QoS感知的Web服務(wù)組合優(yōu)化問(wèn)題，考慮了多個(gè)QoS屬性之間的相互關(guān)系以及如何利用Web服務(wù)多條歷史調(diào)用記錄分析Web服務(wù)QoS可靠性，并改進(jìn)了基于傳統(tǒng)Q-Learning的算法，以解決大規(guī)模服務(wù)組合問(wèn)題。實(shí)驗(yàn)結(jié)果表明，該方法在組合服務(wù)QoS上優(yōu)于傳統(tǒng)尋優(yōu)方法，并且在遇到大規(guī)模服務(wù)組合場(chǎng)景時(shí)，具有更高的可擴(kuò)展性，能夠有效地處理大規(guī)模服務(wù)組合問(wèn)題。

云計(jì)算發(fā)展速度越來(lái)越快，Web服務(wù)的數(shù)量在迅猛增長(zhǎng)，對(duì)于服務(wù)組合問(wèn)題來(lái)說(shuō)，每個(gè)子流程的候選服務(wù)數(shù)量越多，完成組合的難度越大，算法運(yùn)行開(kāi)銷也越久。如果用戶對(duì)于時(shí)效要求進(jìn)一步提高，比如：當(dāng)應(yīng)用場(chǎng)景為高速智能駕駛時(shí)，對(duì)于算法的時(shí)效要求更為嚴(yán)格。今后將進(jìn)一步研究如何提高超大規(guī)模服務(wù)組合低時(shí)耗的問(wèn)題。