耿 力 耿 強(qiáng)

(1.同濟(jì)大學(xué)鐵道與城市軌道交通研究院,201804,上海; 2.電子科技大學(xué)自動(dòng)化工程學(xué)院,611731,成都∥第一作者,碩士研究生)

軌道車(chē)輛通信總線由WTB(絞線式列車(chē)總線)和MVB(多功能車(chē)輛總線)構(gòu)成。其中:WTB主要用于日常作業(yè)時(shí)經(jīng)常改變編組數(shù)量的列車(chē)間連接各車(chē)輛的串行數(shù)據(jù)總線;MVB主要用于固定車(chē)廂或具有固定編組列車(chē)這一特定范圍的軌道車(chē)輛的通信網(wǎng)絡(luò)[1]。MVB將一個(gè)車(chē)廂內(nèi)或一個(gè)編組內(nèi)的可編程設(shè)備互連,并可直接連接簡(jiǎn)單的傳感器和執(zhí)行機(jī)構(gòu),從而為車(chē)廂內(nèi)各設(shè)備的諸多功能(如車(chē)門(mén)控制、列車(chē)制動(dòng)、空調(diào)調(diào)節(jié)、發(fā)布旅客信息及預(yù)留坐席等)的自動(dòng)實(shí)現(xiàn)、消息的傳達(dá)、資源的共享,以及各設(shè)備間的合理調(diào)配提供可靠且順暢的信息交換通道。在車(chē)輛上有眾多設(shè)備,設(shè)備之間對(duì)MVB的占用通過(guò)MVB周期調(diào)度表(以下簡(jiǎn)稱“調(diào)度表”)來(lái)控制。合理的調(diào)度表能提高M(jìn)VB的帶寬利用率,并通過(guò)縮短通信周期來(lái)提高車(chē)輛通信系統(tǒng)的實(shí)時(shí)性。

調(diào)度表的設(shè)計(jì)主要有兩種方案。方案一用經(jīng)典的RMS(單調(diào)速率調(diào)度)算法設(shè)計(jì)調(diào)度表,RMS算法的優(yōu)點(diǎn)是速度快,缺點(diǎn)是其調(diào)度表不具有負(fù)載均衡特性,易引起帶寬浪費(fèi),其通信的實(shí)時(shí)性也較低。方案二借助啟發(fā)式算法找出合理的調(diào)度順序。因?yàn)閷ふ邑?fù)載均衡的調(diào)度方式是一個(gè)NP-Hard(非確定性多項(xiàng)式困難)的組合優(yōu)化問(wèn)題,其組合方式隨變量的數(shù)目呈指數(shù)增長(zhǎng),例如針對(duì)20個(gè)變量的調(diào)度表設(shè)計(jì),普通的計(jì)算機(jī)已經(jīng)難以窮舉求解,通常采用啟發(fā)式算法求解。已提出用于調(diào)度表設(shè)計(jì)的啟發(fā)式算法包括GA(遺傳算法)[2]、混合遺傳算法[3]、免疫遺傳算法[4]、蟻群算法[5]及改進(jìn)的差分進(jìn)化算法[6]等,這些算法的相似度高,很多算法屬于對(duì)同一算法進(jìn)行了不同程度的改進(jìn),其缺點(diǎn)是搜索過(guò)程中可能產(chǎn)生大量效果很差的解,進(jìn)而造成搜索效率低。部分改進(jìn)過(guò)后的算法將搜索分成兩個(gè)階段進(jìn)行[6],第一階段為全局搜索,第二階段為局部搜索,這在一定程度上提高了搜索的效率,但也面臨如更多超參數(shù)等問(wèn)題。

基于強(qiáng)化學(xué)習(xí)的圍棋人工智能程序Alpha-Go采用MCTS(蒙特卡洛樹(shù)搜索)算法進(jìn)行啟發(fā)式搜索[7],該算法很好地解決了組合優(yōu)化問(wèn)題中搜索空間巨大、難以搜索到優(yōu)質(zhì)解這一難題。因此,本文嘗試將MCTS算法引入MVB調(diào)度表設(shè)計(jì)中,并針對(duì)MVB調(diào)度表的特點(diǎn)對(duì)該算法進(jìn)行改進(jìn),以提高搜索效率。

1 MVB周期信息通信原理

1.1 MVB調(diào)度表及約束條件

MVB上有多個(gè)節(jié)點(diǎn),主節(jié)點(diǎn)根據(jù)調(diào)度表的規(guī)則將特定的從設(shè)備指定為源節(jié)點(diǎn),賦予該源節(jié)點(diǎn)發(fā)送數(shù)據(jù)的能力。該調(diào)度過(guò)程不斷循環(huán),將每個(gè)循環(huán)周期稱為宏周期。為了能夠傳輸非周期信息,主節(jié)點(diǎn)將時(shí)間等分成若干個(gè)時(shí)間片,并將該時(shí)間片稱為微周期。每個(gè)微周期被劃分成兩部分,第一部分稱為周期相,用于傳輸周期性數(shù)據(jù);第二部分稱為偶發(fā)相,用于傳輸非周期性數(shù)據(jù)。國(guó)際電工委員會(huì)發(fā)布的IEC 61375標(biāo)準(zhǔn)第3-1部分對(duì)MVB調(diào)度表的宏周期及微周期中的周期相時(shí)間占比等條件進(jìn)行了約束。使用各種算法生成的調(diào)度表,需要檢查是否滿足規(guī)定的約束條件。若滿足約束條件,則稱該調(diào)度表是可調(diào)度的,否則稱該調(diào)度表是不可調(diào)度的。MVB的約束條件包括約束條件1及約束條件2。

1.1.1 約束條件1

約束條件1為變量首次出現(xiàn)位置必須不超過(guò)其周期,可形式化表示為

?i∈{1,2,…,m},pi≤Ti/Tbp

(1)

式中:

i——變量編號(hào);

m——變量總數(shù);

Tbp——微周期,單位ms;

pi——變量i首次出現(xiàn)的周期位置;

Ti——變量i的周期,單位ms。

1.1.2 約束條件2

約束條件2為根據(jù)IEC 61375標(biāo)準(zhǔn)第3-1部分,每個(gè)微周期中周期相所占時(shí)間最多為微周期的65%,即

?j∈{1,2,…,z},Uj≤0.65Tbp

(2)

式中:

j——微周期的編號(hào);

z——微周期總數(shù);

Uj——第j個(gè)微周期中周期相所占時(shí)間,單位ms。

1.2 優(yōu)化目標(biāo)

(3)

(4)

算法的優(yōu)化目標(biāo)轉(zhuǎn)為找到最佳的組合方式G*,使得σ(G)最小,即:

(5)

2 MCTS算法原理簡(jiǎn)述

本文首次將強(qiáng)化學(xué)習(xí)中的MCTS算法引入到MVB調(diào)度表的構(gòu)建過(guò)程中。MCTS算法是一種在決策空間進(jìn)行隨機(jī)采樣并構(gòu)建出一棵搜索樹(shù),通過(guò)搜索樹(shù)來(lái)實(shí)現(xiàn)尋找最優(yōu)決策的算法。MCTS算法在序列決策問(wèn)題、博弈問(wèn)題及規(guī)劃問(wèn)題中均具有重要的影響力,特別是在圍棋AI(人工智能)程序中的成功應(yīng)用,使得該算法備受關(guān)注。MCTS算法原理如圖1所示。

圖1 MCTS算法原理示意圖

如圖1所示,MCTS是一個(gè)不斷迭代的過(guò)程,每次迭代可分為4個(gè)步驟:

1) 步驟1:選擇。從根節(jié)點(diǎn)開(kāi)始,按照一定的策略遞歸向下伸展,直到抵達(dá)最需要擴(kuò)展的節(jié)點(diǎn)處。如果一個(gè)節(jié)點(diǎn)沒(méi)有到達(dá)終止?fàn)顟B(tài),并且還有未訪問(wèn)的子節(jié)點(diǎn),則該節(jié)點(diǎn)是可擴(kuò)展的。如圖1中的A節(jié)點(diǎn)。

2) 步驟2:擴(kuò)展。根據(jù)每個(gè)狀態(tài)可選擇的動(dòng)作,對(duì)選擇出的葉節(jié)點(diǎn)新增一個(gè)或多個(gè)子節(jié)點(diǎn),從而實(shí)現(xiàn)樹(shù)的擴(kuò)展。如圖1中的A節(jié)點(diǎn),可將其擴(kuò)展得到B節(jié)點(diǎn)。

3) 步驟3:模擬。將步驟2擴(kuò)展得到的新節(jié)點(diǎn)按照預(yù)定的方式進(jìn)行演算,進(jìn)而產(chǎn)生一個(gè)輸出結(jié)果,直至游戲結(jié)束。如對(duì)B節(jié)點(diǎn)進(jìn)行快速模擬時(shí),其每個(gè)動(dòng)作通常為隨機(jī)選擇。在游戲結(jié)束時(shí),根據(jù)游戲規(guī)則可獲得對(duì)應(yīng)的獎(jiǎng)勵(lì)。

4) 步驟4:回傳。將步驟3模擬后獲得的獎(jiǎng)勵(lì)回傳,更新執(zhí)行模擬節(jié)點(diǎn)及它的所有祖先節(jié)點(diǎn)的統(tǒng)計(jì)值。

在上述迭代過(guò)程中,步驟1中如何選擇合適的子節(jié)點(diǎn)是一個(gè)關(guān)鍵問(wèn)題,這也正是強(qiáng)化學(xué)習(xí)必須要面對(duì)的探索-利用困境。MCTS算法中使用了UCT(針對(duì)樹(shù)的置信上界)方法,以平衡探索和利用。通常選擇在UCT值最大的節(jié)點(diǎn)上進(jìn)行擴(kuò)展,其表達(dá)式為:

(6)

式中:

Q(v)——節(jié)點(diǎn)v的UCT值;

R(v)——節(jié)點(diǎn)v獲得的累計(jì)獎(jiǎng)勵(lì);

N(v)——節(jié)點(diǎn)v的總訪問(wèn)次數(shù);

pv——v的父節(jié)點(diǎn);

N(pv)——pv被訪問(wèn)的總次數(shù);

Cp——平衡探索與利用的常數(shù),本文取0.1。

式(6)等式的右邊為2項(xiàng)之和,其中:第1項(xiàng)表征了節(jié)點(diǎn)v平均獲得的獎(jiǎng)勵(lì);第2項(xiàng)中,在父節(jié)點(diǎn)pv多次被訪問(wèn)而某個(gè)子節(jié)點(diǎn)長(zhǎng)期未被訪問(wèn)時(shí),其對(duì)應(yīng)的N(v)較小,此時(shí)Q(v)較大,則節(jié)點(diǎn)v應(yīng)被訪問(wèn)。

3 MCTS算法在MVB調(diào)度表中的優(yōu)化

上文介紹了MCTS算法的通用框架,將其應(yīng)用于MVB調(diào)度表時(shí)需要進(jìn)行優(yōu)化設(shè)計(jì)。

3.1 狀態(tài)空間與動(dòng)作空間

MVB調(diào)度表的狀態(tài)為當(dāng)前變量的排布情況,其狀態(tài)采用各個(gè)變量首次出現(xiàn)的微周期序號(hào)形成的整數(shù)數(shù)組來(lái)表示,所有狀態(tài)的可能集合構(gòu)成狀態(tài)空間。不同的狀態(tài)可以執(zhí)行不同的動(dòng)作,即選出某個(gè)未安排的變量,將其排布在某一個(gè)微周期內(nèi),其所有可執(zhí)行的動(dòng)作將構(gòu)成動(dòng)作空間。所有變量均排布完畢后,動(dòng)作空間變?yōu)榭占?算法結(jié)束。

3.2 獎(jiǎng)勵(lì)規(guī)則設(shè)計(jì)

在強(qiáng)化學(xué)習(xí)中,智能體的目標(biāo)是獲得盡可能多的獎(jiǎng)勵(lì)。根據(jù)MVB變量調(diào)度的過(guò)程,提出將當(dāng)前調(diào)度表的均衡程度與歷史數(shù)據(jù)進(jìn)行對(duì)比,根據(jù)“進(jìn)步”程度給出獎(jiǎng)勵(lì)。其獎(jiǎng)勵(lì)規(guī)則如表1所示。

表1 MVB調(diào)度表中MTCS算法的獎(jiǎng)勵(lì)規(guī)則

3.3 對(duì)搜索樹(shù)進(jìn)行預(yù)剪枝優(yōu)化

在變量排布過(guò)程中,應(yīng)遵循上文所述的MVB調(diào)度表約束條件。通常情況下,約束條件2很容易滿足,因此在算法實(shí)現(xiàn)中應(yīng)先考慮約束條件1,待得到一個(gè)較好的解時(shí),再檢查是否滿足約束條件2。約束條件1能過(guò)濾掉大量不滿足要求的劣質(zhì)解。例如,仿真時(shí)選取20個(gè)變量及32個(gè)微周期工況,在無(wú)任何約束時(shí)調(diào)度表的組合數(shù)為2032(即4.3×1041),而滿足約束條件1的組合數(shù)約為5.8×1017,即只有大約1/1024的組合能夠滿足約束條件1。

因此,針對(duì)MCTS算法和約束條件1,本文設(shè)計(jì)的預(yù)剪枝規(guī)則為:如果某個(gè)狀態(tài)對(duì)應(yīng)的調(diào)度表不可調(diào)度,則將其標(biāo)記為不合法節(jié)點(diǎn),以后不再對(duì)該不合法節(jié)點(diǎn)進(jìn)行任何的擴(kuò)展或模擬,以避免大量不必要的搜索。

3.4 設(shè)置變量?jī)?yōu)先級(jí)

變量?jī)?yōu)先級(jí)的設(shè)計(jì)對(duì)提高M(jìn)VB的均衡度有一定的影響。如果最后安排的變量傳輸時(shí)間很長(zhǎng),則該變量的排布很可能導(dǎo)致整個(gè)調(diào)度表不均衡,試驗(yàn)中也驗(yàn)證了此結(jié)論的正確性。因此,優(yōu)先級(jí)規(guī)則設(shè)定為:變量傳輸時(shí)間越長(zhǎng),此變量的優(yōu)先級(jí)越高。

4 仿真試驗(yàn)及結(jié)果分析

選取RMS算法、MCTS算法和GA三種算法進(jìn)行仿真試驗(yàn),并對(duì)各算法的結(jié)果進(jìn)行對(duì)比分析。其中GA的形式隨具體應(yīng)用場(chǎng)景的改變而略有差異,因此先簡(jiǎn)要介紹一下本文使用的GA形式,再進(jìn)行算法對(duì)比。

4.1 用于MVB調(diào)度表的GA

GA是一種經(jīng)典的啟發(fā)式搜索算法,其流程如圖2所示。該算法對(duì)個(gè)體的編碼方法和上文所述MCTS算法的編碼方法一致,即一個(gè)編碼中包含了各個(gè)變量首次出現(xiàn)的位置,編碼長(zhǎng)度等于變量總數(shù)m。初始化種群中個(gè)體數(shù)量為記作Np,每輪更新中將每個(gè)個(gè)體變異。變異方式為取隨機(jī)編碼中的一個(gè)變量,將其隨機(jī)放到一個(gè)微周期內(nèi)。如果變異后的新個(gè)體適應(yīng)度大于其父親的適應(yīng)度,則新個(gè)體代替父親,否則保留父親不變,丟棄新個(gè)體。

對(duì)GA而言,適應(yīng)度越大說(shuō)明其對(duì)應(yīng)的MVB負(fù)載越均衡,因此采用式(3)標(biāo)準(zhǔn)差的相反數(shù)(即-σ(G))作為該算法的適應(yīng)度。將種群中每個(gè)個(gè)體都變異一次叫做一次種群變異,試驗(yàn)中種群變異次數(shù)記為NGA。

4.2 算法對(duì)比分析

定義ti為第i個(gè)變量在1個(gè)微周期中占用MVB時(shí)間。使用文獻(xiàn)[6]中使用的算例數(shù)據(jù),其調(diào)度表包含20個(gè)變量及32個(gè)微周期,各變量對(duì)應(yīng)的周期數(shù)據(jù)如表2所示。

表2 試驗(yàn)用的變量及其周期

本文使用Python編程實(shí)現(xiàn)RMS算法、GA和MCTS算法,硬件采用普通的筆記本電腦,其參數(shù)分別為: CPU(中央處理器)的型號(hào)為i5-8265U,1.60 GHz主頻,RAM(隨機(jī)存取存儲(chǔ)器)的容量為12 GiB。為便于比較GA和MCTS算法,試驗(yàn)中將這兩種算法的一次試驗(yàn)運(yùn)行時(shí)間均設(shè)定為180 min(即10 800 s)。GA一次試驗(yàn)的Np=100個(gè),NGA=5 000萬(wàn)次。MCTS算法一次試驗(yàn)的最大采樣次數(shù)NMCTS=1 500萬(wàn)次。RMS算法具有確定性,但GA和MCTS算法具有一定的隨機(jī)性。為了避免單次試驗(yàn)引起的誤差,將三種算法均重復(fù)運(yùn)行10次。試驗(yàn)中發(fā)現(xiàn)GA和MCTS算法難以收斂,隨著時(shí)間的推移,這兩種算法可能以一定概率獲得一個(gè)更優(yōu)的解。因此,不通過(guò)最終的收斂而通過(guò)一段較長(zhǎng)時(shí)間內(nèi)的搜索結(jié)果來(lái)評(píng)估GA和MCTS算法的好壞。表3給出了三種算法10次試驗(yàn)后的試驗(yàn)平均運(yùn)行時(shí)間、平均均衡度及最優(yōu)解。最優(yōu)解用一個(gè)向量表達(dá),其元素?cái)?shù)等于m,向量的第i個(gè)值(記作pi)表示第i個(gè)變量首次出現(xiàn)安排在第pi個(gè)微周期。

表3 三種算法的最優(yōu)搜索結(jié)果對(duì)比

試驗(yàn)驗(yàn)證可知:表3中各個(gè)算法給出的最優(yōu)解均滿足約束條件1和約束條件2,即獲得的調(diào)度方式是可調(diào)度的。由表3中還可以看出:RMS算法下一次試驗(yàn)的平均運(yùn)行時(shí)間最小,但均衡度最差。在長(zhǎng)時(shí)間搜索下,MCTS算法的搜索效率較GA高,其均衡度在三個(gè)算法中最小。

圖3直觀展示了RMS算法、GA和MCTS算法三種算法生成的最優(yōu)調(diào)度表每個(gè)微周期內(nèi)周期相占用時(shí)間分布情況。由圖3可知:RMS算法生成的調(diào)度表負(fù)載嚴(yán)重不均衡;GA算法生成的調(diào)度表均衡度較好;MCTS生成的調(diào)度表負(fù)載最均衡。

圖3 三種算法生成的最優(yōu)調(diào)度表周期相占用時(shí)間分布

圖4展示了GA和MCTS算法下均衡度隨試驗(yàn)運(yùn)行時(shí)間的變化規(guī)律,帶方塊的黑色虛線和帶三角的黑色實(shí)線分別對(duì)應(yīng)運(yùn)行10次后GA和MCTS算法的平均均衡度,對(duì)應(yīng)的填充區(qū)域?yàn)?0次運(yùn)行中以最大值和最小值為邊界圍成的區(qū)域,邊界線的階梯下降表明找到了均衡度更小的解。隨著試驗(yàn)運(yùn)行時(shí)間的增加,均衡度均值曲線趨于平緩,這是因?yàn)橐腋鼉?yōu)的解已變得困難。相較于GA,MCTS算法生成的調(diào)度表對(duì)應(yīng)的均衡度曲線下降速率更快,即在相同的試驗(yàn)運(yùn)行時(shí)間內(nèi)MCTS算法能找到更好的解。

無(wú)論是GA還是MCTS算法,均會(huì)使用式(3)衡量生成的每個(gè)解的優(yōu)劣程度。MCTS算法能統(tǒng)計(jì)產(chǎn)生各個(gè)解是否比歷史解更優(yōu)等信息,并將這些信息通過(guò)回傳(步驟4)存儲(chǔ)于祖先節(jié)點(diǎn)內(nèi),用以指導(dǎo)后續(xù)解的生成。也就是說(shuō),MCTS算法中每個(gè)新解的生成都參考了歷史所有解的信息。相較之下,GA盡管不斷通過(guò)優(yōu)勝劣汰機(jī)制來(lái)清除劣質(zhì)解,但每個(gè)解的生成僅參考了一個(gè)父節(jié)點(diǎn)的信息進(jìn)行變異,而不是全局信息。這也許是GA搜索效率不如MCTS算法的原因。此外,MCTS算法還可以通過(guò)設(shè)置變量?jī)?yōu)先級(jí)來(lái)提高算法效果,而GA只能隨機(jī)變異。MCTS算法的缺點(diǎn)是需要較大內(nèi)存,用以記錄樹(shù)生成過(guò)程中的大量節(jié)點(diǎn)。

5 結(jié)語(yǔ)

設(shè)計(jì)負(fù)載均衡的MVB調(diào)度表可減少帶寬浪費(fèi),并可提高網(wǎng)絡(luò)通信的實(shí)時(shí)性。本文首次利用強(qiáng)化學(xué)習(xí)中的MCTS算法實(shí)現(xiàn)MVB調(diào)度表的優(yōu)化設(shè)計(jì),通過(guò)設(shè)計(jì)獎(jiǎng)勵(lì)方式及博弈規(guī)則,將MVB周期數(shù)據(jù)調(diào)度問(wèn)題轉(zhuǎn)換成可以用MCTS算法解決的組合優(yōu)化問(wèn)題。

另外,本文根據(jù)MVB調(diào)度表的特征實(shí)現(xiàn)了預(yù)剪枝策略,當(dāng)MVB變量總數(shù)為20個(gè)時(shí),可將搜索空間減少數(shù)十個(gè)數(shù)量級(jí),使其搜索效率優(yōu)于GA。仿真結(jié)果表明:本文優(yōu)化后的MCTS算法能在相同的搜索時(shí)間內(nèi)獲得更均衡的解。如果車(chē)輛通信設(shè)備增加,需要生成包含更多變量的調(diào)度表時(shí),MCTS算法更能凸顯其搜索優(yōu)勢(shì)。未來(lái)可進(jìn)一步設(shè)計(jì)出不同的探索-利用平衡方案,進(jìn)一步提高M(jìn)CTS算法的搜索效果,以期更快設(shè)計(jì)出負(fù)載均衡的MVB調(diào)度表。本文給出的設(shè)計(jì)思路可為通過(guò)MCTS算法求解其他領(lǐng)域的組合優(yōu)化問(wèn)題提供參考。