高遠(yuǎn)翔，羅 龍，孫 罡*

(1. 電子科技大學(xué)光纖傳感與通信教育部重點(diǎn)實(shí)驗(yàn)室 成都 611731)

近年來(lái)，機(jī)器學(xué)習(xí)方法在包括圖像識(shí)別[1]、機(jī)器翻譯[2]等多個(gè)領(lǐng)域得到了廣泛應(yīng)用。由于數(shù)據(jù)量及算法復(fù)雜度的增長(zhǎng)，機(jī)器學(xué)習(xí)應(yīng)用通常在一個(gè)由大量計(jì)算資源組成的集群系統(tǒng)上分布式運(yùn)行。機(jī)器學(xué)習(xí)應(yīng)用周期性地在集群網(wǎng)絡(luò)中產(chǎn)生跨計(jì)算資源的數(shù)據(jù)分組，這些數(shù)據(jù)分組在網(wǎng)絡(luò)中的傳輸延遲對(duì)機(jī)器學(xué)習(xí)應(yīng)用的時(shí)間效率具有關(guān)鍵影響。

機(jī)器學(xué)習(xí)集群常用多階段Clos 網(wǎng)絡(luò)[3-5]，其通過(guò)多個(gè)階段的交換機(jī)將各個(gè)計(jì)算資源互聯(lián)起來(lái)。多階段網(wǎng)絡(luò)在兩個(gè)計(jì)算資源間提供了大量可供選擇的路徑，且網(wǎng)絡(luò)中同時(shí)有大量分組需要路由決策，所以分組的路由是一個(gè)組合優(yōu)化難題。

基于最短路徑的擬靜態(tài)路由算法[6]，如貝爾曼-福特算法、狄克斯特拉算法，無(wú)法跟隨集群網(wǎng)絡(luò)負(fù)載狀態(tài)的迅速變化。而多階段網(wǎng)絡(luò)通常采用基于啟發(fā)式的動(dòng)態(tài)路由算法[3,7]，目前，廣泛使用的是基于“加入最短隊(duì)列”策略[3]的啟發(fā)式路由算法。該算法將分組轉(zhuǎn)發(fā)到具有最少排隊(duì)分組的下一跳交換機(jī)。這些啟發(fā)式算法基于網(wǎng)絡(luò)局部的負(fù)載信息進(jìn)行路由決策，常導(dǎo)致網(wǎng)絡(luò)全局負(fù)載不均衡，無(wú)法保證最小的平均分組傳輸延遲。

本文提出一種基于強(qiáng)化學(xué)習(xí)的分組路由算法，將多階段網(wǎng)絡(luò)的路由問(wèn)題建模為一個(gè)馬爾科夫決策過(guò)程[8](markov decision process, MDP)，這是該問(wèn)題的首個(gè)MDP 模型。為了求解該MDP 的最佳路由策略，本文提出了最大似然策略迭代(maximum likelihood policy iteration, MLPI)算法。該算法在策略評(píng)估步驟中使用最大似然價(jià)值函數(shù)估計(jì)器，該價(jià)值函數(shù)估計(jì)器克服了現(xiàn)有強(qiáng)化學(xué)習(xí)方法[9-10]中蒙泰卡羅(Monte Carlo, MC)或時(shí)間差分(temporaldifference, TD)價(jià)值函數(shù)估計(jì)器樣本效率低的問(wèn)題。為了應(yīng)對(duì)MLPI 算法策略改進(jìn)步驟中涉及的組合優(yōu)化難題，本文提出了一個(gè)序列最小化的方法，通過(guò)將組合優(yōu)化分解為一系列可求解的簡(jiǎn)單優(yōu)化子問(wèn)題來(lái)進(jìn)行有效的策略改進(jìn)。

基于NS-3 網(wǎng)絡(luò)模擬器的仿真實(shí)驗(yàn)結(jié)果表明，本文的MLPI 算法找到的路由策略較“加入最短隊(duì)列”啟發(fā)式策略減少了38.3% 的平均排隊(duì)分組數(shù)目，同時(shí)減少了17.6%的平均分組延遲。此外，MLPI算法的學(xué)習(xí)效率遠(yuǎn)高于基于蒙泰卡羅(MC)或時(shí)間差分(TD)價(jià)值函數(shù)估計(jì)器的強(qiáng)化學(xué)習(xí)算法。

1 多階段網(wǎng)絡(luò)的分組路由

如圖1a 所示，在一個(gè)三階段網(wǎng)絡(luò)中，分組路由問(wèn)題的模型是一個(gè)離散時(shí)間排隊(duì)系統(tǒng)的控制問(wèn)題。在一個(gè)特殊的時(shí)刻t，由計(jì)算資源產(chǎn)生的數(shù)據(jù)分組到達(dá)輸入階段的交換機(jī)。一個(gè)輸入或輸出交換機(jī)通常連接多個(gè)計(jì)算資源。為了簡(jiǎn)潔表達(dá)，連接到輸入輸出交換機(jī)上的計(jì)算資源沒(méi)有在圖中呈現(xiàn)。在第i個(gè)輸入交換機(jī)，目的地為第j個(gè)輸出交換機(jī)的到達(dá)分組數(shù)目服從一個(gè)到達(dá)率為 λi j的泊松分布，且這些到達(dá)分組排在第i個(gè)輸入交換機(jī)的第j個(gè)隊(duì)列中，網(wǎng)絡(luò)狀態(tài)是該網(wǎng)絡(luò)中各隊(duì)列分組的數(shù)目。

在每個(gè)時(shí)刻t，不同階段交換機(jī)之間的每條鏈路負(fù)責(zé)將分組從上游交換機(jī)傳輸?shù)揭粋€(gè)下游交換機(jī)，具有一個(gè)單位的容量。假設(shè)使用先入先出排隊(duì)準(zhǔn)則，路由算法需要為每一個(gè)隊(duì)列中的隊(duì)首分組選擇一個(gè)下游鏈路來(lái)傳輸它。如圖1b 所示，所有隊(duì)首分組的路由選擇可視作一個(gè)全局的路由動(dòng)作。遵循這個(gè)路由動(dòng)作，隊(duì)首分組在選擇的鏈路上傳輸。在下一個(gè)時(shí)刻t+1，如圖1c 所示，傳輸中的分組同時(shí)到達(dá)下游交換機(jī)的相應(yīng)隊(duì)列。所有分組到達(dá)下游交換機(jī)后，到達(dá)輸入階段交換機(jī)的新一輪分組遵循同樣的泊松分布。然后類似的路由動(dòng)作和分組傳輸重復(fù)進(jìn)行。

圖1 三階段網(wǎng)絡(luò)分組路由的離散時(shí)間排隊(duì)系統(tǒng)模型

2 MDP 模型

本節(jié)將多階段網(wǎng)絡(luò)分組路由問(wèn)題建模為一個(gè)馬爾科夫決策過(guò)程MDP。該MDP 由一個(gè)四元組S,A,c,P指定，其中S是狀態(tài)空間， A是動(dòng)作空間，c是代價(jià)函數(shù)，P是狀態(tài)轉(zhuǎn)移概率。該MDP 的具體定義如下。

狀態(tài)：該MDP 在時(shí)刻t的狀態(tài)表示為st，是一個(gè)3 維矩陣，其元素表示為n(sti)j，表示第i個(gè)交換機(jī)上第j個(gè)隊(duì)列在第s個(gè)階段的分組數(shù)目。

動(dòng)作：假設(shè)網(wǎng)絡(luò)中有M個(gè)隊(duì)首分組，該MDP在時(shí)刻t的動(dòng)作是為每一個(gè)隊(duì)首分組選擇的鏈路所組成的集合{a1,a2,···,aM}。動(dòng)作產(chǎn)生的順序是從在最上游階段的最低指標(biāo)輸入交換機(jī)上最低指標(biāo)隊(duì)列中的隊(duì)首分組開始，逐漸輪詢到同一個(gè)輸入交換機(jī)上更高指標(biāo)隊(duì)列中的隊(duì)首分組，然后輪詢到同一個(gè)階段中更高指標(biāo)的輸入交換機(jī)上的各隊(duì)首分組，最終輪詢到更下游交換機(jī)上的各隊(duì)首分組。為第m個(gè)隊(duì)首分組選擇的鏈路am是沒(méi)有被其他隊(duì)首分組選擇的空閑下游鏈路中的一個(gè)。當(dāng)一個(gè)交換機(jī)上的某些隊(duì)列沒(méi)有隊(duì)首分組時(shí)，為了充分利用鏈路，該交換機(jī)上其他隊(duì)列中的非隊(duì)首分組也可能在隊(duì)首分組選擇鏈路后獲得一個(gè)鏈路分配。

3 基于最大似然價(jià)值估計(jì)的策略評(píng)估

式中，St+w表示時(shí)刻t+w狀態(tài)的隨機(jī)變量,w是窗口大小。窗口大小通常設(shè)為能使得更遠(yuǎn)未來(lái)狀態(tài)的代價(jià)可以忽略不計(jì)的值，如在γ=0.99時(shí)設(shè)為500。Eπ,Λ[·]是在策略 π和泊松參數(shù) Λ下，相對(duì)于St+w的概率分布的期望。由于到達(dá)參數(shù)通常是未知的，作為其函數(shù)，上述價(jià)值函數(shù)需要從采樣的狀態(tài)樣本軌跡中估計(jì)得到。

現(xiàn)有強(qiáng)化學(xué)習(xí)算法使用蒙泰卡羅(MC)或時(shí)間差分(TD)價(jià)值函數(shù)估計(jì)器[9-10]，但MC 和TD 價(jià)值估計(jì)樣本效率低[9]。本文使用價(jià)值函數(shù)的最大似然估計(jì)器，推導(dǎo)如下。

給定一個(gè)策略 π，式(3) 中價(jià)值函數(shù)是未知泊松到達(dá)參數(shù) Λ的函數(shù)。給定一個(gè)時(shí)間長(zhǎng)度為T的樣本軌跡，參數(shù){λij}的最大似然估計(jì)(maximum likelihood estimate, MLE)由如下的平均到達(dá)率給出[12]：

式中，樣本軌跡{st,st+1,···,st+w}是在估計(jì)的到達(dá)參數(shù)和策略π下模擬的狀態(tài)轉(zhuǎn)移。

4 最大似然策略迭代

4.1 基于序列最小化的策略改進(jìn)

式中，s′是在狀態(tài)s采取動(dòng)作序列{a1,a2,···,aM}所導(dǎo)致的下一個(gè)狀態(tài)。式(7)中的最小化問(wèn)題是一個(gè)困難的組合優(yōu)化問(wèn)題，其搜索空間隨網(wǎng)絡(luò)中隊(duì)首分組數(shù)目呈指數(shù)式增加。為了快速求解問(wèn)題，本文使用一種在神經(jīng)動(dòng)態(tài)規(guī)劃文獻(xiàn)[15] 中被稱為動(dòng)作空間復(fù)雜度與狀態(tài)空間復(fù)雜度折衷的方法，通過(guò)引入一系列描述每個(gè)動(dòng)作后果的人工狀態(tài)使得策略改進(jìn)步驟能序列地對(duì)每一個(gè)動(dòng)作進(jìn)行。

4.2 最大似然策略迭代算法

如算法1 所示，該MLPI 算法首先初始化一個(gè)近似價(jià)值函數(shù)估計(jì)的卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network, CNN)，Vθ0作為初始的價(jià)值函數(shù)估計(jì)。初始路由策略 π0是相對(duì)于Vθ0的ε-貪婪策略。具體地，在每步序列最小化時(shí)以概率為1-ε選取最佳動(dòng)作而以概率ε隨機(jī)選取鏈路。在第n次策略迭代時(shí)，該算法觀察網(wǎng)絡(luò)進(jìn)行T步狀態(tài)轉(zhuǎn)移，且累加到達(dá)輸入交換機(jī)各隊(duì)列的分組總數(shù)。然后，該算法計(jì)算泊松參數(shù)的最大似然估計(jì)Λ?。

接下來(lái)，MLPI 算法跟隨策略 πn執(zhí)行K(K?T)步模擬的狀態(tài)轉(zhuǎn)移。模擬狀態(tài)轉(zhuǎn)移中經(jīng)歷的狀態(tài)作為輸入集S={sl,l=1,2,···,L}，對(duì)應(yīng)的折扣樣本總代價(jià)C={c(sl)+γ1c(sl+1)+···+γWc(sl+W)}作為輸出集構(gòu)成了一個(gè)龐大的數(shù)據(jù)集Dn。該數(shù)據(jù)集用來(lái)訓(xùn)練Vθn幾個(gè)來(lái)回(epochs)，得到的價(jià)值網(wǎng)絡(luò)Vθn+1是最大似然價(jià)值函數(shù)的近似。之后，在下一次迭代中遇到的每個(gè)狀態(tài)，該算法通過(guò)ε-貪婪地相對(duì)于Vθn+1求解式(9)中的序列最小化來(lái)產(chǎn)生新策略πn+1。

5 實(shí) 驗(yàn)

5.1 測(cè)試網(wǎng)絡(luò)和路由代理

NS-3 網(wǎng)絡(luò)模擬器是一個(gè)廣泛使用的分組級(jí)別的離散事件仿真器[16]。本文基于NS-3 搭建了一個(gè)多階段的網(wǎng)絡(luò)測(cè)試環(huán)境，參考強(qiáng)化學(xué)習(xí)中環(huán)境-代理(agent) 的交互框架[10]搭建了一個(gè)網(wǎng)絡(luò)路由代理。該網(wǎng)絡(luò)路由代理使用由MLPI 算法訓(xùn)練完成的價(jià)值網(wǎng)絡(luò)產(chǎn)生最佳的路由動(dòng)作序列。

具體來(lái)說(shuō)，該測(cè)試網(wǎng)絡(luò)是一個(gè)按時(shí)隙產(chǎn)生控制和進(jìn)行傳輸?shù)木W(wǎng)絡(luò)，在每個(gè)時(shí)隙t，該測(cè)試網(wǎng)絡(luò)中各交換機(jī)將各隊(duì)列的分組數(shù)目上報(bào)給網(wǎng)絡(luò)路由代理。網(wǎng)絡(luò)路由代理得到該時(shí)刻的網(wǎng)絡(luò)狀態(tài)，作為產(chǎn)生路由決策的初始狀態(tài)。從該狀態(tài)開始，路由代理相對(duì)于訓(xùn)練好的價(jià)值網(wǎng)絡(luò)逐步求解序列最小化問(wèn)題(無(wú)需ε-探索)，來(lái)得到該狀態(tài)下所有隊(duì)首分組的最佳路由向量{a*1,a*2,···,a*M}。之后，路由代理將該最佳路由動(dòng)作序列下達(dá)給各交換機(jī)，各交換機(jī)按照指定的路由動(dòng)作發(fā)送各隊(duì)列的隊(duì)首分組。當(dāng)發(fā)送的各分組到達(dá)下游交換機(jī)后，網(wǎng)絡(luò)進(jìn)入下一個(gè)時(shí)隙t+Δt并重復(fù)上述交互過(guò)程。

5.2 實(shí)驗(yàn)設(shè)定

本文在一個(gè)每階段包含16 個(gè)或20 個(gè)交換機(jī)的三階段網(wǎng)絡(luò)中測(cè)試MLPI 算法。在實(shí)驗(yàn)前，分組到達(dá)率{λij}由獨(dú)立同分布的0～1 之間的均勻分布產(chǎn)生，網(wǎng)絡(luò)負(fù)載ρ定義為總到達(dá)率除以單階段的總鏈路容量。

表2 MLPI 算法的超參數(shù)

5.3 對(duì)比方案

將MLPI 算法與典型及現(xiàn)有最優(yōu)的路由啟發(fā)式算法進(jìn)行對(duì)比。

1)隨機(jī)路由(Rand) 算法：交換機(jī)隨機(jī)選擇一個(gè)空閑鏈路來(lái)傳輸隊(duì)首分組。

2)加入最短隊(duì)列(join-the-shortest-queue, JSQ)[3,6]算法：對(duì)于交換機(jī)上第j個(gè)隊(duì)列的隊(duì)首分組，交換機(jī)在所有空閑鏈路里選擇其下游交換機(jī)上第j個(gè)隊(duì)列最短的鏈路來(lái)傳輸該分組。

表1 卷積神經(jīng)網(wǎng)絡(luò)的超參數(shù)

3) Power-of-two-choices(Po2)[7,18]算法：對(duì)于交換機(jī)上第j個(gè)隊(duì)列的隊(duì)首分組，交換機(jī)首先隨機(jī)選取兩個(gè)空閑鏈路作為候選鏈路，再在候選鏈路中選擇其下游交換機(jī)上第j個(gè)隊(duì)列更短的鏈路來(lái)傳輸該分組。

4)基于蒙泰卡羅價(jià)值估計(jì)的強(qiáng)化學(xué)習(xí)(MC)[10]算法：該方法遵循相對(duì)于價(jià)值網(wǎng)絡(luò)ε-貪婪的策略來(lái)與測(cè)試網(wǎng)絡(luò)進(jìn)行交互，在交互過(guò)程中產(chǎn)生的狀態(tài)轉(zhuǎn)移樣本集合被用來(lái)在線訓(xùn)練價(jià)值網(wǎng)絡(luò)。對(duì)每個(gè)狀態(tài)，價(jià)值網(wǎng)絡(luò)的訓(xùn)練目標(biāo)為在一個(gè)窗口范圍內(nèi)未來(lái)狀態(tài)的總折扣代價(jià)值。在產(chǎn)生一批訓(xùn)練示例后，該算法相對(duì)于價(jià)值網(wǎng)絡(luò)參數(shù)執(zhí)行一步隨機(jī)梯度下降。

5)基于n-步TD 價(jià)值估計(jì)的強(qiáng)化學(xué)習(xí)(TD)[10]算法：類似于MC，對(duì)每個(gè)狀態(tài)，價(jià)值網(wǎng)絡(luò)的訓(xùn)練目標(biāo)是在一個(gè)大小為n(n=100)的窗口內(nèi)的未來(lái)狀態(tài)的總折扣代價(jià)，再加上第n+1個(gè)未來(lái)狀態(tài)在γn+1折扣后的價(jià)值估計(jì)值。在產(chǎn)生一批訓(xùn)練示例后，該算法執(zhí)行一步隨機(jī)梯度下降。

5.4 實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)中，MLPI 算法執(zhí)行一系列的策略迭代步驟直到策略不再改進(jìn)。在第n次策略迭代時(shí)，MLPI算法觀察測(cè)試網(wǎng)絡(luò)，進(jìn)行20 個(gè)時(shí)隙的狀態(tài)轉(zhuǎn)移來(lái)更新對(duì)泊松參數(shù)的估計(jì)。然后，MLPI 算法執(zhí)行3 200步模擬的狀態(tài)轉(zhuǎn)移，這個(gè)過(guò)程中收集到的訓(xùn)練示例(接近1 000 000 個(gè)，包含中間狀態(tài))用來(lái)訓(xùn)練價(jià)值網(wǎng)絡(luò)10 個(gè)來(lái)回。訓(xùn)練完成后，從一個(gè)空的網(wǎng)絡(luò)狀態(tài)開始，路由代理使用現(xiàn)有價(jià)值網(wǎng)絡(luò)對(duì)應(yīng)的路由策略來(lái)控制測(cè)試網(wǎng)絡(luò)200 個(gè)時(shí)隙，且將平均排隊(duì)分組總數(shù)和平均分組延遲記錄下來(lái)，作為現(xiàn)有策略πn的性能度量。上述迭代持續(xù)進(jìn)行，直到策略的性能不再改進(jìn)。

5.4.1 平均排隊(duì)分組總數(shù)

圖2 的結(jié)果顯示，對(duì)于每階段16 個(gè)交換機(jī)的網(wǎng)絡(luò)，在6 次最大似然策略迭代之后，MLPI 找到的路由策略的平均排隊(duì)分組總數(shù)達(dá)到最低點(diǎn)，其相對(duì)于JSQ 和Po2 算法分別減少了約26.6%和21.1%的平均分組總數(shù)。圖3 的結(jié)果顯示，對(duì)于每階段20 個(gè)交換機(jī)的網(wǎng)絡(luò)，在7 次最大似然策略迭代后，MLPI 找到的路由策略相對(duì)于JSQ 和Po2 分別減少了約20.7%和17.2%的平均排隊(duì)分組總數(shù)。然而，MC 或TD 算法的平均排隊(duì)分組總數(shù)始終保持在較高的程度，幾乎沒(méi)有從經(jīng)驗(yàn)中學(xué)習(xí)的跡象。

圖2 每階段16 個(gè)交換機(jī)時(shí)的平均排隊(duì)分組總數(shù)

圖3 每階段20 個(gè)交換機(jī)時(shí)的平均排隊(duì)分組總數(shù)

5.4.2 平均分組延遲

如圖4 所示，經(jīng)過(guò)8 次最大似然策略迭代，MLPI 收斂到的路由策略相對(duì)于JSQ 和Po2 分別減少約17.6% 和13.9% 的平均分組延遲。如圖5 所示，經(jīng)過(guò)8 次最大似然策略迭代，MLPI 算法收斂到的路由策略相對(duì)于JSQ 和Po2 分別減少了約13.0%和10.3%的平均分組延遲。可以觀察到平均分組延遲的下降趨勢(shì)與平均排隊(duì)分組總數(shù)的下降趨勢(shì)一致。

圖4 每階段16 個(gè)交換機(jī)時(shí)的平均分組延遲

圖5 每階段20 個(gè)交換機(jī)時(shí)的平均分組延遲

5.4.3 網(wǎng)絡(luò)負(fù)載的影響

圖6 展示了MLPI 算法在各負(fù)載條件下收斂到的路由策略的平均排隊(duì)分組總數(shù)。不論負(fù)載條件如何變化，MLPI 算法找到的路由策略的平均排隊(duì)分組總數(shù)都顯著低于啟發(fā)式路由策略。在越重的負(fù)載條件下，MLPI 算法找到的路由策略相對(duì)于其他對(duì)比方案的平均排隊(duì)分組總數(shù)減少量越大。當(dāng)網(wǎng)絡(luò)負(fù)載為0.8 時(shí)，MLPI 算法相對(duì)于JSQ 和Po2 算法的平均排隊(duì)分組總數(shù)減少量分別約為38.3%和28.9%。

圖6 不同負(fù)載條件下的平均排隊(duì)分組總數(shù)

5.4.4 負(fù)載均衡的效果

在對(duì)不同路由算法的測(cè)試運(yùn)行中，記錄在每個(gè)時(shí)隙泊松到達(dá)事件之前的網(wǎng)絡(luò)狀態(tài)，且對(duì)所收集的狀態(tài)取平均來(lái)得到各路由算法下總體的排隊(duì)行為。如圖7 所示，每一個(gè)熱圖代表一個(gè)16×16 矩陣，其第ij個(gè)元素表示在某個(gè)階段中第i個(gè)交換機(jī)上的第j個(gè)隊(duì)列的平均排隊(duì)分組數(shù)。

圖7 的結(jié)果顯示，在第一個(gè)階段，在記錄狀態(tài)的時(shí)刻各隊(duì)列中沒(méi)有分組累積。在第二個(gè)階段，MC算法找到的路由策略導(dǎo)致了一些擁塞的隊(duì)列和不均衡的負(fù)載分布。在第三個(gè)階段，Po2 路由算法導(dǎo)致了顯著的負(fù)載不均衡，這是因?yàn)槠鋵㈥?duì)首分組路由到一些擁塞隊(duì)列中而讓其他隊(duì)列保持空載。這種對(duì)鏈路資源的欠利用降低了網(wǎng)絡(luò)吞吐量，導(dǎo)致分組滯留在網(wǎng)絡(luò)中。對(duì)比之下，MLPI 算法通過(guò)最大似然策略迭代學(xué)會(huì)了達(dá)到近乎理想的負(fù)載均衡狀態(tài)。

圖7 不同路由策略下各隊(duì)列的平均排隊(duì)分組數(shù)

強(qiáng)化學(xué)習(xí)算法如MC 或TD，需要與實(shí)際網(wǎng)絡(luò)進(jìn)行大量的交互并收集大量的試錯(cuò)數(shù)據(jù)，這會(huì)在訓(xùn)練過(guò)程中顯著損害網(wǎng)絡(luò)的延遲性能。MLPI 算法通過(guò)模擬的狀態(tài)轉(zhuǎn)移來(lái)學(xué)習(xí)路由策略，其訓(xùn)練過(guò)程不會(huì)對(duì)實(shí)際網(wǎng)絡(luò)的正常運(yùn)行產(chǎn)生干擾。由于集群網(wǎng)絡(luò)需要不間斷地為用戶提供低延遲的傳輸服務(wù)，MLPI算法是一種更加實(shí)用的路由策略學(xué)習(xí)方法。

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

本文提出最大似然策略迭代(MLPI)算法來(lái)求解多階段網(wǎng)絡(luò)分組路由問(wèn)題，MLPI 采用了高效的最大似然價(jià)值估計(jì)器來(lái)進(jìn)行策略評(píng)估。為了有效地改進(jìn)策略，MLPI 采用序列最小化的方法將復(fù)雜的組合優(yōu)化問(wèn)題分解為一系列簡(jiǎn)單的優(yōu)化子問(wèn)題進(jìn)行高效求解?；贜S-3 的實(shí)驗(yàn)證實(shí)相較于現(xiàn)有最優(yōu)的啟發(fā)式算法，MLPI 學(xué)習(xí)到的路由策略能將網(wǎng)絡(luò)中的平均排隊(duì)分組總數(shù)和平均分組延遲分別降低約21.1%和13.9%。