基于序贯博弈多智能体强化学习的综合模块化航空电子系统重构方法

张 涛，张文涛，代 凌，陈婧怡，王 丽，魏倩茹

（西北工业大学软件学院，陕西西安 710065）

1 引言

在综合模块化航空电子（Integrated Modular Avionics，IMA）系统［1］中，动态重构是一种有效的故障容错方法，已成功被应用于F-22，F-35，A380，B787等飞机航电系统［2］. 重构蓝图定义了受故障影响的各个应用软件的动态迁移与系统资源重配置策略. 在故障发生时，系统将依据所生成重构蓝图对受故障影响的应用软件进行动态迁移，使得应用软件能够恢复正常运行［3，4］. 目前主要针对少数单一故障模式，基于专家经验人工设计重构蓝图，系统故障容错能力有限［5］. 而对于复杂多级交联故障模式，由于系统可用资源限制，需要多个应用软件动态迁移，甚至牺牲低优先级应用软件，使得重构蓝图的人工规划困难［6，7］. 因此，研究自动化生成重构蓝图的方法，是提高IMA系统重构容错能力的关键.

重构蓝图生成需要综合考虑系统负载均衡、重构影响、重构恢复时间和重构降级等多个因素，是一个典型的NP 完全问题［8，9］. 为解决多目标优化的系统重构问题，传统动态规划［10，11］方法以空间换时间，在数据量大时会造成很大的浪费；分支界限算法［12］在单目标优化上有优势但是无法考虑多目标综合优化；模拟退火［13］等启发式算法虽然可解决多目标优化重构调度问题，但却容易陷入局部最优；基于种群进化思想的遗传［14］和差分进化（Differential Evolution，DE）［15］等算法虽然可获得更优重构调度解，但求解时间过长；使用强化学习中的Q 学习［16］在低维重构调度上可以实现快速重构调度，但容易震荡，难以收敛；基于模拟退火的Q学习［17］同时结合了模拟退火和Q 学习的优点，收敛效果更好，但算法迭代的次数多，无法快速求解. 单纯的策略梯度［18］通常采用随机梯度下降的算法方法快速求解，但在算法收敛上具有一定的震荡特性，并且随着迭代次数的增加其无偏估计量的计算耗时也随之增加，导致在迭代次数较大时算法迭代更新速度过慢. 而有偏估计［19］可以有选择地提取历史经验，在有效地减少计算耗时的同时使期望向造成高回报值的动作方向快速偏移. 使用蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）［20］可以在已知策略空间上探索出最优的动作策略，若是策略空间探索不足则容易陷入局部最优.

综上考虑，本文提出一种结合序贯博弈［21］的多智能体强化学习算法来模拟重构应用软件的重构过程，将多目标的优化过程转化为序贯博弈过程中的竞争与合作目标，以优化求解重构蓝图. 重构中每个待调度应用软件均作为一个智能体，各个智能体不仅要争取自身最优条件，而且要满足整体的多目标优化需求，直到达到混合均衡条件［22］或最大博弈次数. 算法首先根据重构应用软件优先级确定其所对应智能体的博弈顺序. 然后每个智能体使用策略梯度，根据各自动作是否满足约束以及满足约束的程度进行自身策略的迭代.接着使用MCTS方法，根据重构后的目标函数值优劣对全部智能体的策略进行更新，从而快速逼近均衡条件.与传统优化算法和传统强化学习算法相比，所提出算法的优化性能和稳定性更优.

2 IMA系统重构

2.1 IMA系统重构架构

在IMA 系统重构架构中，当CPU 发生故障时，需要根据重构蓝图将受故障影响的应用软件迁移到其他CPU，为其重新配置资源，使应用软件恢复正常运行.如图1所示，在CPU2发生故障后，将其分区内的应用软件C 和应用软件D 分别迁移调度到CPU1和CPU3的分区1 与分区5 中. 基于重构蓝图，被牺牲的应用软件和需要迁移的应用软件越少，应用软件功能恢复时间越短，系统负载越均衡，则重构蓝图质量越好.

图1 重构架构示意图

2.2 重构模型

将IMA 系统中的一组CPU 处理器记作C={C1，C2，…，Cb}，其中C代表CPU 的集合，第l个CPU 表示为Cl，b代表CPU 的总数量.b个CPU 中共有m个可用分区，记作P={P1，P2，…，Pm}，其中第j个分区表示为Pj，其属性有分区内存PM 和分区框架时间Td. 分区Pj中部署了软件序列MPj，记为其中分区Pj中部署的第k个应用软件表示为，其属性有内存RAM、优先级Priority、最大运行时间WCET 和截止时间deadline. 在系统故障时，将生成受故障影响软件集，记为D={D1，D2，…，Dn}，其中第i个应用软件表示为Di. 如图2 所示，在分区P2发生故障后，IMA 系统会将部署在该分区的软件D1，D2和D3分别迁移至其他可用分区P4，P1和P5中，使受到影响的软件继续运行. 由于系统重构时需要将受故障影响软件迁移至其他可用的分区中，因此需要计算迁移后分区的CPU 使用率、内存使用率对应的分区负载，确保应用软件的资源可调度性.

图2 重构模型示例图

（

1）分区CPU使用率

分区CPU 使用率体现了分区内应用软件的最大运行时间占用分区框架时间的比例. 具体公式如下所示：

当应用软件Di被调入Pj后，有

其中，WCETDi表示应用软件Di的最大运行时间.

重构可调度性约束1.分区资源限制

当待重构应用软件Di被调入分区Pj后，分区当中的CPU使用率应满足Cuse(Pj，Di)≤Cuse-max.

（2）分区内存使用率

分区内存使用率体现了分区内应用软件的内存占用分区内存的比例. 具体公式如下所示：

当应用软件Di被调入Pj后，有

其中，RAMDi表示应用软件Di的内存容量.

重构可调度性约束2.分区内存限制

当待重构应用软件Di被调入分区Pj后，分区当中的内存应满足调用条件RMuse(Pj，Di)≤RMuse-max.

（3）分区负载

分区负载综合考虑了分区CPU 使用率和分区内存使用率，是对两个指标的统一处理，分区负载越低，意味着该分区应用软件占用的资源越少，分区剩余的资源越多. 具体公式如下所示：

当第Di个应用软件被调入Pj后，有

2.3 应用软件重构问题

结合IMA 系统重构模型，重构中每个待调度的应用软件都期望在成功调度的同时被调入剩余资源最丰富的分区，本文使用式（6）作为应用软件被调入分区后资源丰富情况的数学表达，分区负载越小，代表该分区剩余的资源越多. 设重构影响集I={I1，I2，…，In}为重构过程中系统受影响的软件序列集，初始时重构影响集等于受故障影响的软件集，即I=D.

当影响集I内所有的应用软件被调入分区序列P中 时，设X={[x11，x12，…，x1m+1]，…，[xn1，xn2，…，xnm+1]}，xij表示软件Ii被调入至Pj的分区中.xij=1 表示软件被正常调度，xij=0 表示不进行调度，当xij=1，j=1+m时表示软件Ii被牺牲.

因此，对每个待调度的软件Ii，有目标函数f1：

并且在重构结束后，在满足式（7）约束的情况下，系统期望拥有一个综合评价高的重构蓝图. 针对系统重构后的综合评价，本文借鉴文献［17］中的4 个评价指标，分别改进为表示重构后系统的负载均衡、重构影响度、重构恢复时间和重构降级率4 个指标，定义如下.

（1）负载均衡

负载均衡表示系统资源使用的均衡程度，可以表示重构后系统资源使用的分布情况. 在重构结束后，可以依据所有可用分区的负载计算系统资源的使用均衡程度，由此定义负载均衡指标：

其中，n表示发生故障需要重构的软件数，m表示可调度分区总数表示软件序列I按X调度后所有分区负载均衡的均值.

（2）重构影响度

重构影响度指执行重构后对原系统软件状态的影响程度. 按照软件对系统影响的等级将应用软件的重要性分为五个优先级. 数字越大，应用软件就越重要. 重构应尽量不影响原系统的软件状态，优先级高的软件应该优先被调入，若调入失败，即不满足约束时，应调换出优先级低的软件放入待调度软件序列，同时放入重构影响集I中，若分区中的软件优先级均比待调入软件优先级高，则调度失败，直至所有的分区均无法满足约束，则停止且将该软件放入重构牺牲集De. 设因优先级被调出的软件共k个，则重构影响集I中共有原先序列D中的n个软件和新调出的k个软件. 由此定义重构影响度指标：

其中，Pri 表示软件优先级；nm表示重构牺牲集中的软件个数，即重构后因为可用资源不足而不得不牺牲的软件总数；n+k是重构影响集的个数，表示发生故障的处理器中需要重新配置的软件总数；PriDei表示重构牺牲集中第i个软件的优先集PriIj表示重构影响集中从原系统因优先级低被抢占调出的软件个数.

（3）重构恢复时间

系统重构过程中进程的恢复占据了主要时间，并假设当多个进程位于同一处理器时，重构加载是串行的，重构时间需要累加计算；当多个进程位于不同处理器时，重构加载是并行的，将其中最大的恢复时间作为系统重构时间. 由此定义重构恢复时间指标：

其中，Tmax表示最大重构时间，通常取值为CPU 主框架时间；Ts表示系统重构时间，取IMA 系统内所有处理器的重构恢复时间的最大值，其计算公式为

其中，TCl表示处理器Cl的重构恢复时间，取该处理器内bm个分区中最大的分区重构时间；TPj表示Pj分区内需要重构进程的重构时间和，其计算公式为

其中，Nre表示分区Pj内进行重构加载的进程数量表示进程的重构时间，与进程大小有关.

（4）重构降级率

在IMA 系统的重构过程中，位于故障处理器内的部分进程可能由于系统冗余资源不足、重构时间限制等未能及时完成重构，则定义重构牺牲集De，表示重构结束后仍然剩余不得不被牺牲的软件. 由此定义重构降级率指标：

其中，n'表示重构牺牲集De的进程数，即需要牺牲的进程总数；Nm 表示系统中的全部进程总数表示进程对应的重要等级.

重构结束后蓝图四个指标的值越大，说明重构蓝图的质量越高. 因此，有目标函数f2：

3 序贯博弈强化学习重构方法

3.1 强化学习序贯博弈模型

本文设置的序贯博弈模型是在强化学习常用的马尔科夫决策过程的基础上［23］，由六元组＜G，S，π，A，R，H＞构成.

智能体G：重构中需要调度的每个应用软件定义为一个自主的智能体，它们独立地与环境交互并根据对前面智能体行为的观察采取自己的策略，为自己实现最大收益或最小损失.

状态S：状态为当前系统中所需重构（故障的）的应用软件序列D，以及所有可被调度（正常的）的分区状态序列P与CPU 状态序列C. 设状态S=＜Cs，Ps，Ds，Disp＞，其 中 处 理 器Cs={C1，C2，…，Cb}，分区Ps={P1，P2，…，Pm}和Ds={D1，D2，…，Dn}分 别 代 表可被调度的CPU 序列、可被调度的分区序列和所需重构的应用软件序列. Disp={Di→Pj}代表应用软件进程Di分配到分区Pj的映射［24］关系.

策略π：智能体在当前状态下，选取动作的策略可以表示为以策略空间分布的概率选取分区作为执行动作. 每个智能体在多智能体序贯博弈中遵循自己的策略，旨在当受环境和其他智能体的策略影响时使代理的奖励最大化和成本最小化.

动作A：选取动作的过程其实就是重构中调度的过程，即在当前状态S下选中某个分区，将待调度的应用软件部署到该分区的调度过程. 例如在调度第i个应用软件时，动作A=re ＜Ii，Pj，Cl＞，其中re 表示将应用软件Ii重新部署到Cl处理器中Pj分区. 执行动作A后，状态从St进行更新St→St+1.

回报函数R：本文设计了两个回报函数，分别对应智能体执行动作的成本以及奖励. 将智能体调度动作满足约束的程度作为智能体执行动作的成本回报值，回报值越高，意味着动作成本越少. 在重构中所有智能体所有的动作都执行结束后，对重构后的系统状态做出的综合评价作为智能体们执行动作奖励的回报值，回报值越高，意味着该次重构效果越好.

策略迭代函数H：本文基于两个回报函数设计了两种策略迭代的算法，使用基于强化学习的策略梯度算法和MCTS 算法分别将智能体的成本回报值和总体回报值反馈给智能体的策略，使得策略按着智能体期望的方向趋近更新.

如图3 所示，在博弈t1中，首先由最高优先级软件D1对应的智能体G1在初始状态S0下以策略π1做出动作Aj的选择，即选择将应用软件D1调度到分区Pj.

图3 序贯博弈模型示意图

计算执行该动作的成本回报值后该智能体的策略相应的进行更新，状态也相应的改变为S1. 次一级的智能体需要在上一级智能体的行为结果S1上做出动作选择，直至所有的智能体调度完毕，该次重构结束. 重构结束后对重构后系统进行综合评价，并作为智能体们的奖励，它们对应的策略亦做出更新. 这轮博弈t1结束，接着开启下一轮的博弈t2，直至达到混合纳什均衡或设定的最大博弈数.

3.2 博弈竞争模型

每个智能体是相互独立的，其对动作都有一个相应的策略空间与历史成本经验池. 单个智能体调度动作执行后，所部署分区的CPU 使用率与内存使用率越小，说明该智能体本次重构调度的成本越小，若超过设定的约束值，则该次重构调度不佳.

当智能体Gi对应的应用软件Di选择的动作为调入分区Pj时，对目标函数1进行转化有

因此，在博弈的竞争模型中，通过博弈交互的成本回报值高低和历史的经验池，每个智能体自主执行策略学习，最优化自己动作所得到的回报，不需要考虑其他智能体的回报情况. 它们相互竞争，每个智能体的都旨在优化自己的成本回报值.

3.2.1 博弈竞争策略

重构初始时按应用软件优先级Priority 排列后，确定 调 度 顺 序 为D1≫D2≫…≫Dn，即 智 能 体G1，G2，…，Gn，每个智能体Gi都有自己的博弈策略θi-1，因此构成多智能体的策略矩阵θ（初始时为0矩阵）：

从状态S0开始，重构中每个智能体的调度动作是基于上一个智能体调度产生的新环境执行的，策略更新顺序为θ0≫θ1≫…≫θn-1，所以智能体的策略之间是相互影响的. 并且每个智能体是单一独立且动作离散的，因此可以使用softmax 分布对当前状态S和每个动作即每个待选分区设置一个偏好值，偏好值越大，被选中的概率就越大.

因此，策略π就是一个关于偏好函数的一个函数. 即

Pr(A=a|S)表示在状态S下选择动作a的概率，即在状态S下选择动作a的策略. 初始时，所有的偏好值均为0，即开始时每个动作被选取的概率一样. 因此，有

竞争策略的迭代函数H1：本文中，强化学习策略梯度主要用于智能体竞争策略的更新，策略矩阵θ中每一行向量为每个智能体对应的策略空间. 由式（19）定义优化的成本回报函数作为博弈竞争的优化目标. 这里定义每一智能体的平均回报，即第N轮博弈的第Gi个智能体时，策略πiN下的累计回报ρ(π)：

其中，dπ(S)是基于策略π生成的马尔可夫链关于状态的静态分布，即从S0≫S1≫…≫Sn-1代表智能体G1，G2，…，Gn调度时对应的第1 个应用软件到第n个应用软件所面临的状态；rS t(a)为在S状态下第t次执行a，a∈[1，1+m]动作的回报值. 当N趋近于无穷时，为ρ(π)的无偏估计量. 随着N的增大，无偏估计量的计算时间也增大，为减少计算耗时，可以以一定的比例抽取历史池. 这里使用有偏估计量（表示取N个r里最优的x个的平均值）作为ρ(π)有效的历史池，在牺牲全局最优性的同时，使事件概率分布尽量往历史最优方向靠，增加收敛性.

设存在一个在s状态下依策略π对动作a的期望评价值Qπ(S，a). 则有

此时，有

当确定状态S时，即对应单一智能体时，由式（19）（21）（22）有

详细证明过程可以参考文献［25，26］.

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

即在s状态下，在选择动作a并获得收益后，策略矩阵的偏好值更新方式为

3.2.2 博弈竞争策略更新

本文采用策略梯度算法更新智能体策略，原因是它能够直接优化策略的期望回报，并以循环更新的方式直接在策略空间中迭代最优策略. 在对系统状态环境与对应动作所可能产生的结果一无所知的情况下，使用策略梯度可以快速地让动作策略向趋近于期望方向更新. 博弈竞争策略的更新如图4所示.

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

智能体Gi在第t轮博弈下基于自我的策略πt选择动作at，回报函数根据策略和状态对动作计算回报值并根据策略迭代函数H1进行更新策略，接着状态Si-1对智能体做出的动作进行状态转移，生成新的状态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 博弈合作模型

当重构的所有智能体都调度结束后，系统对指标综合的评价将作为智能体们的奖励，它们共用一个奖励历史经验池. 若智能体只是贪婪地竞争自己的最优策略，经过一定博弈轮次的迭代后，基于有偏估计策略梯度迭代后的策略空间将适于每一个智能体各自的最优条件. 但是，单一智能体的贪婪并不代表所有智能体的动作集合后的最终系统状态指标的综合评价是最优的. 因此，需要引入智能体的合作模型，使得智能体在竞争中亦能平衡自己成本与奖励的相互权重，直至混合纳什均衡，达到多目标优化的效果. 系统对指标的综合评价越高，智能体对应的奖励回报值就越高.

当智能体一轮博弈结束后，对目标函数2 进行转化有

因此，在博弈的合作模型中，通过博弈轮次结束后系统指标评价的奖励回报值和对应的历史经验池，智能体统一的对策略进行更新，最优化自己动作所得到的奖励回报值与成本回报值. 它们相互合作，每个智能体都在确保自己付出低成本的同时，获得更高的奖励回报值.

3.3.1 博弈合作策略更新

本文使用MCTS 算法对多智能体最终评价的奖励回报值进行策略更新.MCTS作为一种经典的启发式策略搜索方法，被广泛用于游戏博弈问题中的行动规划［27］. 它基于对搜索空间的随机探索，利用探索结果在内存中建立了一个初始搜索树，并且在准确估计最有前途的动作值方面逐渐变得更好.

基于博弈合作的MCTS 包括选举、模拟、拓展和反向传播4个步骤，更新过程如图5所示.

图5 MCTS流程示意图

初始状态下，所有智能体的成本回报经验池与奖励历史池均为空. 智能体按照重构的调度顺序进行序贯博弈，每个智能体依据策略空间不断模拟，模拟一定轮次后开始扩展，随着扩展的进行，对已扩展的智能体的策略以选举的方式选择动作. 每个轮次结束后都会计算相应的奖励回报值方向传播给所有的智能体. 直到所有智能体都没有欲望对策略进行更改，奖励回报值趋于平稳，达到混合纳什均衡，博弈结束.

设step ∈[0，Num]代表已经博弈扩展的层数，通常设Num=n，n表示故障软件数.

（a）选举：智能体选择自己策略中最大的偏好值对应的分区作为调度的动作.

当step ≥s时，选取当前状态策略空间θS中概率最大值即值最大的偏好值作为要执行的动作. 否则，进行模拟. 当step=0时，第一层进行模拟.

（b）模拟：智能体依照策略空间的概率分布，依概率选择动作.

当step ＜s，当前所在的状态空间依策略空间θs概率计算后，依概率进行选择动作，直至到达最后一个状态的动作执行完后计算Ret值并保存进历史池. 使用有偏估计量将行为概率对应分布的最大概率向最优概率靠近.

（c）扩展：确定该智能体是进行选举策略还是模拟策略.

在经过多次选举与模拟后，探索层数加一，即step=step+1，继续进行选举和模拟. 当扩展至最后一层时，所有的智能体选择的策略都是选举最大偏好值作为调度的动作.

（d）反向传播：依据系统评价的奖励回报值，更新博弈过程中所有的智能体所选动作的对应策略偏好值. 未被选中的动作不更新，更新方式为

当step=0时，循环过程未进行选择步骤，只进行模拟，且保存模拟后的回报值，表示对空间的初步探索.博弈合作策略更新如算法2所示.

算法2 蒙特卡洛策略梯度收敛策略空间输入:经过算法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循环结束后计算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 基于序贯博弈的重构流程

基于序贯博弈的多智能体强化学习算法流程如图6所示，在基于应用软件的优先级确定智能体博弈顺序后，进行多智能体序贯竞争博弈，目的是尽可能地降低自己动作的成本，在重构结束后，进行多智能体合作博弈，目的是尽可能地提高自己所获得的奖励. 若是未满足终止条件，则重置重构状态，开启新一轮的序贯博弈，若是达到设定的终止条件，如达到最大博弈轮次或多智能体间达到混合纳什均衡状态，任何一个智能体都不再改变自己策略的时候，序贯博弈结束.

图6 序贯博弈算法流程

由于系统资源有限，若最终得到的博弈结果不存在应用软件由于资源有限，不得不调度失败而被牺牲的情况，则重构流程结束. 若存在，则对牺牲应用软件进行抢占式贪婪博弈. 若抢占后满足约束条件，则将替换后的应用软件放入重博弈序列继续尝试抢占，否则换个分区继续尝试，直至所有分区均抢占失败后放入重构牺牲集De. 待重博弈序列中所有的应用软件均抢占失败后，重构流程结束，如图7所示.

图7 重构流程

在发生故障后，会产生待重构调度的应用软件序列以及可重构调度的分区. 按优先级排序后将应用软件序列转化为多智能体，它们在经过序贯博弈后生成的最优结果中，若存在由于资源限制而不得不牺牲的应用软件，则将牺牲的应用软件放入重博弈序列进行贪婪博弈. 每个被牺牲的应用软件都尽可能地尝试是否可以抢占原系统中状态正常的应用软件. 因为优先级越高的应用软件越应该被优先转移，所以待重构调度的应用软件序列需要按优先级进行排序.

4 实验与性能分析

系统硬件环境为CPUi7-7700、内存16GB，显卡GTX1070，软件环境为Windows10. 实验旨在分析智能重构算法生成高质量蓝图的能力. 首先，收集IMA系统的基本配置信息作为实验的输入数据，如表1、表2 所示. 从初始配置状态开始，实验注入不同的处理器故障，产生不同的重构状态.

表1 应用软件属性数据

图8描绘了所采用的重新配置状态的转变，每个节点代表系统故障后的重构状态. 根据智能重构的8 个环境迁移情况，对故障情形进行模拟，E0的初始配置信息如表2 所示，E1代表在E0的环境下C1发生故障；E3代表在E1的环境下C2发生故障；E5代表在E0的环境下C2、C3发生故障；E7代表在已经发生C4故障的环境E2下C2、C5发生故障.

图8 智能重构的环境迁移

表2 IMA初始E0配置信息

4.2 实验参数

根据实验环境设置的IMA 系统初始环境状态与所设8 个不同的故障环境，设置实验的基本参数. 实验参数如表3 所示，故障应用软件数n与可用分区数m随着8个故障环境的转换而改变. 最大博弈次数与有偏估计长度则随着n与m的改变自适应变换. 博弈中竞争与合作的学习率固定为0.01 与0.9. 评价指标的参数与文献［17］中的一致.

表3 实验参数设置

4.3 算法性能分析

算法性能的对比将比较BE-PGMCTS、PGMCTS、Qlearn 和DE 四种算法的最大回报值和最大值收敛时间，分别在相同最大迭代次数下对每个算法重复训练100 次，记录每次算法内部迭代情况、最大值和收敛时间，积累后分别计算其100 次的平均值. 最大回报值越大，说明算法生成的软件迁移策略即重构蓝图的优化效果越好，优化性能越强. 算法最大值的收敛时间越小，说明在相同故障环境下算法的收敛性能越好.

不同环境下不同算法具体的回报值探索曲线如图9所示，BE-PGMCTS 在E1～E8八个故障环境中都能最早达到收敛，收敛性能最高. 而PGMCTS 在E1～E4的简单故障环境下收敛时间比BE-PGMCTS 略高一点，但是在E5～E8复杂环境下由于无偏估计计算耗时的增加，其最大值收敛时间也飞速增加，收敛性能不稳定.Qlearn 由于自身抖动的因素收敛时间通常较长.DE 算法每次迭代都要尝试种群内所有个体解对应的重构蓝图，因此最大值收敛时间通常最大. 具体数据如表4所示.

如表4 所示，在资源充足的E1～E6故障环境下，BEPGMCTS，PGMCTS 和DE 算法所求得的最大回报值基本相同.Qlearn 虽然在单次迭代的算法时延最短，但是探索到的最大回报值往往无法与其他算法媲美，最大值的收敛时间也不占优.PGMCTS 随着迭代次数增加，每次迭代时计算无偏估计的算法时延也增加，从而导致总体的算法收敛时延飞速增加.BE-PGMCTS 由于有偏估计的计算耗时，其单次迭代的算法时延相比Qlearn会稍高一点，但是总体的算法收敛时间最小. 而DE 算法每次迭代都要计算种群中所有个体的回报值，因此算法时延最高.

在因为资源限制而不得不抢占原系统资源的E7、E8故障环境下，DE 和Qlearn 算法无法保证进入贪婪博弈抢占模式时是最好的状态，因此往往无法找到更优的重构蓝图对应的回报值. 以E8故障环境为例，BEPGMCTS 和PGMCTS 算法重复100 次的最大回报值平均值都在0.8949 左右，而Qlearn 和DE 仅分别为0.8801和0.8858. 这意味着四种算法在因为资源限制而不得不贪婪抢占式博弈的情况下，Qlearn 和DE 更容易收敛于局部最优，而PGMCTS 和BE-PGMCTS 算法可以找到更好的软件迁移策略对应的重构蓝图.

综上所述，无论在资源充足还是资源不足的情况下，BE-PGMCTS 都可以更为快速地得到最优回报值对应的重构蓝图，算法收敛时间最小，收敛的最大值最高，因此算法性能最高.Qlearn 和DE 收敛时间较长，容易陷入局部最优. PGMCTS 在迭代次数递增的同时算法计算时延也会飞速提高. BE-PGMCTS 对其做了改进，保证算法时延与迭代次数是一个递进的线性关系，在减少不必要的计算耗时的同时亦能保证算法的优化效果.

4.4 算法稳定性分析

由于在E7，E8复杂故障环境下四种算法所优化的最大回报值差距略为明显，说明在该环境下算法所求最大回报值并不稳定，存在一定的抖动情况. 因此，为检验算法的稳定性，重复100次训练，记录在E7，E8复杂故障环境下算法回报值迭代过程中的平均值和最大值的标准差，并计算它们在100 次训练后的平均值. 其中，平均值为算法开始迭代到算法达到最大值过程的回报值平均值. 最大值标准差越低，说明算法稳定性越高，若综合考虑平均值，则可以看出算法在探索迁移策略时回报值的抖动情况，平均值越高，则越容易陷入局部最优，平均值越低，则抖动越明显. 具体数据如图10所示.

如 图10 所 示，在E7，E8复 杂 故 障 环 境 下，BEPGMCTS 和PGMCTS 算法的最大回报值最高，标准差最低，意味着它们的稳定性最高. 其中PGMCTS 由于需要付出更多的计算时延去计算无偏估计，其最大回报值会比BE-PGMCTS 的最大回报值略微高一点. DE 算法的平均值最高，标准差略高，但是优化效果却不如BEPGMCTS 和PGMCTS，这意味着其在复杂环境下容易收敛于局部最优. Qlearn 算法的标准差最高，平均值最低，说明其一直处于震荡状态很难收敛到最优的回报值. 综合来看，BE-PGMCTS 和PGMCTS 算法都是在改变动作概率分布的同时增加了最大蓝图指标出现的概率，探索性强，优化效果好，稳定性高.

5 结论

本文在IMA 系统的重构方法中引入了基于序贯博弈多智能体强化学习的方法. 将重构中需要调度的应用软件定义成一个个单独的个体，定义其多智能体间的竞争目标与合作目标. 博弈策略的更新算法是在传统策略梯度算法的基础上提出基于有偏估计的策略梯度MCTS 算法，解决了传统策略梯度算法震荡难收敛、计算耗时长等问题，便于多智能体在不断序贯博弈的同时可以快速地均衡博弈中竞争的成本与合作的奖励. 与传统的智能优化算法和强化学习算法作为对比，本文提出的算法有着更好的算法性能与算法稳定性.