学位论文 > 优秀研究生学位论文题录展示

基于模拟退火—量子遗传算法的路径测试数据自动生成方法研究

作　者: 季海婧
导　师: 孙军梅
学　校: 杭州师范大学
专　业: 计算机应用
关键词: 量子遗传算法模拟退火算法测试数据自动生成基本路径测试角度编码动态旋转角策略
分类号: TP311.53
类　型: 硕士论文
年　份: 2012年
下　载: 123次
引　用: 0次
阅　读: 论文下载

内容摘要

随着软件产品的复杂性不断提高以及软件规模的不断扩大,软件测试的自动化技术越来越受到学术界和工业界的重视。测试数据的自动化生成是实现测试自动化的关键,只有使测试数据能够自动化生成才能从根本上降低软件成本,保证软件质量。目前许多国内外学者针对这一问题进行了研究,虽然目前一些算法和技术已经能够自动生成测试数据,但是尚不成熟,还需要进行进一步的探索和完善。本文通过大量研究和分析发现采用基本路径测试生成测试数据是非常有效的方法,但是该方法需要一种性能较高的演化算法作为基础。因此,本文提出将量子遗传算法作为核心算法,并针对其生成测试数据方面的缺点进行了分析和改进。首先量子染色体的编码方式由矢量编码改进为角度编码,由于角度编码只存储一个实数,大大降低了存储空间；其次,提出一种新的动态旋转角策略,使种群的演化直接以父代最优解为目标,加速了算法收敛效率,同时该策略还可以保证种群中优秀性状能够得到较好地遗传,使子代更容易收敛到最优解；而后,采用Hadamard门变异策略,对变异种群是以小幅度的波动增加种群多样性；最后将量子遗传算法和模拟退火算法有效结合,利用状态转移概率选择性地接受恶化解,使种群概率地跳出当前解,防止算法“早熟收敛”。本文将改进的算法命名为“模拟退火-量子遗传算法”,简称SA-QGA。本文采用多个复杂连续函数对多种算法进行了比较,实验证明新算法在寻优性能和收敛次数上较其他算法有很大提高。最后,本文基于SA-QGA设计并实现了基于指定路径的测试数据自动生成框架。该框架主要分为三个部分：测试环境构造模块、SA-QGA模块以及测试运行环境模块。通过三角形判定问题进行了验证,实验表明该系统能够准确地生成满足指定路径的测试数据,具有很好的寻优性能和较高的收敛效率。

全文目录

致谢  4-5
摘要  5-6
Abstract  6-11
1 绪论  11-21
  1.1 研究背景及意义  11-12
  1.2 国内外研究现状  12-17
  1.3 本文研究内容  17-18
  1.4 本文的组织结构  18-21
2 软件测试的分类及测试数据自动生成技术  21-33
  2.1 软件测试分类  21-27
    2.1.1 静态测试  21-22
    2.1.2 动态测试  22
    2.1.3 黑盒测试  22-23
    2.1.4 白盒测试  23-27
  2.2 测试数据自动生成方法  27-31
    2.2.1 面向功能的测试数据的自动生成  28
    2.2.2 面向结构的测试数据的自动生成  28-31
  2.3 本章小结  31-33
3 模拟退火-量子遗传算法  33-51
  3.1 量子遗传算法  33-37
    3.1.1 量子位  34-35
    3.1.2 量子门表示  35-37
  3.2 改进的量子遗传算法  37-43
    3.2.1 角度编码量子位  38-39
    3.2.2 新的动态旋转角策略  39-40
    3.2.3 Hadamard门(H门)变异操作  40-41
    3.2.4 改进的量子遗传算法流程  41-43
  3.3 模拟退火算法  43-44
    3.3.1 模拟退火算法的构成要素  43-44
    3.3.2 模拟退火算法流程  44
  3.4 模拟退火-量子遗传算法  44-49
    3.4.1 SA-QGA算法描述  45
    3.4.2 SA-QGA算法的优点  45-46
    3.4.3 各算法性能对比实验  46-49
  3.5 本章小结  49-51
4 基于模拟退火-量子遗传算法的测试数据自动生成  51-65
  4.1 测试数据生成框架  51-52
  4.2 被测程序静态分析  52-56
    4.2.1 程序插桩设计  52-53
    4.2.2 参数编码设计  53-54
    4.2.3 适应度函数的设计  54-56
  4.3 SA-QGA算法的设计  56-57
  4.4 SA-QGA算法在测试数据生成框架中的实现  57-62
    4.4.1 种群初始化  58
    4.4.2 计算相应函数的适应度值  58-59
    4.4.3 最佳个体的设计  59
    4.4.4 量子遗传算子的实现  59-61
    4.4.5 退火操作  61-62
  4.5 算法时间度分析  62-63
  4.6 本章小结  63-65
5 仿真实验结果及分析  65-77
  5.1 数据生成实验构造  65-68
  5.2 测试数据自动生成结果分析  68-74
    5.2.1 模拟退火-量子遗传算法自动生成测试数据采样  68-71
    5.2.2 量子遗传算法生成测试数据采样  71-72
    5.2.3 SA-QGA及QGA的测试数据生成对比  72-74
  5.3 时间复杂度验证  74
  5.4 本章小结  74-77
6 结论及展望  77-79
  6.1 结论  77-78
  6.2 展望  78-79
参考文献  79-86
攻读学位期间的研究成果  86

基于模拟退火—量子遗传算法的路径测试数据自动生成方法研究

内容摘要

全文目录

相似论文