基于蒙特卡洛樹搜索算法實現(xiàn)軌道交通車輛多功能車輛總線周期調(diào)度表優(yōu)化

耿 力 耿 強

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

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

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

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

1 MVB周期信息通信原理

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

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

1.1.1 約束條件1

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

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

(1)

式中:

i——變量編號;

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部分,每個微周期中周期相所占時間最多為微周期的65%,即

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

(2)

式中:

j——微周期的編號;

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

Uj——第j個微周期中周期相所占時間,單位ms。

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

(3)

(4)

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

(5)

2 MCTS算法原理簡述

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

圖1 MCTS算法原理示意圖

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

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

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

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

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

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

(6)

式中:

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

R(v)——節(jié)點v獲得的累計獎勵;

N(v)——節(jié)點v的總訪問次數(shù);

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

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

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

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

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

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

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

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

3.2 獎勵規(guī)則設(shè)計

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

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

3.3 對搜索樹進行預(yù)剪枝優(yōu)化

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

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

3.4 設(shè)置變量優(yōu)先級

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

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

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

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

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

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

4.2 算法對比分析

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

表2 試驗用的變量及其周期

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

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

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

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

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

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

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

5 結(jié)語

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

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