基于強(qiáng)化學(xué)習(xí)的戰(zhàn)時(shí)保障力量調(diào)度策略研究

曾 斌, 王 睿, 李厚樸, 樊 旭

(1. 海軍工程大學(xué)管理工程與裝備經(jīng)濟(jì)系, 湖北 武漢 430033; 2. 海軍工程大學(xué)教研保障中心, 湖北 武漢 430033; 3. 海軍工程大學(xué)導(dǎo)航工程系, 湖北 武漢 430033)

0 引 言

當(dāng)前智能技術(shù)的迅猛發(fā)展以及在軍事領(lǐng)域的廣泛應(yīng)用,加速了戰(zhàn)爭形態(tài)從信息化向智能化演變,并在諸如自動(dòng)目標(biāo)識(shí)別等方面去得了較大進(jìn)展,同時(shí)戰(zhàn)爭的智能化也必然需要后裝保障的智能化。

戰(zhàn)時(shí)保障力量可看作由多個(gè)保障分隊(duì)組成,當(dāng)保障區(qū)域(作戰(zhàn)地點(diǎn))發(fā)出保障申請(qǐng)時(shí),基地保障調(diào)度系統(tǒng)需要按照某種策略,決定分派具體保障分隊(duì)完成該次申請(qǐng)或者暫時(shí)不分派。當(dāng)戰(zhàn)況激烈時(shí),保障申請(qǐng)發(fā)生率較高,所有保障分隊(duì)可能處于繁忙狀態(tài),這時(shí)優(yōu)化的調(diào)度策略則尤為重要,它可以取得較高的性能指標(biāo),比如總體響應(yīng)時(shí)間更短、高優(yōu)先級(jí)申請(qǐng)能及時(shí)得到保障服務(wù)等。當(dāng)前保障調(diào)度領(lǐng)域的研究可分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度兩種,靜態(tài)調(diào)度只考慮當(dāng)前時(shí)刻的調(diào)度方案,可能在當(dāng)前時(shí)刻最優(yōu),但全時(shí)域做不到最優(yōu)。動(dòng)態(tài)調(diào)度需要考慮不斷出現(xiàn)新保障申請(qǐng)的情況,又可分為兩種:無預(yù)測(cè)性的動(dòng)態(tài)調(diào)度和有預(yù)測(cè)性的動(dòng)態(tài)調(diào)度。當(dāng)新的保障申請(qǐng)出現(xiàn)時(shí),無預(yù)測(cè)性的動(dòng)態(tài)調(diào)度只能被動(dòng)的調(diào)整原調(diào)度方案,由于原保障方案沒有預(yù)測(cè)性,這種調(diào)整可能會(huì)導(dǎo)致較大開銷；預(yù)測(cè)性的動(dòng)態(tài)調(diào)度在設(shè)計(jì)當(dāng)前調(diào)度方案時(shí)就考慮了后面可能出現(xiàn)的情況。

相關(guān)研究包括:基于啟發(fā)式算法的裝備維修任務(wù)分配和基于優(yōu)先級(jí)的保障力量調(diào)度分別利用遺傳算法解決了維修任務(wù)-維修單元的指派,但假設(shè)在調(diào)度前已知各項(xiàng)保障任務(wù)的優(yōu)先級(jí)、位置等屬性,則屬于靜態(tài)調(diào)度?？紤]不確定因素影響的保障任務(wù)調(diào)度利用混合Petri網(wǎng)建立了流程模型并提出了基于退火進(jìn)化的保障單元調(diào)度算法,雖然考慮了保障任務(wù)執(zhí)行時(shí)間的不確定性,但仍然屬于靜態(tài)調(diào)度。多目標(biāo)動(dòng)態(tài)調(diào)度研究了保障任務(wù)動(dòng)態(tài)增加時(shí),如何減少調(diào)度方案的重新調(diào)整次數(shù)和開銷,但每次重調(diào)度還是會(huì)不可避免地打斷現(xiàn)行任務(wù)執(zhí)行,影響全局保障效能,屬于無預(yù)測(cè)的動(dòng)態(tài)調(diào)度。巡回維修任務(wù)調(diào)度策略研究問題與本文類似,并通過仿真得出預(yù)測(cè)性調(diào)度策略性能高于就近策略,但以裝備故障率來預(yù)測(cè)保障需求到達(dá)時(shí)間,不適用于戰(zhàn)時(shí)情況。

現(xiàn)有相關(guān)研究在數(shù)學(xué)上可歸類于車間調(diào)度問題(job shop scheduling, JSP)或項(xiàng)目資源調(diào)度問題,適合于伴隨保障或保障范圍不大的情況。但當(dāng)需要實(shí)施大范圍的基地級(jí)保障時(shí),例如分布式作戰(zhàn),相較于伴隨保障,保障分隊(duì)和待保障部隊(duì)數(shù)量有限,雖然不需要類似遺傳算法的規(guī)劃方法尋優(yōu),但各作戰(zhàn)地點(diǎn)相距較遠(yuǎn),保障分隊(duì)經(jīng)常處于忙碌狀態(tài),這時(shí)調(diào)度策略中的任務(wù)分派方案則尤為重要。例如,假設(shè)當(dāng)前某區(qū)域發(fā)出保障申請(qǐng),沒有預(yù)測(cè)能力的調(diào)度策略會(huì)分派給基地空閑的保障分隊(duì)執(zhí)行該次任務(wù),但如果下一時(shí)間該基地附近出現(xiàn)了優(yōu)先級(jí)更高的保障申請(qǐng),就近的維修分隊(duì)卻都已分派出去,就會(huì)導(dǎo)致當(dāng)前保障工作失敗。而優(yōu)化的調(diào)度策略,能夠根據(jù)歷史數(shù)據(jù)學(xué)習(xí)經(jīng)驗(yàn),預(yù)測(cè)到可能出現(xiàn)的高優(yōu)先級(jí)保障申請(qǐng),從長遠(yuǎn)回報(bào)考慮,暫時(shí)保留附近空閑的保障分隊(duì)。因此迫切需要具有時(shí)間維度動(dòng)態(tài)預(yù)測(cè)能力的調(diào)度策略提供支持。

作為序貫決策的關(guān)鍵技術(shù)之一,以馬爾可夫決策過程(Markov decision process,MDP)為基礎(chǔ)結(jié)構(gòu)的強(qiáng)化學(xué)習(xí)逐漸在智能化應(yīng)急服務(wù)中得到了應(yīng)用并取得顯著成果,這些應(yīng)急服務(wù)包括:救護(hù)車的調(diào)度、醫(yī)療資源的分配、災(zāi)后救援優(yōu)化策略、戰(zhàn)場(chǎng)傷員的疏散方案、應(yīng)急電力系統(tǒng)的自適應(yīng)控制等。但尚未發(fā)現(xiàn)強(qiáng)化學(xué)習(xí)在后裝保障方面的應(yīng)用研究。

本文提出了基于MDP模型的戰(zhàn)時(shí)預(yù)測(cè)性保障調(diào)度策略,并針對(duì)保障調(diào)度MDP模型中的不確定性、計(jì)算復(fù)雜性和維度災(zāi)問題,分別采用了蒙特卡羅模擬、決策后狀態(tài)變量和基于基函數(shù)的近似函數(shù)來解決,最后通過仿真對(duì)調(diào)度策略的有效性和性能進(jìn)行了驗(yàn)證。

1 技術(shù)路線

圖1為本文的解決思路,強(qiáng)化學(xué)習(xí)的第一步是構(gòu)造問題的MDP模型,為此論文首先建立了MDP的要素。狀態(tài):刻畫當(dāng)前保障過程的運(yùn)行狀態(tài);動(dòng)作:表示保障力量與戰(zhàn)場(chǎng)環(huán)境交互所采取的行動(dòng);獎(jiǎng)勵(lì):保障力量采取行動(dòng)而從戰(zhàn)場(chǎng)環(huán)境中獲得的正面或負(fù)面的強(qiáng)化評(píng)價(jià);調(diào)度策略:保障力量調(diào)度系統(tǒng)的核心,由于其計(jì)算復(fù)雜度過大,本文用基于基函數(shù)集的近似函數(shù)表示,輸入為當(dāng)前狀態(tài),輸出為最佳行動(dòng)及對(duì)應(yīng)的預(yù)測(cè)價(jià)值;戰(zhàn)場(chǎng)環(huán)境:表示與保障調(diào)度交互的現(xiàn)實(shí)環(huán)境。

圖1 調(diào)度策略強(qiáng)化學(xué)習(xí)流程圖Fig.1 Flow chart of scheduling policy reinforcement learning

強(qiáng)化學(xué)習(xí)時(shí)假設(shè)戰(zhàn)場(chǎng)環(huán)境處于一個(gè)特定的狀態(tài),當(dāng)采取動(dòng)作時(shí),會(huì)變?yōu)闋顟B(tài)′。對(duì)于這個(gè)特定的動(dòng)作,在環(huán)境中觀察到的即時(shí)獎(jiǎng)勵(lì)是,該過程不斷反復(fù),直到循環(huán)終止,得到的總回報(bào)為累積獎(jiǎng)勵(lì),調(diào)度策略需要能夠從所有可能的動(dòng)作中估計(jì)哪一個(gè)動(dòng)作將帶來最大的回報(bào)。因此第二步是訓(xùn)練代表調(diào)度策略的近似函數(shù),即估計(jì)其權(quán)重參數(shù),通過不斷迭代更新,最小化最終預(yù)測(cè)的狀態(tài)價(jià)值與觀察到的狀態(tài)價(jià)值的誤差。最后訓(xùn)練完畢的近似函數(shù)代表預(yù)測(cè)性調(diào)度策略。

2 馬爾可夫決策過程模型

MDP包含5個(gè)模型要素,狀態(tài)(state)、動(dòng)作(action)、策略(policy)、獎(jiǎng)勵(lì)(reward)和回報(bào)(return)。

2.1 過程狀態(tài)

當(dāng)發(fā)生事件時(shí),保障調(diào)度系統(tǒng)需要進(jìn)行決策,設(shè)={1,2,…}表示決策時(shí)刻集合,∈表示決策時(shí)刻。事件包括2種類型:① 作戰(zhàn)部隊(duì)發(fā)出保障申請(qǐng);② 保障分隊(duì)完成當(dāng)前保障工作,由忙到閑。時(shí)刻的系統(tǒng)狀態(tài)由以下復(fù)合四元組表示,=(,,,)。其中表示決策時(shí)刻所處的當(dāng)前系統(tǒng)時(shí)間,用時(shí)間變量表示;表示時(shí)刻多個(gè)保障分隊(duì)狀態(tài),用6元組列表表示;表示保障申請(qǐng)隊(duì)列狀態(tài),用四元組列表表示;表示當(dāng)前保障申請(qǐng)狀態(tài),用三元組表示。下面進(jìn)一步描述系統(tǒng)狀態(tài)的各個(gè)組成元素。

設(shè)′={1,2,…,|′|}表示保障分隊(duì)集合,則可表示為各個(gè)保障分隊(duì)狀態(tài):

=[]∈ ′=[1,2,…,| ′|]

其中某一個(gè)保障分隊(duì)的狀態(tài)由以下六元組表示:

設(shè)′={1,2,…,|′|}表示保障申請(qǐng)隊(duì)列,則可表示為隊(duì)列中各個(gè)保障申請(qǐng)狀態(tài):

=[]∈′=[1,2,…,|′|]

其中某一個(gè)保障申請(qǐng)的狀態(tài)由以下四元組表示:

如果時(shí)刻隊(duì)列為空時(shí),=(0,0,0,0)。出隊(duì)列規(guī)則為:首先按優(yōu)先級(jí)出隊(duì)列,當(dāng)優(yōu)先級(jí)相同時(shí),按入隊(duì)時(shí)間出隊(duì)。

根據(jù)戰(zhàn)時(shí)保障要求,建立了保障申請(qǐng)的準(zhǔn)入控制機(jī)制,設(shè)計(jì)了當(dāng)前申請(qǐng)狀態(tài)元組,如果當(dāng)前保障申請(qǐng)的狀態(tài)特征不滿足保障分隊(duì)出動(dòng)規(guī)則,可以不允許其進(jìn)入隊(duì)列或轉(zhuǎn)移該申請(qǐng)至其他機(jī)構(gòu)。當(dāng)前保障申請(qǐng)狀態(tài)由以下三元組表示:

2.2 決策動(dòng)作

(1)

式中：() 為指示函數(shù),當(dāng)=(0,0,0)時(shí)表示當(dāng)前沒有保障申請(qǐng),這時(shí)()=0;否則,即≠(0,0,0)時(shí),()=1。

第2個(gè)決策約束用下式表示:

(2)

該約束表示如果已經(jīng)拒絕了當(dāng)前保障申請(qǐng),則不再分派保障分隊(duì)處理;如果接受當(dāng)前申請(qǐng),最多派遣一支保障分隊(duì)處理。

為了描述所有可行的決策動(dòng)作,再增設(shè)兩個(gè)指示函數(shù),如果()≠,即存在可用保障分隊(duì)時(shí),()=1,否則()=0。如果|′|≠0,即申請(qǐng)隊(duì)列不為空時(shí),()=1,否則()=0。并設(shè)申請(qǐng)隊(duì)列的最大長度為,則調(diào)度過程所有可行決策可表示如下:

(3)

2.3 立即獎(jiǎng)勵(lì)

影響調(diào)度獎(jiǎng)勵(lì)的因素可以歸納為4種,分別為:發(fā)出保障申請(qǐng)的作戰(zhàn)部隊(duì)位置、該申請(qǐng)的工作量、該申請(qǐng)的優(yōu)先級(jí)以及保障分隊(duì)所處的位置。為此獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)如下:

(4)

2.4 最優(yōu)決策函數(shù)

設(shè)()為決策函數(shù),表示當(dāng)系統(tǒng)處于狀態(tài)時(shí),在給定策略的情況下返回的動(dòng)作為。本文馬爾可夫決策過程的目標(biāo)就是找到最優(yōu)策略,最大化整個(gè)保障系統(tǒng)的總回報(bào),所以模型的目標(biāo)可用下式表示:

式中：∈[0,1)為折扣因子,是一個(gè)固定常數(shù),用來計(jì)算累積獎(jiǎng)勵(lì)。最優(yōu)策略可以用Bellman迭代方程計(jì)算得到:

(5)

式中：()為價(jià)值函數(shù);(,)為第22節(jié)所述獎(jiǎng)勵(lì)函數(shù)；(+1|,)為在當(dāng)前時(shí)刻處于狀態(tài)時(shí),采取第32節(jié)所述動(dòng)作后進(jìn)入狀態(tài)+1的價(jià)值。因?yàn)閯?dòng)作可以有多個(gè),所以狀態(tài)價(jià)值是根據(jù)轉(zhuǎn)移概率計(jì)算的平均回報(bào),利用期望值形式E[(+1|,)]表示。

3 近似求解算法

求解保障調(diào)度MDP模型,即對(duì)式(5)進(jìn)行計(jì)算,面臨兩個(gè)難點(diǎn)。第1個(gè)難點(diǎn)是:對(duì)于式(5),如何計(jì)算期望值E[(+1|,)]的最大值。如果采取精確算法,則需要遍歷下一決策時(shí)刻的各個(gè)狀態(tài);如果采用近似算法,則需要通過仿真來估計(jì)期望值,兩種方式不僅都會(huì)帶來巨大的計(jì)算量,而且會(huì)導(dǎo)致統(tǒng)計(jì)誤差,即出現(xiàn)信息空間的維度災(zāi)難。針對(duì)該難點(diǎn),本文在后文設(shè)計(jì)了決策后狀態(tài)變量來解決。

如上文分析,系統(tǒng)狀態(tài)空間過大,這時(shí)無法用常規(guī)表結(jié)構(gòu)來表示價(jià)值量,這是求解式(4)的第2個(gè)難點(diǎn),為此需要用一個(gè)函數(shù)來估計(jì)值函數(shù),稱之為價(jià)值函數(shù)的逼近或近似。

3.1 決策后狀態(tài)變量的設(shè)計(jì)

決策后狀態(tài)變量用于描述處于決策動(dòng)作發(fā)生之后和外部隨機(jī)事件(保障分隊(duì)完成任務(wù)或出現(xiàn)保障申請(qǐng))到達(dá)之前的系統(tǒng)狀態(tài),它將原來只用一步的狀態(tài)轉(zhuǎn)移函數(shù)+1=(,)分成兩步:

圖2 階段3的決策前和決策后狀態(tài)關(guān)系Fig.2 Relationship between pre-decision and post-decision states of stages 3

(6)

同理可得

(7)

把式(7)代入式(5),決策前狀態(tài)的價(jià)值可由下式計(jì)算:

(8)

(9)

式(5)需要計(jì)算期望值的極值,而式(9)是先計(jì)算極大值再計(jì)算期望值,這屬于確定性優(yōu)化問題,可以用迭代方法計(jì)算。

盡管通過引入決策后狀態(tài)變量,式(9)把模型(5)的不確定性問題轉(zhuǎn)換為確定性優(yōu)化問題,但狀態(tài)空間過大的問題仍然存在,這需要利用近似函數(shù)解決。

3.2 近似函數(shù)的框架設(shè)計(jì)

當(dāng)前強(qiáng)化學(xué)習(xí)中,為了解決大型狀態(tài)空間以及連續(xù)狀態(tài)問題,較為有效的方法是利用基函數(shù)集來近似價(jià)值函數(shù),這種方法的關(guān)鍵技術(shù)是如何選取識(shí)別MDP中的基函數(shù)和特征量,在本文中它直接影響了能否得到高質(zhì)量的調(diào)度策略。

本文設(shè)計(jì)了8類基函數(shù)來捕捉保障系統(tǒng)的調(diào)度特征。第1類基函數(shù)用來描述保障分隊(duì)的可用性,數(shù)量為|′|個(gè),函數(shù)表達(dá)式如下:

中國特色社會(huì)主義道路、中國特色社會(huì)主義理論體系以及中國特色社會(huì)主義制度，三者是內(nèi)在的統(tǒng)一，從實(shí)踐、理論和制度不同維度闡釋了中國特色社會(huì)主義。對(duì)此，十八大報(bào)告強(qiáng)調(diào)指出：高舉中國特色社會(huì)主義偉大旗幟，最根本的就是要倍加珍惜、始終堅(jiān)持、不斷發(fā)展中國特色社會(huì)主義道路、中國特色社會(huì)主義理論體系以及中國特色社會(huì)主義制度。

第2～第5類基函數(shù)捕捉保障分隊(duì)處理保障申請(qǐng)的服務(wù)質(zhì)量。第2類基函數(shù)數(shù)量為|′|個(gè),反映了保障分隊(duì)的響應(yīng)速度,用下式表示:

第3類基函數(shù)數(shù)量為|′|個(gè),反映了保障分隊(duì)的期望保障時(shí)間,用下式表示:

第4類基函數(shù)數(shù)量為|′|個(gè),反映了保障分隊(duì)處理申請(qǐng)的優(yōu)先級(jí),用下式表示:

第5類基函數(shù)數(shù)量為|′|個(gè),反映了保障分隊(duì)的服務(wù)工作量,用下式表示:

最后3類基函數(shù)用于捕捉申請(qǐng)隊(duì)列的處理特征。當(dāng)?shù)趥€(gè)保障分隊(duì)分派處理隊(duì)列中第個(gè)申請(qǐng)時(shí),第6類基函數(shù)反映了期望總保障時(shí)間,包括等待時(shí)間(在隊(duì)列中等待的時(shí)間)、路上運(yùn)輸時(shí)間和服務(wù)時(shí)間(故障設(shè)備的維修時(shí)間或物質(zhì)的卸貨時(shí)間),數(shù)量為|′|(|′|,用下式表示:

式中：表示第個(gè)保障分隊(duì)分派處理隊(duì)列中第個(gè)申請(qǐng)時(shí)所花費(fèi)的總時(shí)間。

第7類基函數(shù)反映了隊(duì)列中每一個(gè)等待的申請(qǐng)的優(yōu)先級(jí),它數(shù)量為|′|,用下式表示:

第8類基函數(shù)隊(duì)列中每一個(gè)處于等待狀態(tài)的申請(qǐng)所需工作量,它數(shù)量為|′|,用下式表示:

(10)

3.3 近似函數(shù)的訓(xùn)練

當(dāng)確定了基函數(shù)集結(jié)構(gòu)后,只需要計(jì)算出權(quán)重矢量,就可以得到近似價(jià)值函數(shù)。作為當(dāng)前主流強(qiáng)化學(xué)習(xí)求解算法,時(shí)序差分法可以快速靈活的更新狀態(tài)的價(jià)值估計(jì),方差較低,且對(duì)初始值敏感,所以本文采用基于時(shí)序差分的策略迭代算法,流程圖如圖3所示。

圖3 基于時(shí)序差分的策略迭代算法流程圖Fig.3 Flow chart policy iteration algorithm based on time difference

()=+-

(11)

為了避免策略評(píng)估迭代中采集的差分樣本值出現(xiàn)過擬合現(xiàn)象,本文采用嶺回歸來減小泛化誤差。設(shè)代價(jià)函數(shù)為時(shí)序差分值的平方,即(),基于嶺回歸的更新算法主要步驟如下。

利用嶺回歸法按下式計(jì)算估計(jì)值。

設(shè)計(jì)多項(xiàng)式步長按下式平滑估計(jì)值。

按下式更新θ值。

(12)

的更新算法中步驟1的公式為標(biāo)準(zhǔn)嶺回歸公式,是正則化項(xiàng),是單位矩陣。

步驟2中設(shè)計(jì)步長的目的是加快算法的收斂速度,的下標(biāo)值與策略改進(jìn)迭代次數(shù)一致,表示隨著策略改進(jìn)迭代次數(shù)的增加,減小的速度取決于,較小的值能夠減緩減小速度。

算法中、、和都屬于超參數(shù),其中為策略改進(jìn)迭代閾值,是策略評(píng)估迭代閾值,是嶺回歸的正則化項(xiàng),是步長參數(shù)。

圖3中步驟21采用貪婪法決定通過探索或利用確定動(dòng)作,有的概率選擇探索方式,即按式(3)在可行決策集中隨機(jī)生成新的動(dòng)作作為下一步;有1-的概率選用利用方式,選擇當(dāng)前已產(chǎn)生的最佳動(dòng)作為作為下一步,本文根據(jù)文獻(xiàn)[30]自適應(yīng)調(diào)整的值,在迭代前期值較大,允許更多的探索,后期值逐步減小,盡量使用已收斂的優(yōu)化決策。

3.4 蒙特卡羅模擬

蒙特卡羅模擬主要用于兩個(gè)方面,一是用于策略迭代算法的狀態(tài)演進(jìn),在迭代算法的步驟23中,當(dāng)系統(tǒng)處于決策后狀態(tài)時(shí),需要通過蒙特卡羅模擬產(chǎn)生的事件表往前推進(jìn)。二是用于性能比較,在蒙特卡羅模擬上進(jìn)行仿真,可以比較強(qiáng)化學(xué)習(xí)分派策略與就近分派策略在不同想定下的性能。

保障申請(qǐng)出現(xiàn)和保障完成這兩個(gè)事件,促進(jìn)了保障系統(tǒng)狀態(tài)的變化。本文使用泊松分布生成保障需求的產(chǎn)生概率(事件發(fā)生率),為了能夠接近實(shí)戰(zhàn)背景,泊松分布的發(fā)生率由下式生成:

=

(13)

式中：為保障申請(qǐng)到達(dá)率;為條件概率,表示當(dāng)發(fā)生保障申請(qǐng)時(shí),該申請(qǐng)是從作戰(zhàn)區(qū)域發(fā)出的概率;為條件概率,表示當(dāng)出現(xiàn)保障申請(qǐng)且該申請(qǐng)從作戰(zhàn)區(qū)域發(fā)出時(shí),該申請(qǐng)優(yōu)先級(jí)為的概率。、和需要保障指揮員給定。

為了生成保障完成事件,其服務(wù)率為,表示保障分隊(duì)為作戰(zhàn)部隊(duì)的保障時(shí)間,該服務(wù)率由保障指揮人員通過參數(shù)估計(jì)方法給定,應(yīng)該能捕捉保障分隊(duì)從基地出發(fā)到申請(qǐng)點(diǎn)并完成保障的總時(shí)長。

3.5 調(diào)度步驟

建立的近似函數(shù)可以看作一個(gè)具有預(yù)測(cè)能力的調(diào)度機(jī)。其使用時(shí)機(jī)為:當(dāng)戰(zhàn)場(chǎng)態(tài)勢(shì)變化,例如出現(xiàn)新的保障申請(qǐng),如第21節(jié)描述的當(dāng)前系統(tǒng)狀態(tài)隨之改變。

這時(shí)采用以下步驟得到最優(yōu)決策。

在第22節(jié)描述的決策約束下,生成各種可能的決策動(dòng)作,形成下一步狀態(tài)集合;

把下一步狀態(tài)集中的每一個(gè)狀態(tài)作為第32節(jié)敘述的近似函數(shù)輸入,這時(shí)近似函數(shù)的輸出為下一步狀態(tài)的價(jià)值(),該價(jià)值為第31節(jié)Bellman方程迭代計(jì)算的“期望”價(jià)值;

當(dāng)狀態(tài)集合中的每一個(gè)狀態(tài)都經(jīng)過步驟2,計(jì)算出相應(yīng)期望價(jià)值后(該過程可以并行執(zhí)行),導(dǎo)致下一步狀態(tài)價(jià)值最大的決策可看作當(dāng)前最優(yōu)決策。

4 仿真實(shí)例分析

4.1 仿真方案設(shè)計(jì)

圖4為仿真流程圖。初始化模塊中,仿真時(shí)鐘清零,保障分隊(duì)一開始都位于所屬基地且處于空閑狀態(tài),且統(tǒng)計(jì)變量記錄器和申請(qǐng)隊(duì)列初始化為空,統(tǒng)計(jì)變量記錄器用于記錄仿真實(shí)驗(yàn)需要保存的性能指標(biāo),包括累積獎(jiǎng)勵(lì)、事件響應(yīng)時(shí)間、保障分隊(duì)利用率等。事件列表在初始化階段存儲(chǔ)1條初始事件,仿真開始后在第34節(jié)中按照式(13)根據(jù)發(fā)生率生成新的事件。

圖4 仿真流程圖Fig.4 Simulation flow chart

時(shí)鐘處理程序模塊中,從事件列表中選擇下一個(gè)待處理事件并把時(shí)鐘推進(jìn)到事件標(biāo)記的仿真時(shí)刻。

事件處理程序模塊中,根據(jù)已訓(xùn)練完畢的近似函數(shù)(表示調(diào)度策略)輸出保障分隊(duì)分派決策動(dòng)作,統(tǒng)計(jì)變量及系統(tǒng)狀態(tài)也相應(yīng)改變,并生成新的事件加入事件列表中。如果到達(dá)預(yù)定仿真時(shí)間(本文實(shí)驗(yàn)設(shè)置為24 h)則退出仿真,否則返回時(shí)鐘處理模塊進(jìn)入下一次仿真循環(huán)。

4.2 仿真參數(shù)設(shè)置

為了驗(yàn)證強(qiáng)化學(xué)習(xí)模型在后裝保障調(diào)度領(lǐng)域的適用性,本文采用聯(lián)想工作站ThinkStation P710及Matlab并行計(jì)算工具箱(Parallel Computing Toolbox)作為計(jì)算平臺(tái),工作站CPU配置為雙核Xeon E5-2603 v4,內(nèi)存為128 GB。

圖5為仿真實(shí)驗(yàn)的場(chǎng)景設(shè)置,出于數(shù)據(jù)安全考慮刪除了背景地圖,圖中有兩個(gè)保障基地和兩個(gè)前進(jìn)基地,與保障基地相比,前進(jìn)基地較小,當(dāng)沒有申請(qǐng)所需物質(zhì)裝備時(shí),需要從保障基地補(bǔ)充。設(shè)4個(gè)保障分隊(duì)分屬4個(gè)基地管理,由一個(gè)統(tǒng)一的聯(lián)合保障指揮中心協(xié)調(diào)運(yùn)行,在空閑時(shí)回到自己的分管基地休整。

圖5 作戰(zhàn)行動(dòng)場(chǎng)景Fig.5 Operational case

另外圖5中還包括54個(gè)交戰(zhàn)地點(diǎn),為了便于與精確策略迭代算法比較,分屬12個(gè)交戰(zhàn)區(qū)域。由其代表區(qū)域內(nèi)作戰(zhàn)部隊(duì)的保障申請(qǐng),交戰(zhàn)區(qū)域數(shù)量可以根據(jù)調(diào)度計(jì)算機(jī)的性能調(diào)整,最高數(shù)量可以與交戰(zhàn)地點(diǎn)數(shù)量相等,但此時(shí)受保障分隊(duì)-保障請(qǐng)求對(duì)的影響,計(jì)算空間會(huì)變得過大,導(dǎo)致精確算法無法執(zhí)行,近似算法的執(zhí)行時(shí)間也會(huì)增大。

按式(13)產(chǎn)生各交戰(zhàn)區(qū)域不同優(yōu)先級(jí)保障申請(qǐng)的發(fā)生概率,其參數(shù)配置如表1表示。從式(4)中立即獎(jiǎng)勵(lì)函數(shù)的表達(dá)式可以看出,立即獎(jiǎng)勵(lì)與保障需求事件的優(yōu)先級(jí)權(quán)重、響應(yīng)時(shí)間和工作量有關(guān),在仿真實(shí)驗(yàn)中工作量都設(shè)為相同,優(yōu)先級(jí)權(quán)重的設(shè)置為=09、=009、=001。保障分隊(duì)至各區(qū)域的運(yùn)輸時(shí)間通過蒙特卡羅模擬過程得到,如表2所示,可以看出它與圖5中保障分隊(duì)-保障區(qū)域距離及保障分隊(duì)的運(yùn)輸速度有關(guān)。最后可以通過式(4)計(jì)算得到立即獎(jiǎng)勵(lì),為了節(jié)省篇幅,本處沒有顯示立即獎(jiǎng)勵(lì)值。

表1 按區(qū)域-優(yōu)先級(jí)分類的保障申請(qǐng)概率

表2 保障分隊(duì)至各區(qū)域運(yùn)輸時(shí)間均值

4.3 敏感性分析

影響圖3所示策略迭代算法的計(jì)算復(fù)雜性和性能的主要參數(shù)為內(nèi)循環(huán)次數(shù)和外循環(huán)次數(shù),為此本文設(shè)計(jì)了不同參數(shù)級(jí)別的9種方案進(jìn)行測(cè)試,共測(cè)試20次,表3為設(shè)計(jì)方案及對(duì)應(yīng)的計(jì)算時(shí)間均值。

表3 設(shè)計(jì)方案對(duì)應(yīng)的計(jì)算時(shí)間

圖6中1/表示了保障申請(qǐng)的到達(dá)時(shí)間間隔,它某種程度上可以反映戰(zhàn)況的激烈程度,表示保障申請(qǐng)的優(yōu)先級(jí)別,1為緊急,2為重要。從圖6中可以發(fā)現(xiàn),當(dāng)戰(zhàn)況激烈,保障申請(qǐng)率較高時(shí),保障分隊(duì)負(fù)載加重,導(dǎo)致保障響應(yīng)時(shí)間延長。而且優(yōu)先級(jí)較高的保障申請(qǐng)能夠得到較快的響應(yīng)。另外第5號(hào)設(shè)計(jì)方案在不同仿真參數(shù)下取得的效果較好,從表2可以看出,其對(duì)應(yīng)的外循環(huán)次數(shù)為10,內(nèi)循環(huán)次數(shù)為10 000,因此本文在仿真實(shí)驗(yàn)中以該設(shè)計(jì)方案為基線方案。

圖6 不同設(shè)計(jì)方案下的保障響應(yīng)時(shí)間Fig.6 Response time according to different design schemas

4.4 功能驗(yàn)證

表4 不同場(chǎng)景下優(yōu)化分配策略

本文優(yōu)化分配算法與文獻(xiàn)[7]描述的常規(guī)“最近分配”策略進(jìn)行了比較,表3中帶“+”的數(shù)字表示與“最近分配”策略不同的分配結(jié)果。從表4可以看出,由于緊急保障優(yōu)先級(jí)高且立即獎(jiǎng)勵(lì)較大,所以大多數(shù)情況下優(yōu)化分配與最近分配結(jié)果相同,但也有不同情況,例如在場(chǎng)景1、場(chǎng)景2、場(chǎng)景4和場(chǎng)景5下當(dāng)7號(hào)區(qū)域發(fā)出緊急保障申請(qǐng)時(shí),二者分配結(jié)果不同。例如在場(chǎng)景1下所有保障分隊(duì)空閑時(shí),如果7號(hào)區(qū)域發(fā)出緊急保障申請(qǐng),優(yōu)化算法分配第4隊(duì)保障分隊(duì)執(zhí)行任務(wù),而這時(shí)按表2第7行數(shù)據(jù),最近分配應(yīng)該派遣第3隊(duì)(離7號(hào)區(qū)域最近)處理。造成二者分配結(jié)果不同的原因與表1的保障申請(qǐng)概率和表2的響應(yīng)時(shí)間有關(guān),從表2可以看出第3分隊(duì)和第4分隊(duì)到達(dá)7號(hào)區(qū)域的時(shí)間分別為45.847分鐘和45.999分鐘,相差很小,然而從表1可以看出6號(hào)區(qū)域的保障申請(qǐng)發(fā)生概率為0.049 6+0.049 6+0.210 9≈0.31,大于7號(hào)區(qū)域的保障申請(qǐng)概率0.22,而第3分隊(duì)與6號(hào)區(qū)域的距離(58.221)比第4分隊(duì)的距離(68.596)要近得多,為了應(yīng)對(duì)6號(hào)區(qū)域可能出現(xiàn)的保障申請(qǐng),優(yōu)化策略選擇第4分隊(duì)處理該次申請(qǐng)。

4.5 性能驗(yàn)證

第一個(gè)性能驗(yàn)證實(shí)驗(yàn)比較隨著保障申請(qǐng)概率變化,優(yōu)化算法性能的變化情況,算法的外循環(huán)(策略改進(jìn)迭代次數(shù))設(shè)為10,內(nèi)循環(huán)(策略評(píng)估迭代次數(shù))設(shè)為10 000,式(13)中保障申請(qǐng)到達(dá)率分別設(shè)為1/30,1/60和1/120,即平均30 min、60 min和120 min發(fā)生一次保障申請(qǐng),結(jié)果如表5所示。

表5 實(shí)驗(yàn)比較結(jié)果

其中性能改進(jìn)率impr=(-)/,為優(yōu)化算法計(jì)算得到的價(jià)值,為最近分配策略計(jì)算得到的價(jià)值,置信度為95%,URT為緊急保障的等待時(shí)間,IRT為重要保障的等待時(shí)間,Busy為保障分隊(duì)的平均忙碌率,CT為計(jì)算時(shí)間?？梢钥闯鲭S著的增加,優(yōu)化算法在較少的計(jì)算時(shí)間范圍內(nèi),性能明顯強(qiáng)于最近分配策略。

圖7表示隨著策略改進(jìn)迭代次數(shù)的增加,性能改進(jìn)率impr的變化情況,可以看出,在嶺回歸算法的步驟2中增加了平滑函數(shù)后,計(jì)算結(jié)果質(zhì)量得到了進(jìn)一步改善。

圖7 平滑函數(shù)對(duì)算法性能的影響Fig.7 Performance impact on algorithm performance by smoothing function

另外,從優(yōu)化算法得到的基函數(shù)權(quán)重結(jié)果來看,第4類基函數(shù)對(duì)應(yīng)的權(quán)重最大,反映的是保障分隊(duì)正在處理的申請(qǐng)的優(yōu)先級(jí),權(quán)重大表示它對(duì)分配策略的影響最大。反映保障分隊(duì)距離保障申請(qǐng)點(diǎn)的距離和工作量的基函數(shù)權(quán)重也相對(duì)較大,只有第1類基函數(shù)的權(quán)重最小,這表示它在回歸中所起的作用也最小,這應(yīng)該是由于優(yōu)化算法對(duì)保障分隊(duì)的空閑程度缺乏懲罰。由于系統(tǒng)維度較高,影響因素較多,所以僅靠原則或者經(jīng)驗(yàn)難以決定預(yù)留哪一個(gè)保障分隊(duì)以及預(yù)留多久等決策變量,必須需要較好的學(xué)習(xí)算法才能得到較好質(zhì)量的分配結(jié)果。

通過調(diào)整來改變保障申請(qǐng)率,從中發(fā)現(xiàn)優(yōu)化算法相比最近分配策略的性能改進(jìn),如圖8所示,在不同設(shè)計(jì)方案下,隨著的減小,保障申請(qǐng)率也相應(yīng)較小,優(yōu)化算法針對(duì)最近分配的改進(jìn)率也逐漸減小。這意味著當(dāng)作戰(zhàn)烈度較小,需要后裝保障的頻率也不大時(shí),預(yù)留保障分隊(duì)的效用也被削弱。特別是當(dāng)發(fā)出保障申請(qǐng)的時(shí)間間隔均值為2 h時(shí),在仿真背景下,圖8中顯示優(yōu)化算法性能可能還不如最近分配,這說明基函數(shù)及其在它們基礎(chǔ)之上建立的近似價(jià)值函數(shù)存在著優(yōu)化限制,在保障強(qiáng)度很小時(shí),優(yōu)化算法與最近分配策略的性能差異可以忽略不計(jì)。

圖8 相較最近分配的性能改進(jìn)率Fig.8 Performance improvement with closest dispatch

再來檢驗(yàn)保障優(yōu)先級(jí)比例不同給算法性能帶來的影響,如圖9所示,不管優(yōu)先級(jí)比例如何變化,優(yōu)化算法性能都要顯著高于最近分配,而且隨著緊急保障申請(qǐng)(高優(yōu)先級(jí))的比例增加,優(yōu)化性能更為顯著。

圖9 優(yōu)先級(jí)比例變化的影響Fig.9 Impact by priority ratio changes

最后比較了當(dāng)運(yùn)輸工具速度提高時(shí)不同調(diào)度策略性能的變化情況,這里只調(diào)整了保障分隊(duì)的平均運(yùn)輸速度,其他參數(shù)還是保持不變,表6和表7分別顯示了最近分配和優(yōu)化分配策略的計(jì)算性能。從數(shù)據(jù)安全考慮基準(zhǔn)速度值沒有顯示,Spd Inc表示相對(duì)于基準(zhǔn)速度的提高百分比。

表6 速度提高時(shí)最近分配策略的性能

表7 速度提高時(shí)優(yōu)化分配策略的性能

從表6和表7中可以看出,對(duì)于最近分配和優(yōu)化分配兩種策略而言,都能利用運(yùn)輸速度的提高改善調(diào)度性能。對(duì)于優(yōu)化分配策略,當(dāng)速度提高了25%后,緊急保障申請(qǐng)和重要保障申請(qǐng)的平均響應(yīng)時(shí)間分別為117.2 min和141.7 min,特別是重要保障申請(qǐng)的響應(yīng)時(shí)間從236.5 min減少為141.7 min,這是相當(dāng)大的性能改進(jìn)。盡管當(dāng)速度提高后,表5中最近分配的性能改進(jìn)程度還要高于表6中優(yōu)化分配策略的改進(jìn)程度,但優(yōu)化分配策略還是能夠較大程度的利用速度優(yōu)勢(shì)來改進(jìn)調(diào)度效果。

5 結(jié) 論

智能化后裝保障是智能化戰(zhàn)爭的主要組成部分,在激烈作戰(zhàn)時(shí),當(dāng)指揮人員接收到作戰(zhàn)部隊(duì)發(fā)出的保障申請(qǐng)后,需要在較短時(shí)間內(nèi)給出調(diào)度指令。在滿足各項(xiàng)保障條例情況下,一個(gè)常規(guī)做法是派遣離申請(qǐng)部隊(duì)最近的保障分隊(duì)執(zhí)行此次任務(wù),然而這種直覺方式可能會(huì)造成較大損失。例如當(dāng)保障分隊(duì)被派遣執(zhí)行一個(gè)低優(yōu)先級(jí)的任務(wù)后,如果隨后在附近發(fā)生了高優(yōu)先級(jí)保障申請(qǐng),就會(huì)出現(xiàn)這種局面。而由于影響調(diào)度的因素較多,指揮人員僅憑經(jīng)驗(yàn)或條令條例很難在短時(shí)間內(nèi)給出優(yōu)化決策。為此提出了基于強(qiáng)化學(xué)習(xí)的調(diào)度方法,該方法具有學(xué)習(xí)能力,能夠從有折扣長期效益出發(fā),在派遣合適保障力量的同時(shí)為下一步可能出現(xiàn)的保障事件預(yù)留保障力量。仿真實(shí)驗(yàn)從功能和性能兩方面驗(yàn)證了具有強(qiáng)化學(xué)習(xí)能力的調(diào)度方法的優(yōu)越性。