覆盖表生成的遗传算法配置参数优化

论文摘要

组合测试是软件测试领域的重要测试方法之一。覆盖表作为其测试用例集,能够以少量的测试用例对软件各因素之间的相互作用关系进行最大限度的针对性覆盖,可以有效检测由软件各因素相互作用所触发的故障。如何得到尽可能小规模的覆盖表是组合测试的关键,很多数学方法、贪心算法以及演化搜索方法等被应用于生成各种覆盖表,本文首先对已有算法进行了较为详细的分析及概括,并在此基础上针对演化搜索方法的性能受到方法本身配置参数影响很大这一实际问题,以二维覆盖表生成为实例,系统地对典型的演化搜索方法--遗传算法的种群规模、进化代数、交叉概率、变异概率以及遗传算法的变种算法等因素进行探索,设计了pair-wise法、Base choice法和爬山法三条实验路线,在离散区间内探索遗传算法的这些配置参数及其相互作用对算法生成二维覆盖表效果的影响。本文在上述实验的基础上又提出了双演化方法以进一步提高遗传算法的性能。该方法实现了Hadoop平台下覆盖表的多配置并行自动化生成,通过遗传算法自身的演化能力,在连续值区间内对覆盖表生成的遗传算法参数配置进行大规模的进一步迭代优化,以探索遗传算法在覆盖表生成领域的潜力。本文工作主要为了回答以下三个问题：1)对于特定二维覆盖表生成问题,是否存在遗传算法的较优参数配置；2)对于一般的二维覆盖表生成问题,是否存在通用的遗传算法较优参数配置;3)如果不存在确定的通用最优参数配置,那么是否存在遗传算法参数配置的较优取值范围。本文所采用的四条实验路线可以整合并应用于大部分演化搜索算法的性能优化实验中,为如何提高演化搜索类算法在覆盖表生成领域的性能提供了通用的实验框架。同时,该实验框架能够进一步扩展到其他应用场景下的演化搜索算法的性能研究中,为整个演化搜索算法的性能发掘及提升提供了实践基础。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 课题研究背景
• 1.2 论文主要研究内容
• 1.3 论文架构
• 第二章 覆盖表定义及已有生成方法介绍
• 2.1 覆盖表相关定义
• 2.2 覆盖表生成方法介绍
• 2.2.1 数学方法
• 2.2.2 贪心算法
• 2.2.3 演化搜索算法
• 2.2.3.1 禁忌搜索算法
• 2.2.3.2 模拟退火算法
• 2.2.3.3 粒子群算法
• 2.2.4 覆盖表生成方法小结
• 第三章 可配置覆盖表生成的遗传算法
• 3.1 遗传算法
• 3.2 遗传算法生成覆盖表的已有工作及存在问题
• 3.3 可配置覆盖表生成的遗传算法算法框架
• 3.3.1 种群规模m
• 3.3.2 进化代数T
• 3.3.3 交叉概率Pc
• 3.3.4 变异概率Pm
• 3.3.5 遗传算法的变种算法
• 第四章 Pair-wise、Base choice和爬山法实验设计及数据分析
• 4.1 实验设计
• 4.2 实验工具程序说明
• 4.2.1 编写目的
• 4.2.2 软件功能
• 4.2.2.1 功能一：确定参数配置下利用遗传算法生成二维覆盖表
• 4.2.2.2 功能二：不确定参数配置下利用遗传算法生成二维覆盖表
• 4.2.3 软件精度及时间特性
• 4.2.4 软件运行环境要求
• 4.2.5 软件演示
• 4.2.5.1 安装及初始化
• 4.2.5.2 软件输入
• 4.2.5.3 软件输出
• 4.3 数据分析
• 4.3.1 pair-wise实验
• 4.3.2 Base choice实验
• 4.3.2.1 遗传算法的变种算法
• 4.3.2.2 种群规模
• 4.3.2.3 进化代数
• 4.3.2.4 交叉概率
• 4.3.2.5 变异概率
• 4.3.3 爬山实验
• 4.3.3.1 遗传算法的变种算法
• 4.3.3.2 种群规模
• 4.3.3.3 进化代数
• 4.3.3.4 交叉概率
• 4.3.3.5 变异概率
• 4.4 实验结论
• 第五章 双演化方法
• 5.1 实验设计
• 5.2 数据分析
• 第六章 总结和展望
• 6.1 文章总结
• 6.2 未来工作展望
• 参考文献
• 硕士期间研究成果
• 致谢