基于矩阵的运载火箭测试优化方法

黄子惟，马小龙

（北京宇航系统工程研究所，北京，100076）

0 引言

为考核运载火箭复杂系统的性能，必须对其进行全面的测试，现有的测试方法主要采用分层测试的方式，将系统分为子系统，然后分别进行测试，最后再测试整个系统［1］。然而，这种方法存在局限性，包括状态转换耗时长、受约束多、无法充分考虑所有潜在故障通路等。

为了克服这些问题，需要采用更先进的测试方法来提高测试效率并降低测试成本。一个有效的方法是将测试项目与故障建立有向图模型，以矩阵形式建立关联，矩阵即成为测试的数学模型，计算故障检出率、系统测试性、查找冗余测试等工作可以转化为矩阵计算和矩阵优化的问题。采用列消元法检测冗余测试，用最小路径覆盖算法来检测最小测试，用割点算法来确定测试项目的关键程度，从而帮助制定更高效的测试策略。采用AO*算法进行矩阵优化，可以简化测试过程，提高测试效率［2］。

1 总体分析

1.1 测试流程分析

测试流程如图1所示，可以分为以下步骤［3］：

图1 测试流程Fig.1 Test model flow block diagram

a）分析测试需求。根据系统的功能要求、性能指标、安全性等需求形成需求说明书，据此制定测试计划，以确保测试的全面性和有效性。

b）制定测试计划。制定测试计划应该包括测试的范围、测试的目标、测试的计划安排、测试资源和测试方法。在制定测试计划时，需要考虑系统的复杂性和测试的覆盖性，确保测试计划能够覆盖系统的各个方面。

c）设计测试项目。应该根据需求分析和测试计划设计测试项目。测试项目应该包括正常情况、冗余测试、边界测试等，测试项目应该可重复执行，便于测试系统对输入反馈的一致性，同时应搭建尽可能接近真实的测试环境。

d）执行测试。在测试执行阶段，应该按照测试计划和测试项目，编写测试脚本并执行自动化测试。

e）测试管理。测试执行后，应该对测试中发现的缺陷进行分类和跟踪管理，未通过测试的项目应根据测试结果修改完成后执行回归测试，直至测试合格为止。

f）测试报告。应该对测试结果进行分析和总结，根据测试结果和问题管理情况生成测试报告。

1.2 有向图

有向图是一种形式化的建模方法，用于描述系统中各个组件之间的因果依赖关系［4］。如图2所示，由节点和边组成的有向图，其中节点表示系统中的测试项目，边表示这些项目之间的因果依赖关系。有向图可以用于系统可测试性分析和故障诊断，通过对因果依赖关系进行建模和分析，可以实现高效的故障隔离和诊断。多信号有向图可以用来生成测试序列，并进行复杂系统的可测试性分析。也可以通过“模型驱动”的方法，直接根据系统的设计模型生成有向图。

图2 测试有向图Fig.2 Testing directed graphs

1.3 依赖矩阵

依赖矩阵可以用来描述系统中故障和测试项目之间的依赖关系，进而用于分析测试相关特性、优化测试设计［5］。

有向图向依赖矩阵转化的方法：

a）确定所有的节点，并为每个节点分配一个唯一的标识符，例如用整数来表示；

b）根据节点的数量创建一个空的矩阵，这个矩阵的大小为N*N，其中N为节点的数量；

c）标记依赖关系，根据图形中的边，标记矩阵中的元素，如果节点i依赖于节点j，则矩阵中第j行第i列的元素为1，否则为0。

依赖矩阵的形式为

如式（1）所示，依赖矩阵可以帮助确定系统中各个信号之间的依赖关系，因此可以精确地检测系统中的故障。当系统中某个信号出现故障时，它可能会影响到其他信号的计算结果，进而影响系统的正确性和性能。依赖矩阵定位故障所在的信号，进而进行修复。依赖矩阵可以根据系统中的信号数目进行扩展，因此可以适应从单机测试到总体测试的不同规模测试场景。

2 矩阵分析

2.1 列消元法

通过对依赖矩阵进行列消元，可以确定哪些测试是冗余的［6］。这些测试可以被删除或替换为更有效的测试。列消元法利用依赖矩阵的列之间的线性关系，将其中一些列表示为其他列的线性组合形式，从而消除冗余信息。具体来说，列消元法可以分为以下步骤：

a）构造增广矩阵。将依赖矩阵和一个单位矩阵按列合并，构造出一个增广矩阵。

b）列主元消元。对增广矩阵进行列主元消元，将其转化为行最简形式，在进行消元操作时，需要选取每一列中绝对值最大的元素作为主元素，将其他元素通过行变换转化为零。

c）提取基本列。将行最简形式的增广矩阵按列划分为2个矩阵，其中左边的矩阵为依赖矩阵的行最简形式，右边的矩阵为单位矩阵的行最简形式。此时左边矩阵中不为零的列就是依赖矩阵的基本列，其他列则可以表示为基本列的线性组合形式。

通过列消元法，可以将依赖矩阵中的冗余信息消除，提取出基本列，从而减少矩阵的维度，用于优化测试用例的选择和生成，减少冗余测试，从而提高测试效率和覆盖率。

2.2 最小路径覆盖算法

通过将依赖矩阵转换为一个有向无环图，可以使用最小路径覆盖算法来确定最少需要多少个测试来覆盖所有可能的故障。可以使用Python将矩阵转换为有向无环图［7］，示例依赖矩阵M形式为

图3为示例依赖矩阵M转换后的有向无环图。能更清楚地展示任务之间的依赖、顺序和流程。可以更好地理解和分析任务之间的依赖关系，从而有助于进行优化和决策。

图3 有向无环图Fig.3 Directed acyclinc graph

路径覆盖是指一组不相交的简单路径，这些路径覆盖了图中的所有顶点，即每个顶点恰好在一条路径上。最小路径覆盖就是指路径覆盖中包含最少路径数的覆盖方案。

最小路径覆盖算法可以通过以下步骤实现：

a）构造二分图。将有向无环图转换为一个二分图，如图4所示，其中左部节点对应图4中的所有源节点，右部节点对应所有的汇节点。对于图4中的每个边(u，v)，将其转换为一条从u对应的左部节点到v对应的右部节点的边。

图4 二分图Fig.4 Bipartite graph

b）求二分图的最大匹配。对于上一步构造的二分图，求出它的最大匹配。最大匹配是指二分图中包含最多边的一个匹配，可以使用匈牙利算法、Hopcroft-Karp算法等常用的最大匹配算法进行求解。

c）构造路径覆盖。将最大匹配中的匹配边分解为若干条不相交的简单路径，这些路径即为路径覆盖。在构造过程中，可以使用深度优先搜索或广度优先搜索等算法。

d）计算最小路径覆盖。计算得到的路径覆盖所包含的路径数即为最小路径覆盖的路径数。

2.3 割点算法

通过将依赖矩阵转换为一个无向图，并使用割点算法来确定哪些测试是关键测试，这些关键测试可以提高故障诊断的准确性和效率［8］。

割点也被称为关键节点或割点节点，是指如果将该节点从图中删除，会导致图不连通的节点，如图5所示。

图5 割点算法Fig.5 Cut point algorithm

割点算法是基于深度优先搜索（Depth-first Search，DFS）开展的，割点算法可以通过以下步骤实现：

a）对于每个节点v∈V，假设其在DFS 树中的父节点为u，如果节点v在DFS 树中没有子节点或者子节点的后代节点中没有回到节点v的，则节点u为割点。

b）如果节点v在DFS树的根节点处，且有2个或2个以上的子节点，则节点v为割点。

割点算法的时间复杂度为O（V+E），其中V和E分别为图的顶点数和边数。

3 优化依赖矩阵

使用AO*算法优化依赖矩阵是一个常用的方法。具体而言，AO*算法从起点开始搜索，每次选择距离起点最近的未扩展节点进行扩展。在扩展节点时，AO*算法计算节点到终点的估价函数值，将其作为节点的优先级，以选择下一个要扩展的节点。如果当前节点到终点的路径长度已经超过当前最优路径长度，则将当前节点标记为不可达，不再进行扩展，直到找到终点或者所有可达节点都被扩展完成，AO*算法才停止搜索，并返回最短路径和路径长度。

3.1 估价函数及其优化

根据依赖矩阵的特性，采用估价函数来估计从当前状态到达目标状态的代价，以便更快地搜索到最优解。若定义估价函数为路径的总长度或总代价，路径长度可以表示任务的执行时间、资源投入、可靠性等，最优解通常为使路径总长度最小的路径集合。估价函数的优点是可以比较准确地预测当前节点到终点的距离。

加权平均法是一种组合估价函数的方法，可以将多个估价函数进行加权平均，得到一个更加准确的估价函数。在优化AO*算法的估价函数时，可以采用加权平均法来得到更加优化的估价函数［9］。

具体而言，定义m个估价函数f1（n），…，fm（n），然后采用加权平均的方式将它们组合成一个新的估价函数f(n)。加权平均法的计算公式为

式中w1，…，wm分别表示估价f1(n)，…，fm(n)的权重，满足w1+… +wm=1。

在应用加权平均法优化AO*算法的估价函数时，选择不同的估价函数作为组合的基础，可以根据测试时间长度和测试资源投入设计2 个估价函数f1(n) 和f2(n)，然后使用加权平均法将它们组合起来，得到一个更加准确的估价函数，从而优化AO*算法的搜索效率和搜索结果的质量。

3.2 扩展函数及其优化

扩展函数，用于从当前状态扩展出下一步可能的状态，并计算每个状态的代价。节点扩展策略是指在扩展节点时选择合适的优先级。

可以通过建立专家库优化扩展函数［10］。

建立专家库，主要从过去的故障库中，经过机器学习训练得到专家库模型。需要从故障库中收集大量的数据，这些数据包括故障类型、故障原因、解决方案等信息。同时需要对数据进行清洗、去重、标准化等操作，以确保数据的质量和一致性。然后对数据进行特征提取，从原始数据中提取出有意义的特征，以用于后续的模型训练。选择决策树、支持向量机、神经网络等学习模型，并利用训练数据对模型进行训练。同时，还可以根据专家经验和知识，自定义来指导扩展函数的生成。

将评估优化后的模型部署到专家库中。需要在日常测试中对专家库进行维护，及时自动化更新数据和模型，以保证专家库的准确性和可靠性。

3.3 实施注意事项

a）AO*算法陷入无限循环。

当搜索算法试图展开一个状态时，如果它认为展开该状态会导致搜索结果变差，那么它可能会跳过该状态。但是，如果该状态实际上是搜索结果的一部分，那么搜索算法可能会陷入循环，反复尝试展开该状态。为避免这种情况，可以添加一个最大深度限制，以确保算法不会搜索太深，或者使用回溯技术来撤销搜索过程中的某些步骤。

b）AO*算法会受到依赖矩阵大小的限制。

若依赖矩阵较大，可能会由于搜索时间过长或者占用内存过多而导致性能下降，为避免这种情况，可以使用剪枝技术来减少搜索空间的大小。例如使用Alpha-Beta 剪枝技术或者使用迭代加深搜索来限制搜索的深度。同时也可以使用稀疏矩阵来优化，将搜索状态空间表示为一个稀疏矩阵。在搜索过程中，只需要存储非零元素和相关信息，而不需要存储零元素和无关信息，从而将减少内存占用，加速搜索。

4 结束语

通过将测试过程和方法模型转化为依赖矩阵，可提供更为清晰的可视化方式，更好地理解测试之间的依赖关系，可以量化测试方法之间的关联度和依赖程度从而得到更加具体和可度量的结果，通过矩阵算法分析识别其中的冗余测试，结合图论、专家库和机器学习等手段，充分利用各种方法的优势，使得测试过程更为全面，提高测试方法的准确性和智能化水平。