基于改进量子蚁群算法的测试用例约简方法研究

摘要

测试用例约简(Test Suite Reduction)是在最初测试用例集合的基础上按照一定规则、算法寻找一个测试用例执行代价总和最小的测试用例子集，且该子集必须能够满足与前者相同的测试需求集。针对该问题学者们提出了许多算法。传统约简算法如贪心算法、GRE算法、HGS算法、线性规划法等都是以每个测试用例代价相同为理论基础，求一个包含测试用例数量最少的子集也成为代表集。上述算法虽然能够求得一个包含测试用例数量最小子集，但是该子集测试用例执行代价总和未必最小。本文在进行测试用例约简时，不仅仅考虑减少测试用例的个数，还考虑到每个用例的不同测试用例执行代价，在保证软件测试充分性的前提下求一个测试用例执行代价总和最小的代表集。
　　针对测试用例约简问题本文使用了改进的量子蚁群算法(Modified QuantumAnt Colony Algorithm)。量子蚁群算法是将启发式量子进化算法QEA(Quantum-inspired Evolutionary Algorithm)与传统的蚁群算法相结合，将其量子计算的优点引进到蚁群算法提高蚂蚁全局搜索能力，避免了蚁群容易陷入局部最优问题，能够使蚁群算法突破算法极限。针对测试用例初始集合规模庞大的特点本文引入了候选集的概念，对测试用例集合进行初次筛选，形成一个候选集，以减少量子蚁群算法处理数据的规模。为了让蚁群在算法初期扩大搜索范围，在后期加快收敛速度，本文在算法参数方面使用自适应策略。最后，在信息素设置方面，增强了算法初始各个结点的信息素值，为了避免初值对后期迭代的影响本文对信息素的值采取最大最小区间限制的策略;在信息素更新方式上同时使用局部更新和全局更新两种方式，在挥发机制下经过初期的迭代，信息素会很快恢复到正常水平，但是蚁群能够在算法初期获得一个较好的结果，为蚁群后期迭代奠定良好遍历基础。
　　本文在西门子标准测试套件(Siemens)上进行大量的仿真实验，并将实验结果与已有的算法进行比对。实验结果表明，改进的量子蚁群算法与其他同类算法相比能够获得测试用例执行代价更小的测试用例集且算法具有比较好的稳定性。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 研究现状

1．3 主要内容

1．4 章节安排

第2章 测试用例集约简技术

2．1 软件测试

2．2 测试用例约简

2．2．1 冗余测试用例类型

2．2．2 测试用例约简

2．2．3 测试用例约简规则

2．3 测试用例约简方法

2．3．1 贪心算法

2．3．2 HGS算法

2．3．3 GRE算法

2．3．4 整数规划法

2．3．5 改进的贪心算法

2．3．6 蚁群算法

2．4 本章小结

第3章 蚁群算法

3．1 蚁群算法原理

3．1．1 蚁群算法基本原理

3．1．2 蚁群算法的特征

3．2 蚁群算法数学模型

3．2．1 蚁群算法的框架和流程图

3．2．2 蚁群算法数学模型

3．3 几种改进的蚁群算法

3．3．1 精英蚂蚁系统

3．3．2 蚂蚁系统

3．3．3 最大最小蚂蚁系统

3．3．4 量子蚁群算法

3．4 本章小结

第4章 基于改进量子蚁群算法的测试用例约简方法

4．1 基于蚁群算法的测试用例约简方法

4．1．1 问题域

4．1．2 蚁群算法思路

4．2 基于改进量子蚁群算法的测试用例约简方法

4．2．1 候选集策略

4．2．2 量子编码

4．2．3 量子旋转门

4．2．4 转移规则

4．2．5 信息素更新策略

4．3 基于改进量子蚁群算法的测试用例约简流程

4．4 本章小结

第5章 仿真实验

5．1 实验平台以及实验数据

5．1．1 实验平台

5．1．2 数据来源

5．1．3 测试用例执行流程

5．2 算法参数分析

5．3 实验结果分析

5．4 本章小结

第6章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢