基于改進Q學(xué)習(xí)的IMA系統(tǒng)重構(gòu)藍圖生成方法

羅慶，張濤，單鵬，張文濤，劉子豪

1. 航空工業(yè)沈陽飛機設(shè)計研究所，沈陽 110035

2. 南京航空航天大學(xué) 航天學(xué)院，南京 210016

3. 西北工業(yè)大學(xué) 軟件學(xué)院，西安 710072

4. 航空工業(yè)西安航空計算技術(shù)研究所，西安 710065

模塊化航空綜合電子系統(tǒng)(Integrated Modular Avionics, IMA)具有低成本、低功耗等顯著優(yōu)勢[1-2]。隨著航空電子系統(tǒng)功能急劇增加，IMA系統(tǒng)結(jié)構(gòu)愈加復(fù)雜，安全可靠性風(fēng)險增大。當(dāng)系統(tǒng)故障時，通過對軟件和硬件資源的重構(gòu)配置，以容錯保證系統(tǒng)功能和性能要求[3-4]。

傳統(tǒng)重構(gòu)方法采用基于模擬退火算法[5]、遺傳算法[6]等啟發(fā)式算法[7]預(yù)先訓(xùn)練生成的重構(gòu)藍圖，在飛行過程出現(xiàn)故障時，根據(jù)預(yù)先加載重構(gòu)藍圖，進行系統(tǒng)重構(gòu)容錯[8-9]?，F(xiàn)有方法所生成的重構(gòu)藍圖，收斂速度慢，難以生成最優(yōu)藍圖。

本文研究基于強化學(xué)習(xí)的重構(gòu)藍圖動態(tài)生成方法，直接與環(huán)境交互訓(xùn)練學(xué)習(xí)，并利用強化學(xué)習(xí)中時間差分的特性積累重構(gòu)經(jīng)驗[10-11]，對多目標(biāo)進行優(yōu)化[12-13]，從而快速生成高質(zhì)量重構(gòu)藍圖，提高綜合電子系統(tǒng)重構(gòu)容錯能力。本文提出方法的主要貢獻如下。

1) 不僅考慮了綜合電子系統(tǒng)重構(gòu)的基本資源約束，并且實現(xiàn)了負載均衡、重構(gòu)影響、重構(gòu)時間、重構(gòu)降級的多目標(biāo)優(yōu)化，保證重構(gòu)藍圖質(zhì)量。

2) 采用模擬退火框架改進Q學(xué)習(xí)搜索策略，提高了藍圖生成算法在最優(yōu)解的收斂性，以及算法效率。

1 相關(guān)工作

在重構(gòu)系統(tǒng)建模方面，Cui等[14]基于向后重構(gòu)的概念提出了一種分散式重構(gòu)技術(shù)，利用分散化使系統(tǒng)更快地適應(yīng)計算機模塊中已識別的故障，但增加了系統(tǒng)中每個節(jié)點的復(fù)雜性；Wang等[15]提出了一種基于有限狀態(tài)機理論和故障邏輯的系統(tǒng)可靠性建模與驗證方法；Wei等[16]提出了一種基于AADL(Architecture Analysis and Design Language)模型的綜合電子系統(tǒng)安全關(guān)鍵軟件重構(gòu)方法，使用擴展的錯誤模型和危險模型附件建模操作行為和錯誤行為，檢測故障和危險的發(fā)生。

在重構(gòu)分析方面，Pourmohseni等[17]提出了一種確定性映射重構(gòu)方法，該方法能夠分析最壞情況下的重構(gòu)延遲，從而實現(xiàn)給定的一組映射集之間的可預(yù)測重構(gòu)；Zhang等[18]提出了一種描述組件錯誤狀態(tài)轉(zhuǎn)換、系統(tǒng)架構(gòu)和重構(gòu)行為的建模方法，并設(shè)計模型轉(zhuǎn)換規(guī)則來建立可計算模型，分析其重構(gòu)后應(yīng)用的可調(diào)度性；Da Fontoura等[19]提出了用于故障管理的重構(gòu)方法及時序分析的模型檢查方法，能夠在滿足設(shè)計時序約束的前提下評估所有可預(yù)見的情況，但時序分析的速度和有效性有待提高。

綜上所述，當(dāng)前重構(gòu)技術(shù)研究主要集中在系統(tǒng)建模和分析驗證方面，對于重構(gòu)藍圖生成方法研究較少。因此，如何高效生成高質(zhì)量重構(gòu)藍圖成為亟需解決的問題。

2 IMA系統(tǒng)的智能重構(gòu)方法

根據(jù)IMA組成和特點，建立了IMA系統(tǒng)模型，給出了系統(tǒng)重構(gòu)資源約束和評價指標(biāo)，定義了多目標(biāo)優(yōu)化函數(shù)，最后設(shè)計了重構(gòu)藍圖的智能生成算法。

2.1 IMA系統(tǒng)模型

如圖1所示，IMA可以簡化為集中式硬件結(jié)構(gòu)。其中，一個IMA機箱包含多個處理器模塊，每個處理器模塊可設(shè)置多個任務(wù)分區(qū)，每個任務(wù)分區(qū)中可部署一個或多個應(yīng)用軟件，不同處理器之間通過通信總線相互連接。

圖1 系統(tǒng)簡化示意圖

在IMA系統(tǒng)中，基于資源共享的思想[20]，將硬件資源抽象地轉(zhuǎn)化為邏輯模塊。因此，結(jié)合硬件和軟件需求，這里分別建立應(yīng)用軟件M、分區(qū)P和處理器C模型。

2.2 基本約束與優(yōu)化指標(biāo)

1) 重構(gòu)約束

首先定義基本約束，以篩選出有效的系統(tǒng)重構(gòu)藍圖。在時間方面，IMA系統(tǒng)的每個分區(qū)在處理器內(nèi)都有固定的開始時間和執(zhí)行時間。一個分區(qū)中的所有應(yīng)用軟件必須在規(guī)定的運行時間內(nèi)完成。在內(nèi)存方面，應(yīng)用軟件占用的內(nèi)存總和不得超過該分區(qū)的可用內(nèi)存。

2) 優(yōu)化指標(biāo)

在基本資源約束基礎(chǔ)之上，定義重構(gòu)藍圖評價指標(biāo)，以進一步優(yōu)選出高質(zhì)量的重構(gòu)藍圖。這里定義了負載均衡、重構(gòu)影響、重構(gòu)時間和重構(gòu)降級等4個優(yōu)化評價指標(biāo)。

① 負載均衡

負載均衡可以提高應(yīng)用軟件的執(zhí)行速度。利用標(biāo)準(zhǔn)差來衡量各分區(qū)荷載的離散程度。因此，LB計算公式為

(1)

(2)

② 重構(gòu)影響

重構(gòu)影響是指系統(tǒng)重構(gòu)對應(yīng)用的影響，主要衡量應(yīng)用軟件重新配置的成功率。這里將應(yīng)用軟件重要性分為五級：1～5級。數(shù)字越大，應(yīng)用軟件越重要。因此，In的計算公式為

(3)

式中：nM表示成功完成重新配置的應(yīng)用軟件數(shù)；NM表示發(fā)生故障的處理器中需要重新配置的應(yīng)用軟件總數(shù)；GMi為應(yīng)用Mi的重要等級。

③ 重構(gòu)時間

重構(gòu)時間是完成所有應(yīng)用軟件遷移重構(gòu)的時間。在重構(gòu)時，各個處理器同時根據(jù)重構(gòu)藍圖順序加載其應(yīng)用軟件。因此，各個處理器重構(gòu)時間為其需要加載應(yīng)用時間之和。而IMA系統(tǒng)重構(gòu)時間則是所有處理器最長加載時間。

系統(tǒng)重構(gòu)時間Tre定義為

(4)

式中：Tmax表示最大重新配置時間；TCk表示處理器Ck的重構(gòu)恢復(fù)時間，定義為

(5)

式中：Nre表示在處理器Ck中重新加載的應(yīng)用軟件數(shù)；TMi為應(yīng)用軟件Mi的重新配置時間，取決于應(yīng)用軟件大小。

④ 重構(gòu)降級

重構(gòu)降級表示當(dāng)系統(tǒng)冗余資源不足時，犧牲低優(yōu)先級應(yīng)用來恢復(fù)高優(yōu)先級應(yīng)用。主要衡量重構(gòu)后系統(tǒng)應(yīng)用功能完整性。De的定義為

(6)

式中：nf表示無法重新配置需要犧牲的應(yīng)用軟件的總和；nM表示重構(gòu)系統(tǒng)中的應(yīng)用軟件總數(shù)。

3) 多目標(biāo)優(yōu)化函數(shù)

綜合基本約束和優(yōu)化評價指標(biāo)，這里設(shè)定多目標(biāo)優(yōu)化函數(shù)為

maxf=λ1LB+λ2In+λ3De+λ4Tre

(7)

2.3 重構(gòu)藍圖生成算法

本文通過改進Q學(xué)習(xí)方法，智能生成綜合電子系統(tǒng)重構(gòu)藍圖。首先定義了重構(gòu)藍圖Q學(xué)習(xí)的基本要素，包括狀態(tài)、動作、策略、回報函數(shù)、狀態(tài)-動作函數(shù)等。然后提出了一種Q學(xué)習(xí)結(jié)合模擬退火的藍圖生成算法框架。

1)Q學(xué)習(xí)基本要素

① 狀態(tài)s

將系統(tǒng)重構(gòu)過程的配置藍圖定義為Q學(xué)習(xí)的狀態(tài)元素s，其定義為

s=

(8)

式中：Cs={C1,C2,…,Cn}、Ps={P1,P2,…,Pm}和Ms={M1,M2,…,Ml}分別表示處理器集合、分區(qū)集合和應(yīng)用軟件集合；Bind={Mi→Pj→Ck}是應(yīng)用程序在分區(qū)和處理器上的映射信息[21]。

② 動作a

動作a定義為將應(yīng)用軟件重新配置到新的處理器分區(qū)，即

a=re

(9)

式中：re表示將應(yīng)用Mi重新部署到處理器Ck中的分區(qū)Pj。選擇動作后從舊狀態(tài)到新狀態(tài)的轉(zhuǎn)換函數(shù)定義如下：

(10)

③ 策略π

策略是指從配置狀態(tài)的動作空間中選擇動作的方法。這里選擇了一種平衡探測和收斂的貪婪策略作為重構(gòu)策略。該策略依概率ε隨機選擇動作空間里的動作，或依概率1-ε選擇當(dāng)前狀態(tài)下具有最高狀態(tài)Q值的動作。策略π的定義為

(11)

式中：argmaxaQ(s,a)表示使得狀態(tài)Q值最高的動作。為使策略在充分探索的同時又具有收斂性，對ε采用指數(shù)衰減化處理：

(12)

式中：N表示總探索次數(shù)；t為當(dāng)前探索次數(shù)，初始時，ε=1。

④ 回報函數(shù)R

回報函數(shù)R用于在重構(gòu)動作后對新的配置藍圖進行評估。如果在執(zhí)行應(yīng)用軟件重構(gòu)動作a之后，當(dāng)前配置狀態(tài)si變?yōu)樾聽顟B(tài)si+1，那么必須提供一個評估新狀態(tài)si+1、好壞的獎勵信號。

本文根據(jù)狀態(tài)si+1將獎賞分為3種情況：第一，如果si+1不滿足資源約束，則對錯誤動作給予負獎賞；第二，如果滿足資源約束，但系統(tǒng)還未重構(gòu)完成，則不給予獎勵；第三， 如果si+1滿足資源約束，并且已經(jīng)完成系統(tǒng)重構(gòu)，將通過多目標(biāo)優(yōu)化函數(shù)給予正獎勵。因此，回報函數(shù)定義為

(13)

式中：R(s,a)表示在系統(tǒng)重構(gòu)s中選擇重構(gòu)動作a的回報；LB、In、De和Tre分別表示負載均衡指標(biāo)、重構(gòu)影響指標(biāo)、重構(gòu)降級指標(biāo)和重構(gòu)時間指標(biāo)。這4個指標(biāo)的權(quán)重分別表示為λ1、λ2、λ3和λ4。

⑤ 狀態(tài)-動作函數(shù)Q(s,a)

狀態(tài)-動作函數(shù)Q(s,a)表示從狀態(tài)s出發(fā)，執(zhí)行動作a并再使用策略π后帶來的累計獎賞。

Q值的迭代計算公式定義為

QNew(s,a)=Q(s,a)+α[R(s,a)+

γmaxQ′(s′,a′)-Q(s,a)]

(14)

式中：QNew(s,a)表示通過在系統(tǒng)配置s中執(zhí)行動作a獲得的新的Q值；Q(s,a)為當(dāng)前s對應(yīng)動作a的Q值；α和γ分別表示學(xué)習(xí)率和獎勵衰減；maxQ′(s′,a′)表示在新的重新配置狀態(tài)s′中，通過采取行動a′獲得的最大狀態(tài)值函數(shù)。

2) 算法機制

這里引入模擬退火思想，將模擬退火中擾動解步驟改為應(yīng)用Q學(xué)習(xí)算法生成新解，即新的Q表。如圖2所示，算法會生成初始為0的Q表，并計算其回報R值作為最大回報值Rmax。通過Q學(xué)習(xí)算法進行Q表擾動產(chǎn)生新的Q表與新的R值后，計算其差值。若新的R值大于舊Rmax，則接受新的Q表，并更新Rmax。否則按Metropolis準(zhǔn)則[22]接受新Q表。

圖2 算法流程圖

將新的R值放入歷史池，判斷是否滿足終止條件，通常設(shè)終止條件為溫度到達最小值或歷史池趨于穩(wěn)定時停止算法。若不滿足終止條件，則緩慢減低溫度后繼續(xù)算法，溫度即為Q學(xué)習(xí)中的探索度ε。

如圖2所示，在模擬退火框架中，采用Q學(xué)習(xí)中狀態(tài)-動態(tài)函數(shù)的迭代公式計算擾動解，并將Q學(xué)習(xí)算法中探索策略的探索度ε與模擬退火中的溫度結(jié)合，使探索度能逐漸減為最小溫度，直至算法結(jié)束。改進后的算法如算法1所示。其中:M為應(yīng)用序列;P為分區(qū)序列;C為CPU序列；N為探索總次數(shù)。隨著探索次數(shù)t的增加，探索度ε逐漸減少為0，算法逐漸達到收斂狀態(tài)。算法中，探索度亦為溫度。

算法1 模擬退火Q學(xué)習(xí)算法輸入:M,P,C,N輸出:新Q表, Rt=0,α=0.01,Rmax=0,γ=0.9,Tmin=0.000 1pool = []While(ε≥Tmin) If 滿足終止條件 End ε=cosπ2·tN For s 1 to n If 0-1均勻分布隨機值 < ε a=當(dāng)前狀態(tài)的動作空間隨機選一個作為調(diào)度分區(qū) Else a=當(dāng)前狀態(tài)的動作空間選一個最高Q值作為根據(jù)所選動作調(diào)度分區(qū) 計算R(s,a) If s min(pool) Q(s,a)=Q'(s,a) pool.append(R(s,a)) t+=1 End

3 仿真實驗

基于上述算法描述，將基于模擬退火的改進Q學(xué)習(xí)算法(SA_Qlearn)進行仿真實驗，測試其不同指標(biāo)權(quán)重和不同超參對仿真效果的影響。選擇效果最好的參數(shù)實驗算法在不同環(huán)境下的結(jié)果。并引入模擬退火、差分進化、Q學(xué)習(xí)等算法進行對比，分析本文所提出算法的收斂性能和算法效率。

3.1 仿真實驗設(shè)置

實驗設(shè)定的IMA系統(tǒng)硬件與軟件應(yīng)用基本配置如表1和表2所示。如圖3所示，從初始配置S0開始，通過依次注入不同的處理器故障，產(chǎn)生不同的重構(gòu)配置。圖3中每個節(jié)點Si代表系統(tǒng)發(fā)生故障后的重構(gòu)配置，例如S1是在S0發(fā)生C1故障后的重構(gòu)配置，S7是在S0下同時發(fā)生C2、C3故障后的重構(gòu)配置。

表1 軟件應(yīng)用屬性數(shù)據(jù)

表2 IMA初始S0配置信息

圖3 智能重構(gòu)的環(huán)境遷移

3.2 指標(biāo)權(quán)重分析

在多目標(biāo)優(yōu)化過程中，各個優(yōu)化指標(biāo)的不同權(quán)重系數(shù)值，對應(yīng)著不同的收斂傾向。權(quán)重越高，收斂傾向越高。指標(biāo)間的相關(guān)性如圖4所示。

圖4為S7復(fù)雜環(huán)境下的指標(biāo)相關(guān)性熱力圖，其中指標(biāo)的權(quán)重分配為0.25、0.25、0.25、0.25。從圖4可以看出，負載均衡LB與重構(gòu)影響In、重構(gòu)降級De承0.35的相關(guān)性，與重構(gòu)時間基本沒有相關(guān)性。重構(gòu)影響In、重構(gòu)降級De之間相互為1的強相關(guān)性，與重構(gòu)時間呈-0.31弱負相關(guān)性。

圖4 S7環(huán)境下指標(biāo)間熱力相關(guān)圖

如表3所示，為驗證不同權(quán)重參數(shù)值對訓(xùn)練結(jié)果的影響，以S7重構(gòu)配置環(huán)境生成為例，實驗分析各個優(yōu)化指標(biāo)權(quán)重對訓(xùn)練收斂的影響。

表3 S7環(huán)境下不同權(quán)重λ的訓(xùn)練結(jié)果

從表3可以看出，若λ1或λ4的取值高于0.25，會發(fā)現(xiàn)最優(yōu)值很難高于0.9，并且遷移結(jié)果存在犧牲。在λ2或λ3取0.3以上時，若λ1取值高于λ4，則收斂難度增加，最終收斂結(jié)果并不趨向于最優(yōu)解。根據(jù)以上分析，優(yōu)化目標(biāo)權(quán)重分別取為：λ1=0.1、λ2=0.35、λ3=0.35、λ4=0.2。

3.3 學(xué)習(xí)率與獎勵衰減分析

不同的學(xué)習(xí)率α、與獎勵衰減γ也會對優(yōu)化訓(xùn)練過程產(chǎn)生影響。如圖3所示，在確定獎勵衰減γ=0.9的情況下，取不同的學(xué)習(xí)率進行訓(xùn)練。圖5、圖6中曲線是以每50項為基的滑動平均線。其中圖5對比了在S7環(huán)境下α=0.01，0.1，0.5，0.9等不同學(xué)習(xí)率對學(xué)習(xí)曲線的效果。

圖5 S7環(huán)境下不同學(xué)習(xí)率對回報值的影響

圖5中學(xué)習(xí)率α=0.01時藍色曲線上升的幅度最大且最終收斂的回報值最高。學(xué)習(xí)率越大，越容易過擬合，導(dǎo)致最后收斂回報值越低。

為驗證獎勵衰減γ對優(yōu)化訓(xùn)練過程產(chǎn)生的影響。如圖6所示，在確定學(xué)習(xí)率α=0.01的情況下，取不同的獎勵衰減進行訓(xùn)練。這里對比了在S7環(huán)境下γ=0.1、γ=0.4、γ=0.9、γ=1等不同獎勵衰減對學(xué)習(xí)曲線的效果。

圖6 S7環(huán)境下不同獎勵衰減對回報值的影響

圖6中曲線上升的幅度相差不大，其中獎勵衰減γ=0.9時綠色曲線最終收斂的回報值最高。獎勵衰減越大，后續(xù)的獎勵占比越大。當(dāng)γ=1時容易造成過擬合。

根據(jù)以上分析，實驗中取α=0.01、γ=0.9。

3.4 實驗結(jié)果

基于3.2與3.3節(jié)目標(biāo)權(quán)重與訓(xùn)練參數(shù)的選擇，對圖7中不同的環(huán)境使用基于模擬退火的Q學(xué)習(xí)算法進行訓(xùn)練。

如圖7所示，其中淡藍色曲線表示10 000次真實探索情況對應(yīng)的回報值的更新曲線，黃色曲線表示真實更新曲線中以每10次探索為單位的滑動平均趨勢曲線。并且根據(jù)黃色曲線可以看出探索的趨勢會隨著探索度ε的減少而收斂于最優(yōu)。其中，即使是在S6無可行解的環(huán)境下(必須犧牲應(yīng)用時，回報值無法大于0.9)，亦能找到使?fàn)奚鼞?yīng)用代價最小的動作解而收斂到最優(yōu)。

3.5 實驗分析

本文將所提出算法(SA_Qlearn)與模擬退火算法(SA)、差分進化算法(DEA)、傳統(tǒng)Q學(xué)習(xí)算法(Qlearn)等常用多目標(biāo)優(yōu)化算法相比較，以分析驗證所提出算法效率與收斂性能[23-27]。

1) 算法效率

以10 000次為最大迭代次數(shù)，分別記錄不同算法迭代用時與最終的收斂回報值。

如圖8所示，顯示了4種算法在8種重構(gòu)環(huán)境下10 000次迭代的求解時間。其中，由于DEA所用時間相對過長，為顯示其他3種算法的時間對比，對其真實求解時間乘以0.05。由于每次迭代都要計算種群中所有的解并且做出解的擾動，即使在縮小真實值的情況下，DEA的求解時間依然最大。而SA、Qlearn和SA_Qlearn這3種算法是無種群的線性迭代，因此這3種算法之間求解時間相差不大，Qlearn最小，SA_Qlearn次之，SA相對最大。

圖8 S1～S8求解時間對比

表4給出了4種算法在8種不同環(huán)境下訓(xùn)練10 000次的最終收斂值。顯然，SA_Qlearn算法可以得到比其他3種算法更優(yōu)的收斂值，Qlearn次之，DEA與SA差別不大。結(jié)合算法收斂值與算法求解時間對比，SA_Qlearn算法最好。

表4 S1～S8回報收斂值對比

2) 收斂性能

以復(fù)雜環(huán)境S7為例子，表5給出了4種算法在環(huán)境S7下迭代10 000次的局部回報值。

表5 S7環(huán)境下4種算法的局部回報變換

表5中數(shù)據(jù)表明，SA與DEA更容易陷于局部最優(yōu)解。Qleran算法雖然在1 000次左右就得到最優(yōu)解，但一直震蕩無法收斂。而SA_Qlearn算法結(jié)合了SA算法與Qlearn算法的優(yōu)點，并解決這兩種算法的缺點，在跳出局部最優(yōu)的同時亦有優(yōu)秀的收斂性能，從而得到更好的收斂值。

SA_Qlearn算法在SA的框架上引用擾動效果更好的Qlearn算法，使得該算法解決了SA容易收斂于局部最優(yōu)解的缺點。又在Qlearn算法上引入SA算法的溫度作為探索策略的探索度，解決了Qlearn算法震蕩而收斂困難的缺點。從而使SA_Qlearn算法既保留了兩個算法優(yōu)點，又解決了兩個算法缺點。

4 結(jié) 論

本文將強化學(xué)習(xí)的經(jīng)典Q學(xué)習(xí)算法引入模擬退火框架進行改進，并用于生成IMA系統(tǒng)重構(gòu)藍圖。本文研究工作為解決IMA系統(tǒng)的故障重構(gòu)提供了新的可行途徑，而且所提出的改進算法與傳統(tǒng)模擬退火算法、差分進化算法、Q學(xué)習(xí)算法相比，收斂性能更好、效率更高。