Page 129 - 《软件学报》2025年第5期

孙百才 等: 代理辅助多任务进化优化引导的 MPI 程序路径覆盖测试用例生成 2029

大值.
∗
由公式 (1) 可知, Sim(p , p j (X)) 越大, X 遍历的子路径 p j (X) 越接近目标子路径 p . 当 Sim(p , p j (X)) = 1 时,
∗
∗
j j j
∗
∗ ∗ p 的测试用例生成问题为
p j (X) 即为 p . 此时, X 即为覆盖 p 的测试用例. 这样一来, 可转换进程 π j 内目标子路径 j
j
j
最大优化问题, 并建立如公式 (2) 所示的优化模型.

OptMod = max F j (X) = Sim(p , p j (X)) (2)
∗
j j
X∈D
∗
p 的适应值, 即覆
其中, X 为一个测试输入, 也称为一个进化个体; F j (X) 为适应值函数, 其具体的数值表示 X 覆盖 j
∗
j
盖程度. 结合多任务进化优化的工作原理, 这里能够将面向 p 的测试用例生成优化模型 OptMod j 置于第 个优化
j
任务 task j 中, 并基于本文所提策略和进化算法求解 OptMod j , 其中, j = 1,2,...,N .

1.2 基于进化优化的路径覆盖测试
Ma 等人 [11] 提出了一个面向 C 语言程序的测试用例生成框架, 该框架基于禁忌搜索算法搜索隐藏故障的可行
路径, 从而约减需生成的有效测试用例数量. 鉴于软件测试成本通常占软件开发总成本的 40% 以上, Khari 等人 [12]
分别使用爬山算法、粒子群优化、萤火虫算法, 以及布谷鸟搜索算法等 6 种进化优化方法, 生成覆盖路径的测试
用例, 并通过对比实验数据, 找到求解路径覆盖测试问题的最优算法. 基于相似路径通常由相似测试用例来覆盖的
原则, Cai 等人 [13] 设计了一款新式局部搜索策略, 并提出了一种基于改进分散搜索策略的进化优化算法, 用于生成
覆盖路径的测试用例. 此后, Semujju 等人 [14] 提出了一种基于反馈导向机制的路径覆盖测试用例生成方法, 该方法
的优势在于能够自动删除不可行路径, 以及筛选出可行路径.
针对 MPI 程序的不确定性特征, Tian 等人 [15] 通过变异不确定性原语的通信参数, 寻找合适的通信序列, 并使
用遗传算法生成了覆盖路径的测试用例. 随后, Gong 等人 [16] 提出了一种用于 MPI 程序路径覆盖测试的反馈导向
遗传算法, 该算法通过改进遗传算子提升了测试用例生成效率. 针对不确定性带来的 MPI 程序测试难度大的问题,
我们提出为每一路径选择一个优越的通信序列, 并基于协同进化遗传算法生成期望的测试用例, 实现以同一测试
用例执行具有不确定性的 MPI 程序时, 该测试用例会遍历相同的程序片段 [17] . 针对 MPI 程序测试效率低的问题,
Du 等人 [18] 基于实际执行代码行数与条件谓词数等评价指标, 选择最容易覆盖的路径作为目标路径, 并使用遗传算
法生成期望的测试用例. 随后, 我们提出了分布式代理模型驱动的 MPI 程序路径覆盖测试用例进化生成方法, 进
一步减少了测试所需成本 [19] .
以上成果表明, 研究 MPI 程序路径覆盖测试用例生成问题及其进化求解方法, 是有效生成测试用例的重要途
径. 然而, 基于现有工作生成覆盖 MPI 程序目标路径的测试用例生成时, 所需的测试成本仍居高不下. 鉴于此, 本
文将 MPI 程序目标路径内每条目标子路径的测试用例生成问题优化模型置于一个优化任务中, 并在每一优化任
务中, 基于进化算法来求解相应的优化模型, 以及利用代理模型来降低被测 MPI 程序的实际执行成本, 从而进一
步提升 MPI 程序路径覆盖测试效率.

1.3 代理辅助进化优化
代理辅助进化优化的一般原理如下: 使用进化算法求解昂贵优化问题的过程中, 基于收集的历史数据训练一
或多个代理模型, 用于估计进化个体的适应值, 从而减少进化个体适应值的评估次数和成本 [20] . 当前, 用于进化个
体适应值估计的代理模型多种多样, 主要分为单一代理模型和多代理模型两类 [21] .
针对单一代理模型, Li 等人 [22] 提出了一种径向基函数辅助进化优化框架, 降低了昂贵优化问题的求解成本.
为解决昂贵高维优化问题, Zhan 等人 [23] 提出了一种 Kriging 辅助差分进化算法, 该算法应用于若干测试问题上, 验
证了 Kriging 模型的优越性. 为解决高约束昂贵优化问题, Jiao 等人 [24] 提出了一种高斯过程辅助进化算法, 该算法
能够提高优化问题求解速度和约束处理能力. 关于多代理模型, Wang 等人 [25] 提出了一种数据驱动进化优化算法,
该算法采用集成代理模型代替昂贵优化问题的实际求解, 降低了问题的求解成本. 针对高维决策变量导致的代理
模型预测准确度不高的问题, Lin 等人 [26] 提出了一种用于处理昂贵多目标优化问题的集成代理框架, 显著提高了
模型的预测准确度. 使用进化算法求解 MPI 程序路径覆盖测试用例生成优化问题的过程中, 我们开发了集成代理