張 濤，張文濤，代 凌，陳婧怡，王 麗，魏倩茹

（西北工業(yè)大學軟件學院，陜西西安 710065）

1 引言

在綜合模塊化航空電子（Integrated Modular Avionics，IMA）系統(tǒng)［1］中，動態(tài)重構(gòu)是一種有效的故障容錯方法，已成功被應用于F-22，F(xiàn)-35，A380，B787等飛機航電系統(tǒng)［2］. 重構(gòu)藍圖定義了受故障影響的各個應用軟件的動態(tài)遷移與系統(tǒng)資源重配置策略. 在故障發(fā)生時，系統(tǒng)將依據(jù)所生成重構(gòu)藍圖對受故障影響的應用軟件進行動態(tài)遷移，使得應用軟件能夠恢復正常運行［3，4］. 目前主要針對少數(shù)單一故障模式，基于專家經(jīng)驗人工設計重構(gòu)藍圖，系統(tǒng)故障容錯能力有限［5］. 而對于復雜多級交聯(lián)故障模式，由于系統(tǒng)可用資源限制，需要多個應用軟件動態(tài)遷移，甚至犧牲低優(yōu)先級應用軟件，使得重構(gòu)藍圖的人工規(guī)劃困難［6，7］. 因此，研究自動化生成重構(gòu)藍圖的方法，是提高IMA系統(tǒng)重構(gòu)容錯能力的關鍵.

重構(gòu)藍圖生成需要綜合考慮系統(tǒng)負載均衡、重構(gòu)影響、重構(gòu)恢復時間和重構(gòu)降級等多個因素，是一個典型的NP 完全問題［8，9］. 為解決多目標優(yōu)化的系統(tǒng)重構(gòu)問題，傳統(tǒng)動態(tài)規(guī)劃［10，11］方法以空間換時間，在數(shù)據(jù)量大時會造成很大的浪費；分支界限算法［12］在單目標優(yōu)化上有優(yōu)勢但是無法考慮多目標綜合優(yōu)化；模擬退火［13］等啟發(fā)式算法雖然可解決多目標優(yōu)化重構(gòu)調(diào)度問題，但卻容易陷入局部最優(yōu)；基于種群進化思想的遺傳［14］和差分進化（Differential Evolution，DE）［15］等算法雖然可獲得更優(yōu)重構(gòu)調(diào)度解，但求解時間過長；使用強化學習中的Q 學習［16］在低維重構(gòu)調(diào)度上可以實現(xiàn)快速重構(gòu)調(diào)度，但容易震蕩，難以收斂；基于模擬退火的Q學習［17］同時結(jié)合了模擬退火和Q 學習的優(yōu)點，收斂效果更好，但算法迭代的次數(shù)多，無法快速求解. 單純的策略梯度［18］通常采用隨機梯度下降的算法方法快速求解，但在算法收斂上具有一定的震蕩特性，并且隨著迭代次數(shù)的增加其無偏估計量的計算耗時也隨之增加，導致在迭代次數(shù)較大時算法迭代更新速度過慢. 而有偏估計［19］可以有選擇地提取歷史經(jīng)驗，在有效地減少計算耗時的同時使期望向造成高回報值的動作方向快速偏移. 使用蒙特卡洛樹搜索（Monte Carlo Tree Search，MCTS）［20］可以在已知策略空間上探索出最優(yōu)的動作策略，若是策略空間探索不足則容易陷入局部最優(yōu).

綜上考慮，本文提出一種結(jié)合序貫博弈［21］的多智能體強化學習算法來模擬重構(gòu)應用軟件的重構(gòu)過程，將多目標的優(yōu)化過程轉(zhuǎn)化為序貫博弈過程中的競爭與合作目標，以優(yōu)化求解重構(gòu)藍圖. 重構(gòu)中每個待調(diào)度應用軟件均作為一個智能體，各個智能體不僅要爭取自身最優(yōu)條件，而且要滿足整體的多目標優(yōu)化需求，直到達到混合均衡條件［22］或最大博弈次數(shù). 算法首先根據(jù)重構(gòu)應用軟件優(yōu)先級確定其所對應智能體的博弈順序. 然后每個智能體使用策略梯度，根據(jù)各自動作是否滿足約束以及滿足約束的程度進行自身策略的迭代.接著使用MCTS方法，根據(jù)重構(gòu)后的目標函數(shù)值優(yōu)劣對全部智能體的策略進行更新，從而快速逼近均衡條件.與傳統(tǒng)優(yōu)化算法和傳統(tǒng)強化學習算法相比，所提出算法的優(yōu)化性能和穩(wěn)定性更優(yōu).

2 IMA系統(tǒng)重構(gòu)

2.1 IMA系統(tǒng)重構(gòu)架構(gòu)

在IMA 系統(tǒng)重構(gòu)架構(gòu)中，當CPU 發(fā)生故障時，需要根據(jù)重構(gòu)藍圖將受故障影響的應用軟件遷移到其他CPU，為其重新配置資源，使應用軟件恢復正常運行.如圖1所示，在CPU2發(fā)生故障后，將其分區(qū)內(nèi)的應用軟件C 和應用軟件D 分別遷移調(diào)度到CPU1和CPU3的分區(qū)1 與分區(qū)5 中. 基于重構(gòu)藍圖，被犧牲的應用軟件和需要遷移的應用軟件越少，應用軟件功能恢復時間越短，系統(tǒng)負載越均衡，則重構(gòu)藍圖質(zhì)量越好.

圖1 重構(gòu)架構(gòu)示意圖

2.2 重構(gòu)模型

將IMA 系統(tǒng)中的一組CPU 處理器記作C={C1，C2，…，Cb}，其中C代表CPU 的集合，第l個CPU 表示為Cl，b代表CPU 的總數(shù)量.b個CPU 中共有m個可用分區(qū)，記作P={P1，P2，…，Pm}，其中第j個分區(qū)表示為Pj，其屬性有分區(qū)內(nèi)存PM 和分區(qū)框架時間Td. 分區(qū)Pj中部署了軟件序列MPj，記為其中分區(qū)Pj中部署的第k個應用軟件表示為，其屬性有內(nèi)存RAM、優(yōu)先級Priority、最大運行時間WCET 和截止時間deadline. 在系統(tǒng)故障時，將生成受故障影響軟件集，記為D={D1，D2，…，Dn}，其中第i個應用軟件表示為Di. 如圖2 所示，在分區(qū)P2發(fā)生故障后，IMA 系統(tǒng)會將部署在該分區(qū)的軟件D1，D2和D3分別遷移至其他可用分區(qū)P4，P1和P5中，使受到影響的軟件繼續(xù)運行. 由于系統(tǒng)重構(gòu)時需要將受故障影響軟件遷移至其他可用的分區(qū)中，因此需要計算遷移后分區(qū)的CPU 使用率、內(nèi)存使用率對應的分區(qū)負載，確保應用軟件的資源可調(diào)度性.

圖2 重構(gòu)模型示例圖

（

1）分區(qū)CPU使用率

分區(qū)CPU 使用率體現(xiàn)了分區(qū)內(nèi)應用軟件的最大運行時間占用分區(qū)框架時間的比例. 具體公式如下所示：

當應用軟件Di被調(diào)入Pj后，有

其中，WCETDi表示應用軟件Di的最大運行時間.

重構(gòu)可調(diào)度性約束1.分區(qū)資源限制

當待重構(gòu)應用軟件Di被調(diào)入分區(qū)Pj后，分區(qū)當中的CPU使用率應滿足Cuse(Pj，Di)≤Cuse-max.

（2）分區(qū)內(nèi)存使用率

分區(qū)內(nèi)存使用率體現(xiàn)了分區(qū)內(nèi)應用軟件的內(nèi)存占用分區(qū)內(nèi)存的比例. 具體公式如下所示：

當應用軟件Di被調(diào)入Pj后，有

其中，RAMDi表示應用軟件Di的內(nèi)存容量.

重構(gòu)可調(diào)度性約束2.分區(qū)內(nèi)存限制

當待重構(gòu)應用軟件Di被調(diào)入分區(qū)Pj后，分區(qū)當中的內(nèi)存應滿足調(diào)用條件RMuse(Pj，Di)≤RMuse-max.

（3）分區(qū)負載

分區(qū)負載綜合考慮了分區(qū)CPU 使用率和分區(qū)內(nèi)存使用率，是對兩個指標的統(tǒng)一處理，分區(qū)負載越低，意味著該分區(qū)應用軟件占用的資源越少，分區(qū)剩余的資源越多. 具體公式如下所示：

當?shù)贒i個應用軟件被調(diào)入Pj后，有

2.3 應用軟件重構(gòu)問題

結(jié)合IMA 系統(tǒng)重構(gòu)模型，重構(gòu)中每個待調(diào)度的應用軟件都期望在成功調(diào)度的同時被調(diào)入剩余資源最豐富的分區(qū)，本文使用式（6）作為應用軟件被調(diào)入分區(qū)后資源豐富情況的數(shù)學表達，分區(qū)負載越小，代表該分區(qū)剩余的資源越多. 設重構(gòu)影響集I={I1，I2，…，In}為重構(gòu)過程中系統(tǒng)受影響的軟件序列集，初始時重構(gòu)影響集等于受故障影響的軟件集，即I=D.

當影響集I內(nèi)所有的應用軟件被調(diào)入分區(qū)序列P中 時，設X={[x11，x12，…，x1m+1]，…，[xn1，xn2，…，xnm+1]}，xij表示軟件Ii被調(diào)入至Pj的分區(qū)中.xij=1 表示軟件被正常調(diào)度，xij=0 表示不進行調(diào)度，當xij=1，j=1+m時表示軟件Ii被犧牲.

因此，對每個待調(diào)度的軟件Ii，有目標函數(shù)f1：

并且在重構(gòu)結(jié)束后，在滿足式（7）約束的情況下，系統(tǒng)期望擁有一個綜合評價高的重構(gòu)藍圖. 針對系統(tǒng)重構(gòu)后的綜合評價，本文借鑒文獻［17］中的4 個評價指標，分別改進為表示重構(gòu)后系統(tǒng)的負載均衡、重構(gòu)影響度、重構(gòu)恢復時間和重構(gòu)降級率4 個指標，定義如下.

（1）負載均衡

負載均衡表示系統(tǒng)資源使用的均衡程度，可以表示重構(gòu)后系統(tǒng)資源使用的分布情況. 在重構(gòu)結(jié)束后，可以依據(jù)所有可用分區(qū)的負載計算系統(tǒng)資源的使用均衡程度，由此定義負載均衡指標：

其中，n表示發(fā)生故障需要重構(gòu)的軟件數(shù)，m表示可調(diào)度分區(qū)總數(shù)表示軟件序列I按X調(diào)度后所有分區(qū)負載均衡的均值.

（2）重構(gòu)影響度

重構(gòu)影響度指執(zhí)行重構(gòu)后對原系統(tǒng)軟件狀態(tài)的影響程度. 按照軟件對系統(tǒng)影響的等級將應用軟件的重要性分為五個優(yōu)先級. 數(shù)字越大，應用軟件就越重要. 重構(gòu)應盡量不影響原系統(tǒng)的軟件狀態(tài)，優(yōu)先級高的軟件應該優(yōu)先被調(diào)入，若調(diào)入失敗，即不滿足約束時，應調(diào)換出優(yōu)先級低的軟件放入待調(diào)度軟件序列，同時放入重構(gòu)影響集I中，若分區(qū)中的軟件優(yōu)先級均比待調(diào)入軟件優(yōu)先級高，則調(diào)度失敗，直至所有的分區(qū)均無法滿足約束，則停止且將該軟件放入重構(gòu)犧牲集De. 設因優(yōu)先級被調(diào)出的軟件共k個，則重構(gòu)影響集I中共有原先序列D中的n個軟件和新調(diào)出的k個軟件. 由此定義重構(gòu)影響度指標：

其中，Pri 表示軟件優(yōu)先級；nm表示重構(gòu)犧牲集中的軟件個數(shù)，即重構(gòu)后因為可用資源不足而不得不犧牲的軟件總數(shù)；n+k是重構(gòu)影響集的個數(shù)，表示發(fā)生故障的處理器中需要重新配置的軟件總數(shù)；PriDei表示重構(gòu)犧牲集中第i個軟件的優(yōu)先集PriIj表示重構(gòu)影響集中從原系統(tǒng)因優(yōu)先級低被搶占調(diào)出的軟件個數(shù).

（3）重構(gòu)恢復時間

系統(tǒng)重構(gòu)過程中進程的恢復占據(jù)了主要時間，并假設當多個進程位于同一處理器時，重構(gòu)加載是串行的，重構(gòu)時間需要累加計算；當多個進程位于不同處理器時，重構(gòu)加載是并行的，將其中最大的恢復時間作為系統(tǒng)重構(gòu)時間. 由此定義重構(gòu)恢復時間指標：

其中，Tmax表示最大重構(gòu)時間，通常取值為CPU 主框架時間；Ts表示系統(tǒng)重構(gòu)時間，取IMA 系統(tǒng)內(nèi)所有處理器的重構(gòu)恢復時間的最大值，其計算公式為

其中，TCl表示處理器Cl的重構(gòu)恢復時間，取該處理器內(nèi)bm個分區(qū)中最大的分區(qū)重構(gòu)時間；TPj表示Pj分區(qū)內(nèi)需要重構(gòu)進程的重構(gòu)時間和，其計算公式為

其中，Nre表示分區(qū)Pj內(nèi)進行重構(gòu)加載的進程數(shù)量表示進程的重構(gòu)時間，與進程大小有關.

（4）重構(gòu)降級率

在IMA 系統(tǒng)的重構(gòu)過程中，位于故障處理器內(nèi)的部分進程可能由于系統(tǒng)冗余資源不足、重構(gòu)時間限制等未能及時完成重構(gòu)，則定義重構(gòu)犧牲集De，表示重構(gòu)結(jié)束后仍然剩余不得不被犧牲的軟件. 由此定義重構(gòu)降級率指標：

其中，n'表示重構(gòu)犧牲集De的進程數(shù)，即需要犧牲的進程總數(shù)；Nm 表示系統(tǒng)中的全部進程總數(shù)表示進程對應的重要等級.

重構(gòu)結(jié)束后藍圖四個指標的值越大，說明重構(gòu)藍圖的質(zhì)量越高. 因此，有目標函數(shù)f2：

3 序貫博弈強化學習重構(gòu)方法

3.1 強化學習序貫博弈模型

本文設置的序貫博弈模型是在強化學習常用的馬爾科夫決策過程的基礎上［23］，由六元組＜G，S，π，A，R，H＞構(gòu)成.

智能體G：重構(gòu)中需要調(diào)度的每個應用軟件定義為一個自主的智能體，它們獨立地與環(huán)境交互并根據(jù)對前面智能體行為的觀察采取自己的策略，為自己實現(xiàn)最大收益或最小損失.

狀態(tài)S：狀態(tài)為當前系統(tǒng)中所需重構(gòu)（故障的）的應用軟件序列D，以及所有可被調(diào)度（正常的）的分區(qū)狀態(tài)序列P與CPU 狀態(tài)序列C. 設狀態(tài)S=＜Cs，Ps，Ds，Disp＞，其 中 處 理 器Cs={C1，C2，…，Cb}，分區(qū)Ps={P1，P2，…，Pm}和Ds={D1，D2，…，Dn}分 別 代 表可被調(diào)度的CPU 序列、可被調(diào)度的分區(qū)序列和所需重構(gòu)的應用軟件序列. Disp={Di→Pj}代表應用軟件進程Di分配到分區(qū)Pj的映射［24］關系.

策略π：智能體在當前狀態(tài)下，選取動作的策略可以表示為以策略空間分布的概率選取分區(qū)作為執(zhí)行動作. 每個智能體在多智能體序貫博弈中遵循自己的策略，旨在當受環(huán)境和其他智能體的策略影響時使代理的獎勵最大化和成本最小化.

動作A：選取動作的過程其實就是重構(gòu)中調(diào)度的過程，即在當前狀態(tài)S下選中某個分區(qū)，將待調(diào)度的應用軟件部署到該分區(qū)的調(diào)度過程. 例如在調(diào)度第i個應用軟件時，動作A=re ＜Ii，Pj，Cl＞，其中re 表示將應用軟件Ii重新部署到Cl處理器中Pj分區(qū). 執(zhí)行動作A后，狀態(tài)從St進行更新St→St+1.

回報函數(shù)R：本文設計了兩個回報函數(shù)，分別對應智能體執(zhí)行動作的成本以及獎勵. 將智能體調(diào)度動作滿足約束的程度作為智能體執(zhí)行動作的成本回報值，回報值越高，意味著動作成本越少. 在重構(gòu)中所有智能體所有的動作都執(zhí)行結(jié)束后，對重構(gòu)后的系統(tǒng)狀態(tài)做出的綜合評價作為智能體們執(zhí)行動作獎勵的回報值，回報值越高，意味著該次重構(gòu)效果越好.

策略迭代函數(shù)H：本文基于兩個回報函數(shù)設計了兩種策略迭代的算法，使用基于強化學習的策略梯度算法和MCTS 算法分別將智能體的成本回報值和總體回報值反饋給智能體的策略，使得策略按著智能體期望的方向趨近更新.

如圖3 所示，在博弈t1中，首先由最高優(yōu)先級軟件D1對應的智能體G1在初始狀態(tài)S0下以策略π1做出動作Aj的選擇，即選擇將應用軟件D1調(diào)度到分區(qū)Pj.

圖3 序貫博弈模型示意圖

計算執(zhí)行該動作的成本回報值后該智能體的策略相應的進行更新，狀態(tài)也相應的改變?yōu)镾1. 次一級的智能體需要在上一級智能體的行為結(jié)果S1上做出動作選擇，直至所有的智能體調(diào)度完畢，該次重構(gòu)結(jié)束. 重構(gòu)結(jié)束后對重構(gòu)后系統(tǒng)進行綜合評價，并作為智能體們的獎勵，它們對應的策略亦做出更新. 這輪博弈t1結(jié)束，接著開啟下一輪的博弈t2，直至達到混合納什均衡或設定的最大博弈數(shù).

3.2 博弈競爭模型

每個智能體是相互獨立的，其對動作都有一個相應的策略空間與歷史成本經(jīng)驗池. 單個智能體調(diào)度動作執(zhí)行后，所部署分區(qū)的CPU 使用率與內(nèi)存使用率越小，說明該智能體本次重構(gòu)調(diào)度的成本越小，若超過設定的約束值，則該次重構(gòu)調(diào)度不佳.

當智能體Gi對應的應用軟件Di選擇的動作為調(diào)入分區(qū)Pj時，對目標函數(shù)1進行轉(zhuǎn)化有

因此，在博弈的競爭模型中，通過博弈交互的成本回報值高低和歷史的經(jīng)驗池，每個智能體自主執(zhí)行策略學習，最優(yōu)化自己動作所得到的回報，不需要考慮其他智能體的回報情況. 它們相互競爭，每個智能體的都旨在優(yōu)化自己的成本回報值.

3.2.1 博弈競爭策略

重構(gòu)初始時按應用軟件優(yōu)先級Priority 排列后，確定 調(diào) 度 順 序 為D1?D2?…?Dn，即 智 能 體G1，G2，…，Gn，每個智能體Gi都有自己的博弈策略θi-1，因此構(gòu)成多智能體的策略矩陣θ（初始時為0矩陣）：

從狀態(tài)S0開始，重構(gòu)中每個智能體的調(diào)度動作是基于上一個智能體調(diào)度產(chǎn)生的新環(huán)境執(zhí)行的，策略更新順序為θ0?θ1?…?θn-1，所以智能體的策略之間是相互影響的. 并且每個智能體是單一獨立且動作離散的，因此可以使用softmax 分布對當前狀態(tài)S和每個動作即每個待選分區(qū)設置一個偏好值，偏好值越大，被選中的概率就越大.

因此，策略π就是一個關于偏好函數(shù)的一個函數(shù). 即

Pr(A=a|S)表示在狀態(tài)S下選擇動作a的概率，即在狀態(tài)S下選擇動作a的策略. 初始時，所有的偏好值均為0，即開始時每個動作被選取的概率一樣. 因此，有

競爭策略的迭代函數(shù)H1：本文中，強化學習策略梯度主要用于智能體競爭策略的更新，策略矩陣θ中每一行向量為每個智能體對應的策略空間. 由式（19）定義優(yōu)化的成本回報函數(shù)作為博弈競爭的優(yōu)化目標. 這里定義每一智能體的平均回報，即第N輪博弈的第Gi個智能體時，策略πiN下的累計回報ρ(π)：

其中，dπ(S)是基于策略π生成的馬爾可夫鏈關于狀態(tài)的靜態(tài)分布，即從S0?S1?…?Sn-1代表智能體G1，G2，…，Gn調(diào)度時對應的第1 個應用軟件到第n個應用軟件所面臨的狀態(tài)；rS t(a)為在S狀態(tài)下第t次執(zhí)行a，a∈[1，1+m]動作的回報值. 當N趨近于無窮時，為ρ(π)的無偏估計量. 隨著N的增大，無偏估計量的計算時間也增大，為減少計算耗時，可以以一定的比例抽取歷史池. 這里使用有偏估計量（表示取N個r里最優(yōu)的x個的平均值）作為ρ(π)有效的歷史池，在犧牲全局最優(yōu)性的同時，使事件概率分布盡量往歷史最優(yōu)方向靠，增加收斂性.

設存在一個在s狀態(tài)下依策略π對動作a的期望評價值Qπ(S，a). 則有

此時，有

當確定狀態(tài)S時，即對應單一智能體時，由式（19）（21）（22）有

詳細證明過程可以參考文獻［25，26］.

則θS更新按梯度上升思想有

即在s狀態(tài)下，在選擇動作a并獲得收益后，策略矩陣的偏好值更新方式為

3.2.2 博弈競爭策略更新

本文采用策略梯度算法更新智能體策略，原因是它能夠直接優(yōu)化策略的期望回報，并以循環(huán)更新的方式直接在策略空間中迭代最優(yōu)策略. 在對系統(tǒng)狀態(tài)環(huán)境與對應動作所可能產(chǎn)生的結(jié)果一無所知的情況下，使用策略梯度可以快速地讓動作策略向趨近于期望方向更新. 博弈競爭策略的更新如圖4所示.

圖4 博弈策略更新流程示意圖

智能體Gi在第t輪博弈下基于自我的策略πt選擇動作at，回報函數(shù)根據(jù)策略和狀態(tài)對動作計算回報值并根據(jù)策略迭代函數(shù)H1進行更新策略，接著狀態(tài)Si-1對智能體做出的動作進行狀態(tài)轉(zhuǎn)移，生成新的狀態(tài)Si，并傳遞給下一個智能體Gi+1. 競爭策略更新如算法1所示.

算法1 博弈競爭策略更新算法輸入:初始化或上輪博弈后的策略矩陣θ輸出:策略矩陣θ FOR t=0 to N:FOR S in θ,θ={θ0，θ1，…，θn-1}:FOR a in {θS1，θS2，…，θS1+m}:Pra=π(S，a)END FOR依概率{Pra in S}選取動作a,a ∈[P1，P1+m]依動作由式(16)計算此次動作的rS t (a)IF len(-r'S)＜x-r'S =1 t+1 {rS1+rS2+…+rS t +r}ELSE-r'S =1 x top x{rS1+rS2+…+rS t +r}由式(25)更新θs θSa(t+1)=θSa(t)+α(rSt (a)--r'S)(1-π(S，a))θS b ≠a(t+1)=θSb ≠a(t)-α(rS t (a)--r'S)π(S，b)END FOR END FOR

3.3 博弈合作模型

當重構(gòu)的所有智能體都調(diào)度結(jié)束后，系統(tǒng)對指標綜合的評價將作為智能體們的獎勵，它們共用一個獎勵歷史經(jīng)驗池. 若智能體只是貪婪地競爭自己的最優(yōu)策略，經(jīng)過一定博弈輪次的迭代后，基于有偏估計策略梯度迭代后的策略空間將適于每一個智能體各自的最優(yōu)條件. 但是，單一智能體的貪婪并不代表所有智能體的動作集合后的最終系統(tǒng)狀態(tài)指標的綜合評價是最優(yōu)的. 因此，需要引入智能體的合作模型，使得智能體在競爭中亦能平衡自己成本與獎勵的相互權(quán)重，直至混合納什均衡，達到多目標優(yōu)化的效果. 系統(tǒng)對指標的綜合評價越高，智能體對應的獎勵回報值就越高.

當智能體一輪博弈結(jié)束后，對目標函數(shù)2 進行轉(zhuǎn)化有

因此，在博弈的合作模型中，通過博弈輪次結(jié)束后系統(tǒng)指標評價的獎勵回報值和對應的歷史經(jīng)驗池，智能體統(tǒng)一的對策略進行更新，最優(yōu)化自己動作所得到的獎勵回報值與成本回報值. 它們相互合作，每個智能體都在確保自己付出低成本的同時，獲得更高的獎勵回報值.

3.3.1 博弈合作策略更新

本文使用MCTS 算法對多智能體最終評價的獎勵回報值進行策略更新.MCTS作為一種經(jīng)典的啟發(fā)式策略搜索方法，被廣泛用于游戲博弈問題中的行動規(guī)劃［27］. 它基于對搜索空間的隨機探索，利用探索結(jié)果在內(nèi)存中建立了一個初始搜索樹，并且在準確估計最有前途的動作值方面逐漸變得更好.

基于博弈合作的MCTS 包括選舉、模擬、拓展和反向傳播4個步驟，更新過程如圖5所示.

圖5 MCTS流程示意圖

初始狀態(tài)下，所有智能體的成本回報經(jīng)驗池與獎勵歷史池均為空. 智能體按照重構(gòu)的調(diào)度順序進行序貫博弈，每個智能體依據(jù)策略空間不斷模擬，模擬一定輪次后開始擴展，隨著擴展的進行，對已擴展的智能體的策略以選舉的方式選擇動作. 每個輪次結(jié)束后都會計算相應的獎勵回報值方向傳播給所有的智能體. 直到所有智能體都沒有欲望對策略進行更改，獎勵回報值趨于平穩(wěn)，達到混合納什均衡，博弈結(jié)束.

設step ∈[0，Num]代表已經(jīng)博弈擴展的層數(shù)，通常設Num=n，n表示故障軟件數(shù).

（a）選舉：智能體選擇自己策略中最大的偏好值對應的分區(qū)作為調(diào)度的動作.

當step ≥s時，選取當前狀態(tài)策略空間θS中概率最大值即值最大的偏好值作為要執(zhí)行的動作. 否則，進行模擬. 當step=0時，第一層進行模擬.

（b）模擬：智能體依照策略空間的概率分布，依概率選擇動作.

當step ＜s，當前所在的狀態(tài)空間依策略空間θs概率計算后，依概率進行選擇動作，直至到達最后一個狀態(tài)的動作執(zhí)行完后計算Ret值并保存進歷史池. 使用有偏估計量將行為概率對應分布的最大概率向最優(yōu)概率靠近.

（c）擴展：確定該智能體是進行選舉策略還是模擬策略.

在經(jīng)過多次選舉與模擬后，探索層數(shù)加一，即step=step+1，繼續(xù)進行選舉和模擬. 當擴展至最后一層時，所有的智能體選擇的策略都是選舉最大偏好值作為調(diào)度的動作.

（d）反向傳播：依據(jù)系統(tǒng)評價的獎勵回報值，更新博弈過程中所有的智能體所選動作的對應策略偏好值. 未被選中的動作不更新，更新方式為

當step=0時，循環(huán)過程未進行選擇步驟，只進行模擬，且保存模擬后的回報值，表示對空間的初步探索.博弈合作策略更新如算法2所示.

算法2 蒙特卡洛策略梯度收斂策略空間輸入:經(jīng)過算法1迭代后的策略矩陣θ輸出:策略空間θ T={}FOR step=0 to Num:FOR t=0 to N:FOR s in S,S={θ0，θ1，…，θn-1}:IF step ＜s:FOR a in {θs1，θs2，…，θs1+m}:Pra=π(s，a)依概率{Pra in s}選取動作A,A ∈[P1，P1+m]END FOR ELSE:選擇最大θSa 作為動作a,a=Pa,T=T+(s，a)END FOR循環(huán)結(jié)束后計算Ret,且- -----Ret' =1 x top x{Ret1，Ret2，…}FOR(s，a)in T:θSa(t+1)=θSa(t)+γ(Re tt- - -------Re t')(1-π(s，a))END FOR END FOR

3.4 基于序貫博弈的重構(gòu)流程

基于序貫博弈的多智能體強化學習算法流程如圖6所示，在基于應用軟件的優(yōu)先級確定智能體博弈順序后，進行多智能體序貫競爭博弈，目的是盡可能地降低自己動作的成本，在重構(gòu)結(jié)束后，進行多智能體合作博弈，目的是盡可能地提高自己所獲得的獎勵. 若是未滿足終止條件，則重置重構(gòu)狀態(tài)，開啟新一輪的序貫博弈，若是達到設定的終止條件，如達到最大博弈輪次或多智能體間達到混合納什均衡狀態(tài)，任何一個智能體都不再改變自己策略的時候，序貫博弈結(jié)束.

圖6 序貫博弈算法流程

由于系統(tǒng)資源有限，若最終得到的博弈結(jié)果不存在應用軟件由于資源有限，不得不調(diào)度失敗而被犧牲的情況，則重構(gòu)流程結(jié)束. 若存在，則對犧牲應用軟件進行搶占式貪婪博弈. 若搶占后滿足約束條件，則將替換后的應用軟件放入重博弈序列繼續(xù)嘗試搶占，否則換個分區(qū)繼續(xù)嘗試，直至所有分區(qū)均搶占失敗后放入重構(gòu)犧牲集De. 待重博弈序列中所有的應用軟件均搶占失敗后，重構(gòu)流程結(jié)束，如圖7所示.

圖7 重構(gòu)流程

在發(fā)生故障后，會產(chǎn)生待重構(gòu)調(diào)度的應用軟件序列以及可重構(gòu)調(diào)度的分區(qū). 按優(yōu)先級排序后將應用軟件序列轉(zhuǎn)化為多智能體，它們在經(jīng)過序貫博弈后生成的最優(yōu)結(jié)果中，若存在由于資源限制而不得不犧牲的應用軟件，則將犧牲的應用軟件放入重博弈序列進行貪婪博弈. 每個被犧牲的應用軟件都盡可能地嘗試是否可以搶占原系統(tǒng)中狀態(tài)正常的應用軟件. 因為優(yōu)先級越高的應用軟件越應該被優(yōu)先轉(zhuǎn)移，所以待重構(gòu)調(diào)度的應用軟件序列需要按優(yōu)先級進行排序.

4 實驗與性能分析

系統(tǒng)硬件環(huán)境為CPUi7-7700、內(nèi)存16GB，顯卡GTX1070，軟件環(huán)境為Windows10. 實驗旨在分析智能重構(gòu)算法生成高質(zhì)量藍圖的能力. 首先，收集IMA系統(tǒng)的基本配置信息作為實驗的輸入數(shù)據(jù)，如表1、表2 所示. 從初始配置狀態(tài)開始，實驗注入不同的處理器故障，產(chǎn)生不同的重構(gòu)狀態(tài).

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

圖8描繪了所采用的重新配置狀態(tài)的轉(zhuǎn)變，每個節(jié)點代表系統(tǒng)故障后的重構(gòu)狀態(tài). 根據(jù)智能重構(gòu)的8 個環(huán)境遷移情況，對故障情形進行模擬，E0的初始配置信息如表2 所示，E1代表在E0的環(huán)境下C1發(fā)生故障；E3代表在E1的環(huán)境下C2發(fā)生故障；E5代表在E0的環(huán)境下C2、C3發(fā)生故障；E7代表在已經(jīng)發(fā)生C4故障的環(huán)境E2下C2、C5發(fā)生故障.

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

表2 IMA初始E0配置信息

4.2 實驗參數(shù)

根據(jù)實驗環(huán)境設置的IMA 系統(tǒng)初始環(huán)境狀態(tài)與所設8 個不同的故障環(huán)境，設置實驗的基本參數(shù). 實驗參數(shù)如表3 所示，故障應用軟件數(shù)n與可用分區(qū)數(shù)m隨著8個故障環(huán)境的轉(zhuǎn)換而改變. 最大博弈次數(shù)與有偏估計長度則隨著n與m的改變自適應變換. 博弈中競爭與合作的學習率固定為0.01 與0.9. 評價指標的參數(shù)與文獻［17］中的一致.

表3 實驗參數(shù)設置

4.3 算法性能分析

算法性能的對比將比較BE-PGMCTS、PGMCTS、Qlearn 和DE 四種算法的最大回報值和最大值收斂時間，分別在相同最大迭代次數(shù)下對每個算法重復訓練100 次，記錄每次算法內(nèi)部迭代情況、最大值和收斂時間，積累后分別計算其100 次的平均值. 最大回報值越大，說明算法生成的軟件遷移策略即重構(gòu)藍圖的優(yōu)化效果越好，優(yōu)化性能越強. 算法最大值的收斂時間越小，說明在相同故障環(huán)境下算法的收斂性能越好.

不同環(huán)境下不同算法具體的回報值探索曲線如圖9所示，BE-PGMCTS 在E1～E8八個故障環(huán)境中都能最早達到收斂，收斂性能最高. 而PGMCTS 在E1～E4的簡單故障環(huán)境下收斂時間比BE-PGMCTS 略高一點，但是在E5～E8復雜環(huán)境下由于無偏估計計算耗時的增加，其最大值收斂時間也飛速增加，收斂性能不穩(wěn)定.Qlearn 由于自身抖動的因素收斂時間通常較長.DE 算法每次迭代都要嘗試種群內(nèi)所有個體解對應的重構(gòu)藍圖，因此最大值收斂時間通常最大. 具體數(shù)據(jù)如表4所示.

如表4 所示，在資源充足的E1～E6故障環(huán)境下，BEPGMCTS，PGMCTS 和DE 算法所求得的最大回報值基本相同.Qlearn 雖然在單次迭代的算法時延最短，但是探索到的最大回報值往往無法與其他算法媲美，最大值的收斂時間也不占優(yōu).PGMCTS 隨著迭代次數(shù)增加，每次迭代時計算無偏估計的算法時延也增加，從而導致總體的算法收斂時延飛速增加.BE-PGMCTS 由于有偏估計的計算耗時，其單次迭代的算法時延相比Qlearn會稍高一點，但是總體的算法收斂時間最小. 而DE 算法每次迭代都要計算種群中所有個體的回報值，因此算法時延最高.

在因為資源限制而不得不搶占原系統(tǒng)資源的E7、E8故障環(huán)境下，DE 和Qlearn 算法無法保證進入貪婪博弈搶占模式時是最好的狀態(tài)，因此往往無法找到更優(yōu)的重構(gòu)藍圖對應的回報值. 以E8故障環(huán)境為例，BEPGMCTS 和PGMCTS 算法重復100 次的最大回報值平均值都在0.8949 左右，而Qlearn 和DE 僅分別為0.8801和0.8858. 這意味著四種算法在因為資源限制而不得不貪婪搶占式博弈的情況下，Qlearn 和DE 更容易收斂于局部最優(yōu)，而PGMCTS 和BE-PGMCTS 算法可以找到更好的軟件遷移策略對應的重構(gòu)藍圖.

綜上所述，無論在資源充足還是資源不足的情況下，BE-PGMCTS 都可以更為快速地得到最優(yōu)回報值對應的重構(gòu)藍圖，算法收斂時間最小，收斂的最大值最高，因此算法性能最高.Qlearn 和DE 收斂時間較長，容易陷入局部最優(yōu). PGMCTS 在迭代次數(shù)遞增的同時算法計算時延也會飛速提高. BE-PGMCTS 對其做了改進，保證算法時延與迭代次數(shù)是一個遞進的線性關系，在減少不必要的計算耗時的同時亦能保證算法的優(yōu)化效果.

4.4 算法穩(wěn)定性分析

由于在E7，E8復雜故障環(huán)境下四種算法所優(yōu)化的最大回報值差距略為明顯，說明在該環(huán)境下算法所求最大回報值并不穩(wěn)定，存在一定的抖動情況. 因此，為檢驗算法的穩(wěn)定性，重復100次訓練，記錄在E7，E8復雜故障環(huán)境下算法回報值迭代過程中的平均值和最大值的標準差，并計算它們在100 次訓練后的平均值. 其中，平均值為算法開始迭代到算法達到最大值過程的回報值平均值. 最大值標準差越低，說明算法穩(wěn)定性越高，若綜合考慮平均值，則可以看出算法在探索遷移策略時回報值的抖動情況，平均值越高，則越容易陷入局部最優(yōu)，平均值越低，則抖動越明顯. 具體數(shù)據(jù)如圖10所示.

如 圖10 所 示，在E7，E8復 雜 故 障 環(huán) 境 下，BEPGMCTS 和PGMCTS 算法的最大回報值最高，標準差最低，意味著它們的穩(wěn)定性最高. 其中PGMCTS 由于需要付出更多的計算時延去計算無偏估計，其最大回報值會比BE-PGMCTS 的最大回報值略微高一點. DE 算法的平均值最高，標準差略高，但是優(yōu)化效果卻不如BEPGMCTS 和PGMCTS，這意味著其在復雜環(huán)境下容易收斂于局部最優(yōu). Qlearn 算法的標準差最高，平均值最低，說明其一直處于震蕩狀態(tài)很難收斂到最優(yōu)的回報值. 綜合來看，BE-PGMCTS 和PGMCTS 算法都是在改變動作概率分布的同時增加了最大藍圖指標出現(xiàn)的概率，探索性強，優(yōu)化效果好，穩(wěn)定性高.

5 結(jié)論

本文在IMA 系統(tǒng)的重構(gòu)方法中引入了基于序貫博弈多智能體強化學習的方法. 將重構(gòu)中需要調(diào)度的應用軟件定義成一個個單獨的個體，定義其多智能體間的競爭目標與合作目標. 博弈策略的更新算法是在傳統(tǒng)策略梯度算法的基礎上提出基于有偏估計的策略梯度MCTS 算法，解決了傳統(tǒng)策略梯度算法震蕩難收斂、計算耗時長等問題，便于多智能體在不斷序貫博弈的同時可以快速地均衡博弈中競爭的成本與合作的獎勵. 與傳統(tǒng)的智能優(yōu)化算法和強化學習算法作為對比，本文提出的算法有著更好的算法性能與算法穩(wěn)定性.