基于序貫博弈多智能體強(qiáng)化學(xué)習(xí)的綜合模塊化航空電子系統(tǒng)重構(gòu)方法

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

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

1 引言

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

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

綜上考慮，本文提出一種結(jié)合序貫博弈［21］的多智能體強(qiáng)化學(xué)習(xí)算法來模擬重構(gòu)應(yīng)用軟件的重構(gòu)過程，將多目標(biāo)的優(yōu)化過程轉(zhuǎn)化為序貫博弈過程中的競爭與合作目標(biāo)，以優(yōu)化求解重構(gòu)藍(lán)圖. 重構(gòu)中每個(gè)待調(diào)度應(yīng)用軟件均作為一個(gè)智能體，各個(gè)智能體不僅要爭取自身最優(yōu)條件，而且要滿足整體的多目標(biāo)優(yōu)化需求，直到達(dá)到混合均衡條件［22］或最大博弈次數(shù). 算法首先根據(jù)重構(gòu)應(yīng)用軟件優(yōu)先級(jí)確定其所對(duì)應(yīng)智能體的博弈順序. 然后每個(gè)智能體使用策略梯度，根據(jù)各自動(dòng)作是否滿足約束以及滿足約束的程度進(jìn)行自身策略的迭代.接著使用MCTS方法，根據(jù)重構(gòu)后的目標(biāo)函數(shù)值優(yōu)劣對(duì)全部智能體的策略進(jìn)行更新，從而快速逼近均衡條件.與傳統(tǒng)優(yōu)化算法和傳統(tǒng)強(qiáng)化學(xué)習(xí)算法相比，所提出算法的優(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)中，當(dāng)CPU 發(fā)生故障時(shí)，需要根據(jù)重構(gòu)藍(lán)圖將受故障影響的應(yīng)用軟件遷移到其他CPU，為其重新配置資源，使應(yīng)用軟件恢復(fù)正常運(yùn)行.如圖1所示，在CPU2發(fā)生故障后，將其分區(qū)內(nèi)的應(yīng)用軟件C 和應(yīng)用軟件D 分別遷移調(diào)度到CPU1和CPU3的分區(qū)1 與分區(qū)5 中. 基于重構(gòu)藍(lán)圖，被犧牲的應(yīng)用軟件和需要遷移的應(yīng)用軟件越少，應(yīng)用軟件功能恢復(fù)時(shí)間越短，系統(tǒng)負(fù)載越均衡，則重構(gòu)藍(lán)圖質(zhì)量越好.

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

2.2 重構(gòu)模型

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

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

（

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

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

當(dāng)應(yīng)用軟件Di被調(diào)入Pj后，有

其中，WCETDi表示應(yīng)用軟件Di的最大運(yùn)行時(shí)間.

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

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

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

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

當(dāng)應(yīng)用軟件Di被調(diào)入Pj后，有

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

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

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

（3）分區(qū)負(fù)載

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

當(dāng)?shù)贒i個(gè)應(yīng)用軟件被調(diào)入Pj后，有

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

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

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

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

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

（1）負(fù)載均衡

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

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

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

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

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

（3）重構(gòu)恢復(fù)時(shí)間

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

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

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

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

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

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

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

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

3 序貫博弈強(qiáng)化學(xué)習(xí)重構(gòu)方法

3.1 強(qiáng)化學(xué)習(xí)序貫博弈模型

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

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

狀態(tài)S：狀態(tài)為當(dāng)前系統(tǒng)中所需重構(gòu)（故障的）的應(yīng)用軟件序列D，以及所有可被調(diào)度（正常的）的分區(qū)狀態(tài)序列P與CPU 狀態(tài)序列C. 設(shè)狀態(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)的應(yīng)用軟件序列. Disp={Di→Pj}代表應(yīng)用軟件進(jìn)程Di分配到分區(qū)Pj的映射［24］關(guān)系.

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

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

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

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

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

圖3 序貫博弈模型示意圖

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

3.2 博弈競爭模型

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

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

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

3.2.1 博弈競爭策略

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

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

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

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

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

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

設(shè)存在一個(gè)在s狀態(tài)下依策略π對(duì)動(dòng)作a的期望評(píng)價(jià)值Qπ(S，a). 則有

此時(shí)，有

當(dāng)確定狀態(tài)S時(shí)，即對(duì)應(yīng)單一智能體時(shí)，由式（19）（21）（22）有

詳細(xì)證明過程可以參考文獻(xiàn)［25，26］.

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

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

3.2.2 博弈競爭策略更新

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

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

智能體Gi在第t輪博弈下基于自我的策略πt選擇動(dòng)作at，回報(bào)函數(shù)根據(jù)策略和狀態(tài)對(duì)動(dòng)作計(jì)算回報(bào)值并根據(jù)策略迭代函數(shù)H1進(jìn)行更新策略，接著狀態(tài)Si-1對(duì)智能體做出的動(dòng)作進(jìn)行狀態(tài)轉(zhuǎn)移，生成新的狀態(tài)Si，并傳遞給下一個(gè)智能體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}選取動(dòng)作a,a ∈[P1，P1+m]依動(dòng)作由式(16)計(jì)算此次動(dòng)作的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 博弈合作模型

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

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

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

3.3.1 博弈合作策略更新

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

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

圖5 MCTS流程示意圖

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

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

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

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

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

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

（c）擴(kuò)展：確定該智能體是進(jìn)行選舉策略還是模擬策略.

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

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

當(dāng)step=0時(shí)，循環(huán)過程未進(jìn)行選擇步驟，只進(jìn)行模擬，且保存模擬后的回報(bào)值，表示對(duì)空間的初步探索.博弈合作策略更新如算法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}選取動(dòng)作A,A ∈[P1，P1+m]END FOR ELSE:選擇最大θSa 作為動(dòng)作a,a=Pa,T=T+(s，a)END FOR循環(huán)結(jié)束后計(jì)算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)流程

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

圖6 序貫博弈算法流程

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

圖7 重構(gòu)流程

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

4 實(shí)驗(yàn)與性能分析

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

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

圖8描繪了所采用的重新配置狀態(tài)的轉(zhuǎn)變，每個(gè)節(jié)點(diǎn)代表系統(tǒng)故障后的重構(gòu)狀態(tài). 根據(jù)智能重構(gòu)的8 個(gè)環(huán)境遷移情況，對(duì)故障情形進(jì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í)驗(yàn)參數(shù)

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

表3 實(shí)驗(yàn)參數(shù)設(shè)置

4.3 算法性能分析

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

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

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

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

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

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

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

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

5 結(jié)論

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