基于遗传算法的协议一致性测试序列生成研究

论文摘要

在软件测试基础上发展起来的协议测试是协议开发过程中的重要环节。协议测试中的协议一致性测试是最重要的协议测试。通过对协议实现(待测实体)的协议一致性测试,我们可以找出协议实现与协议描述的差异。协议一致性测试中,如何从协议描述出发生成高质量的一致性测试序列直接关系到测试的成功与否。本文在研究了遗传算法在工程领域的应用实现和当前生成一致性测试测试序列主要方法的基础上,提出了应用遗传算法来搜索协议一致性测试序列的设计与实现。本文首先介绍协议测试和一致性测试的相关理论基础以及ISO/IEC9646标准给出的协议一致性测试的指导框架,对现存的几种协议一致性测试序列的生成方法作了分析。然后针对自然语言描述协议不精确的特征,介绍了协议描述的几种形式化技术,重点是以Petri网模型描述协议。最后总结了遗传算法的构成、相关理论、数学分析和在工程应用中需要注意的一些问题。在前面分析了描述协议的Petri网模型特征和性质及遗传算法基本应用原理的基础上,借鉴遗传算法解决其他工程领域优化问题的成功应用经验,提出了以采用测试目标转移序列映射的遗传算法生成协议一致性测试序列的设计思想,对算法的各个组成要素作了详细地设计介绍,并给出了实现生成协议一致性测试序列程序的框架流程。然后结合算法性能简要地分析了在生成测试序列的遗传搜索中控制参数对算法性能的影响。最后针对本文生成协议一致性测试序列方法提出了一些可行的优化思想。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 研究背景和意义
• 1.3 国内外研究现状
• 1.4 课题主要研究内容及组织结构
• 第二章 协议一致性测试
• 2.1 协议开发与协议测试
• 2.2 协议测试
• 2.3 一致性测试
• 2.4 协议一致性测试序列生成方法
• 2.4.1 T 方法
• 2.4.2 D 方法
• 2.4.3 UIO 方法
• 2.4.4 W 方法
• 2.5 本章小结
• 第三章 协议的形式化描述
• 3.1 形式化描述模型
• 3.1.1 有限状态机FSM
• 3.1.2 时序逻辑（TL）
• 3.1.3 通信进程演算（CCS）
• 3.1.4 Petri 网模型
• 3.2 其它形式化描述语言
• 3.3 本章小结
• 第四章 遗传算法介绍
• 4.1 遗传算法概况
• 4.2 标准遗传算法的组成
• 4.2.1 编码
• 4.2.2 种群初始化
• 4.2.3 选择（复制）操作
• 4.2.4 遗传算子
• 4.2.5 搜索评价
• 4.2.6 终止判定
• 4.3 遗传算法的模式定理和基因块假设
• 4.3.1 模式与模式空间
• 4.3.2 模式生存模型
• 4.3.3 模式定理
• 4.3.4 遗传算法的基因块假设
• 4.4 遗传算法的隐并行性
• 4.5 遗传算法的数学分析
• 4.6 遗传算法的早熟问题与约束问题
• 4.6.1 早熟问题
• 4.6.2 约束问题
• 4.7 遗传算法的性能指标
• 4.8 非标准遗传算法
• 4.8.1 混合遗传算法
• 4.8.2 并行遗传算法
• 4.9 本章小结
• 第五章 一致性测试序列生成中的遗传算法应用
• 5.1 采用PETRI 网模型描述待测协议
• 5.2 遗传算法搜索测试序列的思想
• 5.2.1 测试序列与Petri 网转移的映射
• 5.2.2 转移序列的搜索目标
• 5.2.3 测试目标转移和测试执行转移
• 5.2.4 遗传搜索前预计算
• 5.3 参数选择
• 5.3.1 编码
• 5.3.2 种群初始化
• 5.3.3 选择（复制）操作
• 5.3.4 遗传算子
• 5.3.5 目标函数
• 5.3.6 终止判定
• 5.3.7 编码逆映射
• 5.4 算法设计实现
• 5.5 本章小结
• 第六章 性能评估与优化
• 6.1 算法性能
• 6.2 参数分析
• 6.2.1 交叉概率
• 6.2.2 变异概率
• 6.2.3 控制参数设计
• 6.3 遗传搜索的优化
• 6.3.1 预计算优化
• 6.3.2 混合遗传搜索优化
• 6.3.3 局部序列优化
• 6.4 本章小结
• 第七章 总结与展望
• 参考文献
• 致谢
• 在学期间的研究成果及发表的学术论文