基于改进Q学习的IMA系统重构蓝图生成方法

2021-10-22罗庆张涛单鹏张文涛刘子豪

航空学报 2021年8期

关键词：模拟退火蓝图分区

罗庆，张涛，单鹏，张文涛，刘子豪

1. 航空工业沈阳飞机设计研究所，沈阳 110035

2. 南京航空航天大学航天学院，南京 210016

3. 西北工业大学软件学院，西安 710072

4. 航空工业西安航空计算技术研究所，西安 710065

模块化航空综合电子系统(Integrated Modular Avionics, IMA)具有低成本、低功耗等显著优势[1-2]。随着航空电子系统功能急剧增加，IMA系统结构愈加复杂，安全可靠性风险增大。当系统故障时，通过对软件和硬件资源的重构配置，以容错保证系统功能和性能要求[3-4]。

传统重构方法采用基于模拟退火算法[5]、遗传算法[6]等启发式算法[7]预先训练生成的重构蓝图，在飞行过程出现故障时，根据预先加载重构蓝图，进行系统重构容错[8-9]。现有方法所生成的重构蓝图，收敛速度慢，难以生成最优蓝图。

本文研究基于强化学习的重构蓝图动态生成方法，直接与环境交互训练学习，并利用强化学习中时间差分的特性积累重构经验[10-11]，对多目标进行优化[12-13]，从而快速生成高质量重构蓝图，提高综合电子系统重构容错能力。本文提出方法的主要贡献如下。

1) 不仅考虑了综合电子系统重构的基本资源约束，并且实现了负载均衡、重构影响、重构时间、重构降级的多目标优化，保证重构蓝图质量。

2) 采用模拟退火框架改进Q学习搜索策略，提高了蓝图生成算法在最优解的收敛性，以及算法效率。

1 相关工作

在重构系统建模方面，Cui等[14]基于向后重构的概念提出了一种分散式重构技术，利用分散化使系统更快地适应计算机模块中已识别的故障，但增加了系统中每个节点的复杂性；Wang等[15]提出了一种基于有限状态机理论和故障逻辑的系统可靠性建模与验证方法；Wei等[16]提出了一种基于AADL(Architecture Analysis and Design Language)模型的综合电子系统安全关键软件重构方法，使用扩展的错误模型和危险模型附件建模操作行为和错误行为，检测故障和危险的发生。

在重构分析方面，Pourmohseni等[17]提出了一种确定性映射重构方法，该方法能够分析最坏情况下的重构延迟，从而实现给定的一组映射集之间的可预测重构；Zhang等[18]提出了一种描述组件错误状态转换、系统架构和重构行为的建模方法，并设计模型转换规则来建立可计算模型，分析其重构后应用的可调度性；Da Fontoura等[19]提出了用于故障管理的重构方法及时序分析的模型检查方法，能够在满足设计时序约束的前提下评估所有可预见的情况，但时序分析的速度和有效性有待提高。

综上所述，当前重构技术研究主要集中在系统建模和分析验证方面，对于重构蓝图生成方法研究较少。因此，如何高效生成高质量重构蓝图成为亟需解决的问题。

2 IMA系统的智能重构方法

根据IMA组成和特点，建立了IMA系统模型，给出了系统重构资源约束和评价指标，定义了多目标优化函数，最后设计了重构蓝图的智能生成算法。

2.1 IMA系统模型

如图1所示，IMA可以简化为集中式硬件结构。其中，一个IMA机箱包含多个处理器模块，每个处理器模块可设置多个任务分区，每个任务分区中可部署一个或多个应用软件，不同处理器之间通过通信总线相互连接。

图1 系统简化示意图

在IMA系统中，基于资源共享的思想[20]，将硬件资源抽象地转化为逻辑模块。因此，结合硬件和软件需求，这里分别建立应用软件M、分区P和处理器C模型。

2.2 基本约束与优化指标

1) 重构约束

首先定义基本约束，以筛选出有效的系统重构蓝图。在时间方面，IMA系统的每个分区在处理器内都有固定的开始时间和执行时间。一个分区中的所有应用软件必须在规定的运行时间内完成。在内存方面，应用软件占用的内存总和不得超过该分区的可用内存。

2) 优化指标

在基本资源约束基础之上，定义重构蓝图评价指标，以进一步优选出高质量的重构蓝图。这里定义了负载均衡、重构影响、重构时间和重构降级等4个优化评价指标。

① 负载均衡

负载均衡可以提高应用软件的执行速度。利用标准差来衡量各分区荷载的离散程度。因此，LB计算公式为

(1)

(2)

② 重构影响

重构影响是指系统重构对应用的影响，主要衡量应用软件重新配置的成功率。这里将应用软件重要性分为五级：1～5级。数字越大，应用软件越重要。因此，In的计算公式为

(3)

式中：nM表示成功完成重新配置的应用软件数；NM表示发生故障的处理器中需要重新配置的应用软件总数；GMi为应用Mi的重要等级。

③ 重构时间

重构时间是完成所有应用软件迁移重构的时间。在重构时，各个处理器同时根据重构蓝图顺序加载其应用软件。因此，各个处理器重构时间为其需要加载应用时间之和。而IMA系统重构时间则是所有处理器最长加载时间。

系统重构时间Tre定义为

(4)

式中：Tmax表示最大重新配置时间；TCk表示处理器Ck的重构恢复时间，定义为

(5)

式中：Nre表示在处理器Ck中重新加载的应用软件数；TMi为应用软件Mi的重新配置时间，取决于应用软件大小。

④ 重构降级

重构降级表示当系统冗余资源不足时，牺牲低优先级应用来恢复高优先级应用。主要衡量重构后系统应用功能完整性。De的定义为

(6)

式中：nf表示无法重新配置需要牺牲的应用软件的总和；nM表示重构系统中的应用软件总数。

3) 多目标优化函数

综合基本约束和优化评价指标，这里设定多目标优化函数为

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

(7)

2.3 重构蓝图生成算法

本文通过改进Q学习方法，智能生成综合电子系统重构蓝图。首先定义了重构蓝图Q学习的基本要素，包括状态、动作、策略、回报函数、状态-动作函数等。然后提出了一种Q学习结合模拟退火的蓝图生成算法框架。

1)Q学习基本要素

① 状态s

将系统重构过程的配置蓝图定义为Q学习的状态元素s，其定义为

(8)

式中：Cs={C1,C2,…,Cn}、Ps={P1,P2,…,Pm}和Ms={M1,M2,…,Ml}分别表示处理器集合、分区集合和应用软件集合；Bind={Mi→Pj→Ck}是应用程序在分区和处理器上的映射信息[21]。

② 动作a

动作a定义为将应用软件重新配置到新的处理器分区，即

a=re

(9)

式中：re表示将应用Mi重新部署到处理器Ck中的分区Pj。选择动作后从旧状态到新状态的转换函数定义如下：

(10)

③ 策略π

策略是指从配置状态的动作空间中选择动作的方法。这里选择了一种平衡探测和收敛的贪婪策略作为重构策略。该策略依概率ε随机选择动作空间里的动作，或依概率1-ε选择当前状态下具有最高状态Q值的动作。策略π的定义为

(11)

式中：argmaxaQ(s,a)表示使得状态Q值最高的动作。为使策略在充分探索的同时又具有收敛性，对ε采用指数衰减化处理：

(12)

式中：N表示总探索次数；t为当前探索次数，初始时，ε=1。

④ 回报函数R

回报函数R用于在重构动作后对新的配置蓝图进行评估。如果在执行应用软件重构动作a之后，当前配置状态si变为新状态si+1，那么必须提供一个评估新状态si+1、好坏的奖励信号。

本文根据状态si+1将奖赏分为3种情况：第一，如果si+1不满足资源约束，则对错误动作给予负奖赏；第二，如果满足资源约束，但系统还未重构完成，则不给予奖励；第三，如果si+1满足资源约束，并且已经完成系统重构，将通过多目标优化函数给予正奖励。因此，回报函数定义为

(13)

式中：R(s,a)表示在系统重构s中选择重构动作a的回报；LB、In、De和Tre分别表示负载均衡指标、重构影响指标、重构降级指标和重构时间指标。这4个指标的权重分别表示为λ1、λ2、λ3和λ4。

⑤ 状态-动作函数Q(s,a)

状态-动作函数Q(s,a)表示从状态s出发，执行动作a并再使用策略π后带来的累计奖赏。

Q值的迭代计算公式定义为

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

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

(14)

式中：QNew(s,a)表示通过在系统配置s中执行动作a获得的新的Q值；Q(s,a)为当前s对应动作a的Q值；α和γ分别表示学习率和奖励衰减；maxQ′(s′,a′)表示在新的重新配置状态s′中，通过采取行动a′获得的最大状态值函数。

2) 算法机制

这里引入模拟退火思想，将模拟退火中扰动解步骤改为应用Q学习算法生成新解，即新的Q表。如图2所示，算法会生成初始为0的Q表，并计算其回报R值作为最大回报值Rmax。通过Q学习算法进行Q表扰动产生新的Q表与新的R值后，计算其差值。若新的R值大于旧Rmax，则接受新的Q表，并更新Rmax。否则按Metropolis准则[22]接受新Q表。

图2 算法流程图

将新的R值放入历史池，判断是否满足终止条件，通常设终止条件为温度到达最小值或历史池趋于稳定时停止算法。若不满足终止条件，则缓慢减低温度后继续算法，温度即为Q学习中的探索度ε。

如图2所示，在模拟退火框架中，采用Q学习中状态-动态函数的迭代公式计算扰动解，并将Q学习算法中探索策略的探索度ε与模拟退火中的温度结合，使探索度能逐渐减为最小温度，直至算法结束。改进后的算法如算法1所示。其中:M为应用序列;P为分区序列;C为CPU序列；N为探索总次数。随着探索次数t的增加，探索度ε逐渐减少为0，算法逐渐达到收敛状态。算法中，探索度亦为温度。

算法1 模拟退火Q学习算法输入: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=当前状态的动作空间随机选一个作为调度分区 Else a=当前状态的动作空间选一个最高Q值作为根据所选动作调度分区计算R(s,a) If s min(pool) Q(s,a)=Q'(s,a) pool.append(R(s,a)) t+=1 End

3 仿真实验

基于上述算法描述，将基于模拟退火的改进Q学习算法(SA_Qlearn)进行仿真实验，测试其不同指标权重和不同超参对仿真效果的影响。选择效果最好的参数实验算法在不同环境下的结果。并引入模拟退火、差分进化、Q学习等算法进行对比，分析本文所提出算法的收敛性能和算法效率。

3.1 仿真实验设置

实验设定的IMA系统硬件与软件应用基本配置如表1和表2所示。如图3所示，从初始配置S0开始，通过依次注入不同的处理器故障，产生不同的重构配置。图3中每个节点Si代表系统发生故障后的重构配置，例如S1是在S0发生C1故障后的重构配置，S7是在S0下同时发生C2、C3故障后的重构配置。

表1 软件应用属性数据

表2 IMA初始S0配置信息

图3 智能重构的环境迁移

3.2 指标权重分析

在多目标优化过程中，各个优化指标的不同权重系数值，对应着不同的收敛倾向。权重越高，收敛倾向越高。指标间的相关性如图4所示。

图4为S7复杂环境下的指标相关性热力图，其中指标的权重分配为0.25、0.25、0.25、0.25。从图4可以看出，负载均衡LB与重构影响In、重构降级De承0.35的相关性，与重构时间基本没有相关性。重构影响In、重构降级De之间相互为1的强相关性，与重构时间呈-0.31弱负相关性。

图4 S7环境下指标间热力相关图

如表3所示，为验证不同权重参数值对训练结果的影响，以S7重构配置环境生成为例，实验分析各个优化指标权重对训练收敛的影响。

表3 S7环境下不同权重λ的训练结果

从表3可以看出，若λ1或λ4的取值高于0.25，会发现最优值很难高于0.9，并且迁移结果存在牺牲。在λ2或λ3取0.3以上时，若λ1取值高于λ4，则收敛难度增加，最终收敛结果并不趋向于最优解。根据以上分析，优化目标权重分别取为：λ1=0.1、λ2=0.35、λ3=0.35、λ4=0.2。

3.3 学习率与奖励衰减分析

不同的学习率α、与奖励衰减γ也会对优化训练过程产生影响。如图3所示，在确定奖励衰减γ=0.9的情况下，取不同的学习率进行训练。图5、图6中曲线是以每50项为基的滑动平均线。其中图5对比了在S7环境下α=0.01，0.1，0.5，0.9等不同学习率对学习曲线的效果。

图5 S7环境下不同学习率对回报值的影响

图5中学习率α=0.01时蓝色曲线上升的幅度最大且最终收敛的回报值最高。学习率越大，越容易过拟合，导致最后收敛回报值越低。

为验证奖励衰减γ对优化训练过程产生的影响。如图6所示，在确定学习率α=0.01的情况下，取不同的奖励衰减进行训练。这里对比了在S7环境下γ=0.1、γ=0.4、γ=0.9、γ=1等不同奖励衰减对学习曲线的效果。

图6 S7环境下不同奖励衰减对回报值的影响

图6中曲线上升的幅度相差不大，其中奖励衰减γ=0.9时绿色曲线最终收敛的回报值最高。奖励衰减越大，后续的奖励占比越大。当γ=1时容易造成过拟合。

根据以上分析，实验中取α=0.01、γ=0.9。

3.4 实验结果

基于3.2与3.3节目标权重与训练参数的选择，对图7中不同的环境使用基于模拟退火的Q学习算法进行训练。

如图7所示，其中淡蓝色曲线表示10 000次真实探索情况对应的回报值的更新曲线，黄色曲线表示真实更新曲线中以每10次探索为单位的滑动平均趋势曲线。并且根据黄色曲线可以看出探索的趋势会随着探索度ε的减少而收敛于最优。其中，即使是在S6无可行解的环境下(必须牺牲应用时，回报值无法大于0.9)，亦能找到使牺牲应用代价最小的动作解而收敛到最优。

3.5 实验分析

本文将所提出算法(SA_Qlearn)与模拟退火算法(SA)、差分进化算法(DEA)、传统Q学习算法(Qlearn)等常用多目标优化算法相比较，以分析验证所提出算法效率与收敛性能[23-27]。

1) 算法效率

以10 000次为最大迭代次数，分别记录不同算法迭代用时与最终的收敛回报值。

如图8所示，显示了4种算法在8种重构环境下10 000次迭代的求解时间。其中，由于DEA所用时间相对过长，为显示其他3种算法的时间对比，对其真实求解时间乘以0.05。由于每次迭代都要计算种群中所有的解并且做出解的扰动，即使在缩小真实值的情况下，DEA的求解时间依然最大。而SA、Qlearn和SA_Qlearn这3种算法是无种群的线性迭代，因此这3种算法之间求解时间相差不大，Qlearn最小，SA_Qlearn次之，SA相对最大。