基于模拟退火遗传算法的测试数据生成研究

论文摘要

随着信息技术的快速发展,大量的软件产品已渗透到各行各业。如何保证软件的质量问题成为一个关注焦点。软件测试是确保软件产品质量及可靠性的主要途径,其地位是无可替代的。然而,随着软件行业的发展,软件产品的规模在逐渐扩大,复杂度也越来越高,使得软件测试的困难进一步加剧,如何有效的降低软件测试所需的大量人力、物力资源和耗费的时间,是软件测试需要重点研究的问题,据统计,软件测试耗费的时间约占整个开发周期的1/3,成本上占了近50%。所以,软件测试自动化能力的提升是保证软件产品质量、降低产品开发成本的关键途径。而为了提高软件测试的自动化程度,需要重点研究的就是如何提高测试数据的自动生成,本文重点将对此问题进行研究与分析。本文首先简单介绍了软件测试研究的背景和意义,以及研究的现状,并简要提出了本文研究的内容和本篇论文的结构框架。接着,本文较详细的对软件测试进行了概述,并介绍了测试数据自动生成的相关技术,同时对它们各自优缺点进行了论述。重点分析了面向结构的测试数据自动生成技术,以及已有的一些可用办法。文中对各种方法及相关技术做了系统的总结与比较,而后提出在这一领域,人工智能技术将能发挥很大作用。随后,本文对遗传算法和模拟退火算法进行了详细的介绍,重点分析了它们各自的算法原理、构成要素、算法执行步骤以及各自所存在的优缺点。由于普通遗传算法在进化寻找最优解过程中,极易陷入“早熟”收敛,且种群个体存在多样性较差的现象,本文提出了混合模拟退火遗传算法(SAGA),并将其用于测试用例的自动生成,充分发挥二者优势互补的特点,提高算法的整体性能,并将此混合算法作为本文的核心算法。然后,本文介绍了将SAGA算法用于测试数据自动生成的系统结构模型,并且针对实际的应用,对SAGA算法的一些关键技术进行了改进：如编码问题、分支函数的构造和程序插桩方式,构造适应实际问题求解的适应度函数、和遗传操作中的交叉、变异策略的改进等。改进后的模拟退火遗传算法(ISAGA),不仅更有效克服了“早熟”收敛的问题,而且也提高了算法进化求解的收敛速度,大大改善了搜索效率。最后在实验分析部分,先设计实现了基于改进模拟退火遗传算法(ISAGA)的测试数据辅助生成工具,并以一个经典程序作为例子,自动生成相应的测试用例,通过对实验结果的分析,证明了本文核心算法能有效生成满足目标的测试用例,且收敛性高,能克服一般GA算法的“早熟”收敛问题。而后,本文又利用了几个具有数学复杂特征的纯数学函数作为算法的适应度函数,来进化搜索满足问题目标的测试用例,通过实验表明本文的ISAGA算法较一般GA算法和SAGA算法在生成满足要求的测试数据的性能上,有较好的改善。

论文目录

• 摘要
• Abstract
• 目录
• 第1章 绪论
• 1.1 研究背景和意义
• 1.2 软件测试研究现状
• 1.3 本文研究内容和论文结构
• 1.3.1 研究内容
• 1.3.2 论文结构
• 第2章 软件测试及测试数据生成技术
• 2.1 软件测试概述
• 2.1.1 软件测试定义
• 2.1.2 软件测试目的和原则
• 2.2 软件测试分类
• 2.2.1 静态测试
• 2.2.2 动态测试
• 2.2.3 软件测试的步骤
• 2.3 软件测试数据生成技术
• 2.3.1 面向功能的测试数据自动生成
• 2.3.2 面向结构的测试数据自动生成
• 2.4 本章小结
• 第3章 测试数据搜索算法的研究与分析
• 3.1 遗传算法
• 3.1.1 遗传算法的原理
• 3.1.2 遗传算法的构成要素
• 3.1.3 遗传算法的基本流程
• 3.2 模拟退火算法
• 3.2.1 模拟退火算法的原理
• 3.2.2 模拟退火算法的基本流程
• 3.2.3 算法参数控制问题
• 3.3 混合算法
• 3.4 本章小结
• 第4章 模拟退火遗传算法的测试数据生成
• 4.1 系统框架
• 4.2 参数的编码
• 4.2.1 参数的选取
• 4.2.2 参数的编码
• 4.3 插桩及适应度函数构造
• 4.3.1 程序插桩理论
• 4.3.2 适应度函数构造
• 4.3.3 程序插桩改进
• 4.3.4 分支函数插桩过程
• 4.4 遗传算子的改进
• 4.4.1 采用多点均分交叉
• 4.4.2 采用自适应变异概率
• 4.5 模拟退火遗传算法的设计
• 4.6 本章小结
• 第5章 实验和分析
• 5.1 工具总体设计
• 5.1.1 被测程序分析模块
• 5.1.2 程序插桩模块
• 5.1.3 SAGA数据生成模块
• 5.2 实验结果分析
• 5.2.1 测试数据生成分析
• 5.2.2 算法性能比较
• 5.3 本章小结
• 第6章 总结与展望
• 参考文献
• 附录A 图索引
• 附录B 表索引
• Appendix A. Figure Index
• Appendix B. Table Index
• 致谢
• 攻读学位期间的科研成果