基于元启发式算法的测试场景生成与优化方法

摘要

软件测试是保证软件质量和提高软件可靠性的重要技术。随着基于UML模型的软件开发与RUP开发过程的广泛应用，使得基于UML模型的测试逐渐成为基于模型测试的主要研究方向。基于搜索的软件工程问题可以转化为优化问题，优化问题又可以使用元启发式算法解决。其中，在基于UML活动图生成与优化测试场景的问题上，遗传算法是最常用的元启发式算法。
　　在场景生成问题上引入遗传算法，对该问题提供了必然的动力，然而遗传算法局部搜索能力差，在进化后期搜索效率低，导致算法比较费时；并且随着软件规模与复杂度迅猛增长，在测试过程中，很难进行详尽的测试。另外，测试本身还要求在有限的时间内发现尽可能多的错误。因此，需要根据某种需求对场景进行优化，其目的是在有限的时间内将注意力更多地集中在重要且复杂的部分上。
　　1）对于基于UML活动图生成测试场景问题，提出了混合遗传算法，该方法结合遗传算法和爬山算法，解决了遗传算法局部搜索能力差的问题。并且为了避免“早熟”现象，在算法每次进行爬山操作之前调用种群生成函数。与其它算法相比，该算法不仅解决了局部性问题而且能够有效地提高测试场景生成的效率，从而降低测试的成本。
　　2）对于基于UML活动图优化测试场景问题，提出了一种场景优化技术。首先将活动图转化为控制流图；通过DFS遍历控制流图生成所有可能的测试路径；最后对已得到的路径进行优化。该优化算法将遗传算法和粒子群优化算法相结合，利用粒子群优化算法特有的记忆功能，解决遗传算法在种群发生改变时丧失以前信息的缺点。与其它算法相比，该算法不仅能生成一条优先测试的关键测试场景，而且能够大大提高测试场景优化的效率。
　　3）最后，使用一些常用的UML活动图对算法进行说明，并使用Java语言对改进算法进行验证。实验结果表明：改进的算法增强了处理活动图的能力。

目录

封面

声明

中文摘要

英文摘要

目录

缩略词

第一章 绪论

1.1引言

1.2 国内外研究现状

1.3 论文的研究内容

1.4 论文的组织结构

第二章 软件测试相关理论及关键技术

2.1 软件测试

2.2 面向对象软件测试

2.3 基于模型的软件测试

2.4 基于UML模型的软件测试

2.5 元启发式优化算法

2.6 本章小结

第三章 基于元启发式算法的测试场景生成方法

3.1 遗传算法

3.2 爬山算法

3.3 UML活动图

3.4 基于UML活动图的覆盖准则

3.5 混合遗传算法的思想与流程

3.6 混合遗传算法的原理与实现

3.7 本章小结

第四章 基于元启发式算法的测试场景优化方法

4.1 粒子群优化算法

4.2 测试场景优化算法的思想及流程

4.3 测试场景优化算法的原理及实现

4.4 本章小结

第五章 实验与结果分析

5.1 测试场景生成方法

5.2 测试场景优化方法

5.3 本章小结

第六章 总结与展望

6.1研究工作总结

6.2 工作展望

参考文献

致谢

在学期间的研究成果及发表的学术论文