基于改进NSGA-Ⅱ算法测试资源优化配置的研究

信息化高度发展的今天, 越来越多的软件产品深入人们的生活, 而高质量的软件产品一直是我们所追求的目标, 如何提高软件产品质量也是一个经久不衰的话题。完整测试某种程度上就是穷举测试, 但大多数软件在进行测试的时候只能采取有限测试, 这就意味着一种冒险, 在实际测试中如果不使用穷举测试是很难发现一些潜在问题的, 而如果在软件投入市场时才发现则修复代价就会非常高。是否投入越多, 发现的错误就越多, 产品质量就越高呢?其实不然, 随着测试量的增加, 测试成本将呈几何数级上升, 而软件缺陷降低到某一数值之后将不会有明显的变化, 现实生活中要得出这个最优测试量是比较困难的。

目前最优测试量还只能靠有经验的软件测试工程师根据经验来判定, 如何使用数学模型的方式更准确的找到最优测试范围则是本次研究要解决的问题。在求曲线最优解的数学算法中运用最普遍的是遗传算法, 但遗传算法只能解决简单的单目标优化问题, 软件测试中的多目标优化仅仅靠遗传算法是不能解决的, 如今解决多目标优化问题的遗传算法有多目标加权遗传算法、基于向量评估的遗传算法、基于博弈论的遗传算法、非支配排序遗传算法 (Non-dominated Sorting Genetic Algorithm, NSGA) [1]及其改进算法NSGA-II[2]等。

NSGA-Ⅱ是目前最流行的多目标进化算法之一, 它降低了非劣排序遗传算法的复杂性, 具有运行速度快, 解集的收敛性好的优点, 成为其他多目标优化算法性能的基准。NSGA-Ⅱ算法在资源优化配置方面的研究主要集中在工业应用如电力资源, 水利资源等的配置方面, 在软件项目开发中的资源优化配置研究较少。本次研究将以软件测试中的资源个体建立目标函数, 使用NSGA-Ⅱ算法建立测试资源优化模型, 并进行应用改进。

假设项目的模块规模、复杂度等综合表现用函数f (xi) 表示 (i=1, 2, …n) , 缺陷的产生与被测模块的规模及复杂度有一定关系, 用d (xi) 表示 (i=1, 2, …n) , 如果被测模块都由符合条件的软件测试人员来进行测试 (此处不考虑高级和低级软件测试人员) , 测试时间用Ti表示 (i=1, 2, …n) , 则每个模块消耗的成本为Ci=f (xi) *Ti。

NSGA-Ⅱ算法提出了拥挤度的概念, 用id表示, 在带精英策略的非支配排序遗传算法中, 拥挤度的计算是保证种群多样性的一个重要环节。

如果个体i所处非支配层优于个体j所处的非支配层, 再比较拥挤度, 优胜者进入下一步计算, 如此循环, 产生新个体选择。

软件测试阶段中, 对测试资源的分配存在一定的差异性, 因此在考虑资源分配时我们可以分阶段进行, 由于测试资源有限, 因此我们考虑每个阶段成本的最低值。获取每个测试阶段最优的资源配置结果, 即获得在系统达到Pareto最优时各模块实际消耗的测试资源, 在实际分配过程中, 系统测试可能不需要这么多的资源, 也就是说, 实际测试时间可能提前, 因此, 在每一测试阶段找到最优解之后需要获得实际的测试时间T实。

我们也可以用斜率比较的方式来找到资源分配最优点, 一般测试成本是呈曲线增加的, 假设第i个点的坐标为 (xi, yi) , 第i+1个点的坐标为 (xi+1, yi+1) , 第i-1个点的坐标为 (xi-1, yi-1) , i点与i+1点之间的斜率为:

i-1点与i点之间的斜率为:

比较Ki+1与ki的大小, 如果Ki+1≥2ki, 则可考虑停止追加资源。

综合比较我们会发现基于NSGA-Ⅱ算法比斜率法更严谨, 系统测试是软件开发各个阶段中最消耗时间和资源的阶段, 对于串并行软件系统来说, 系统可软件产品随着测试的进程推进会发生变化, 如果按照最初的资源分配方案很显然会造成资源浪费, 因此本文使用基于NSGA-Ⅱ算法, 考虑测试资源多目标动态分配, 以测试资源 (时间) 为约束、以最小化测试成本为目标, 动态分配资源, 在一定程度上可以节省系统测试资源的消耗, 提高复杂软件产品的质量, 从而在测试资源分配问题研究领域, 对深化测试资源分配问题的研究起到了一定的推动作用。

摘要：提高软件产品质量是一个经久不衰的话题, 普遍认为提高软件产品质量最有效的方法是软件测试, 完整测试某种程度上就是穷举测试, 但大多数软件在进行测试的时候只能采取有限测试, 这意味着一种冒险, 在实际测试中如果不使用穷举测试是很难发现一些潜在问题的, 那么如何使用有限的资源提高软件产品质量呢?NSGA-Ⅱ是目前较流行的多目标进化算法之一, 它降低了非劣排序遗传算法的复杂性, 具有运行速度快, 解集的收敛性好等优点, 成为其他多目标优化算法性能的基准, 本文从NSGA-Ⅱ算法入手, 提出了基于改进NSGA-Ⅱ算法使测试资源得到优化配置, 使用数学模型的方式更准确的找到最优测试范围, 从而将无限的软件测试变成有限测试, 进而达到提高软件产品质量的目的。

关键词：NSGA-Ⅱ,测试资源,项目管理,优化配置

参考文献

[1] Srinivas N., Deb K..Multiobjective function optimization using nondominated sorting genetic algorithms[J].Evolutionary Computation, 1995, 2 (3) :221-248.

[2] 盛万兴, 叶学顺, 刘科研, 孟晓丽, 基于NSGA-Ⅱ算法的分布式电源与微电网分组优化配置[J].中国电机工程学报, 2015, 35 (18) .

[3] 张屹, 陈平, 万兴余.基于正交设计NSGA-II算法的制动器多目标优化[J].计算机应用研究, 2016 (03) .

[4] 尹杭, 孟涛.基于改进NSGA-Ⅱ算法的配电网分布式电源规划[J].黑龙江电力, 2015 (06) .

[5] 王超学, 田利波.一种改进的多目标合作型协同进化遗传算法[J].计算机工程与应用, 2016 (02) .

[6] 陆阳, 岳峰, 张国富, 苏兆品, 王永奇.串并行软件系统测试资源动态分配建模及求解[J].软件学报, 2016, 27 (8) :1964-1977.