第一章 绪论
1.1国内外研究现状
软件测试作为确保软件的质量，保证软件可靠性的有效手段。软件测试方法的优劣将直接影响到软件的质量、软件开发的周期以及软件开发的成本。在软件测试领域中，测试用例的生成与选择是专家学者和软件测试相关的工作人员关注的重点。
自上世纪 60 年代以来，国内外众多专家学者投入到测试用例自动生成的研究中并且提出了很多行之有效的科学方法。软件测试也逐渐成为一门独立的学科。测试用例的自动生成是软件测试重点及难点之一，如何使用高效的测试用例自动生成方法生成规模小且质量高的测试用例集，一直是专家学者研究的热点。近年来，一些专家学者尝试将智能搜索算法应用到软件测试用例的选择与生成，并取得了一定的成果。
S Xanthakis 等人[7]具有开创性的将遗传算法应用到路径覆盖的测试用例生成中。其首次将智能搜索算法用来解决路径覆盖的测试问题。基本思想是使用函数构造的方法将测试用例生成的问题转化为在搜索区域内求解函数最优值的问题。这种方法为后来的研究者将智能搜索算法引入到软件测试用例生成研究指明了方向。Wegener 等人[8]对遗传算法进行研究并在此基础上建立生成测试用例生成环境，并将其应用于工业程序的测试中。证明了遗传算法比随机法具有更高的覆盖率。Kaewyotha J 等人[9]在对遗传算法进行一定的研究并将其思想应用到测试用例生成中。该算法基于路径覆盖的方法进行程序用例生成，其分析被测程序流程图并找到被测程序中循环结构中的关键路径。在找到关键路径的基础上提出一种新的生成关键路径的方法。文献[4]研究了针对软件结构的测试用例生成问题，提出了使用遗传算法实现优化搜索生成测试用例。文献[10]将遗传算法与蚁群算法相结合，提出了遗传蚂蚁融合算法，对适应度函数进行一定的改进，并提出了“结构树”的概念。最后将所提算法应用于三角形判定程序中，实验表明其算法具有一定的可行，相比于标准遗传算法具有明显的优势。文献[11]提出基于遗传算法的测试用例生成技术，测试用例的参数根据遗传算法进行选择或变异。文献[12]将遗传算法和粒子群算法相结合应用于复杂的被测程序中，在一次执行中生成多组测试用例，提高了测试用例生成的效率。巩敦卫等人[13]将遗传算法应用于测试用例生成。验证了遗传算法在测试用例生成上的效率及故障检测率。
...........................
1.2本文研究内容
以上研究是将遗传算法、粒子群算法以及对他们的改进引入到测试用例生成中，但是由于遗传算法和粒子群算法存在其自身固有的缺陷。在将他们应用于测试用例生成时都极大的影响测试用例生成的效率和质量。例如遗传算法容易陷入早熟，收敛速度相对较慢，
算法的局部搜索能力相对不佳，搜索精度不高，算法稳定性较差，处理数据的规模小，控制的变量较多，计算复杂且计算量大，难以处理非线性约束的问题，并且需要对问题进行编码，编码的策略将直接影响算法的性能；粒子群算法也同样容易陷入早熟和落入局部最优，收敛性能不佳且收敛精度不高，对于离散问题和组合优化问题处理不佳。
在将遗传算法或粒子群算法应用于多路径测试用例生成和组合测试用例生成时，对适应度函数的设计并不理想，在设计适应度函数时没有将已生成的测试用例考虑进去、忽略了已生成的测试用例对正在生成的测试用例具有引导作用。
第三章 万有引力算法（GSA）研究及改进 ............................ 17在将遗传算法或粒子群算法应用于多路径测试用例生成和组合测试用例生成时，对适应度函数的设计并不理想，在设计适应度函数时没有将已生成的测试用例考虑进去、忽略了已生成的测试用例对正在生成的测试用例具有引导作用。
针对以上问题，本课题将万有引力搜索算法[17](Gravitational Search Algorithm，
GSA)引入软件测试中，并对 GSA 算法进行改进应用于多路径测试用例生成和组合测试用例生成中。本文主要研究内容如下所述：
（1）系统的学习研究软件测试用例生成方法。详细介绍了软件测试的分类以及关于测试用例生成方法与技术。并介绍了目前用于测试用例生成的部分智能搜索算法。
（2）分析 GSA 算法特点，针对 GSA 算法的易陷入早熟收敛和落入局部最优、全局搜索能力较弱的缺点提出基于改进的 Tent 混沌万有引力搜索算法(Gravitational Search Algorithm Based on Improved Tent Chaos，ITC-GSA)。该算法首先使用改进的 Tent 混沌映射来初始化种群，利用 Tent 混沌序列随机性、遍历性和规律性的特性使得初始种群尽可能随机地分布在可行域，加强算法的全局搜索能力；其次，引入引力常数 G 的动态调整策略提高算法的收敛速度和收敛精度；然后，设计成熟度指标判断种群成熟度并使用 Tent 混沌搜索有效抑制算法早熟收敛帮助种群跳出局部最优。
（1）系统的学习研究软件测试用例生成方法。详细介绍了软件测试的分类以及关于测试用例生成方法与技术。并介绍了目前用于测试用例生成的部分智能搜索算法。
（2）分析 GSA 算法特点，针对 GSA 算法的易陷入早熟收敛和落入局部最优、全局搜索能力较弱的缺点提出基于改进的 Tent 混沌万有引力搜索算法(Gravitational Search Algorithm Based on Improved Tent Chaos，ITC-GSA)。该算法首先使用改进的 Tent 混沌映射来初始化种群，利用 Tent 混沌序列随机性、遍历性和规律性的特性使得初始种群尽可能随机地分布在可行域，加强算法的全局搜索能力；其次，引入引力常数 G 的动态调整策略提高算法的收敛速度和收敛精度；然后，设计成熟度指标判断种群成熟度并使用 Tent 混沌搜索有效抑制算法早熟收敛帮助种群跳出局部最优。
............................
第二章 测试用例生成理论与技术
2.1 软件测试的定义及目的
软件测试是保证软件的质量以及软件可靠性的有效手段。软件测试的目的是为了发现被测程序中可能存在的缺陷或错误，也就是说软件测试的目的是为了验证软件满足需求达到预期的功能。软件测试伴随着软件的开发、运行以及后期维护的始终，应用于各个阶段并是其中重要组成部分。其根据软件开发的规格说明和软件的内部逻辑结构周密的设计一些测试用例集，并将设计好的测试用例输入到被测程序中，执行被测程序发现被测程序中的错误或缺陷。
众多软件测试研究方面的先驱给“软件测试”下过定义。其中，比较著名的有 G.J.Myers在其著作中定义软件测试为[18]：为了发现被测程序或系统中存在的错误或缺陷而执行的过程。软件工程技术委员会在 IEEE 计算机协会中将软件测试定义为[19]：为验证被测程序或系统是否符合其需求或者衡量其执行的实际结果与预期结果之间的差距而采用一些人工或者自动的方式进行验证或测试的过程。
第二章 测试用例生成理论与技术
2.1 软件测试的定义及目的
软件测试是保证软件的质量以及软件可靠性的有效手段。软件测试的目的是为了发现被测程序中可能存在的缺陷或错误，也就是说软件测试的目的是为了验证软件满足需求达到预期的功能。软件测试伴随着软件的开发、运行以及后期维护的始终，应用于各个阶段并是其中重要组成部分。其根据软件开发的规格说明和软件的内部逻辑结构周密的设计一些测试用例集，并将设计好的测试用例输入到被测程序中，执行被测程序发现被测程序中的错误或缺陷。
众多软件测试研究方面的先驱给“软件测试”下过定义。其中，比较著名的有 G.J.Myers在其著作中定义软件测试为[18]：为了发现被测程序或系统中存在的错误或缺陷而执行的过程。软件工程技术委员会在 IEEE 计算机协会中将软件测试定义为[19]：为验证被测程序或系统是否符合其需求或者衡量其执行的实际结果与预期结果之间的差距而采用一些人工或者自动的方式进行验证或测试的过程。
软件测试从用户的角度和软件开发者的角度分别有以下两种目的[20]：从用户的角度来看，希望软件测试发现被测程序中可能存在的缺陷或错误，来衡量可否接受该软件产品；从软件开发者的角度来看，希望软件测试发现被测程序中的可能存在或者隐藏着的缺陷或错误，通过修复程序的缺陷或错误提高软件的质量，为提高产品可靠性提供依据，或者验证程序中不存在缺陷或错误。G.J.Myer 认为软件测试的目的是在于发现被测程序中可能存在的缺陷或错误，测试用例能够发现被测程序中可能存在的缺陷或错误才是好的测试用例，该过程才是成功的软件测试。
众多学者投入到软件测试的学习和研究中，目前已经形成了规范的科学体系。软件测试从一个依靠经验和基于代码的测试活动演变为一个依据一定的科学手段建立模型进行分析并可以通过科学方法进行研究的学科。
..............................
2.2 测试用例基本概念
测试用例（Testing case）的生成是软件测试的关键。测试用例是为验证被测程序而专门设计的一组数据。其包含根据被测程序设计的输入数据、被测程序执行的条件以及输入该组数据后被测程序执行的预期结果。由于在设置测试用例时要依据被测程序而设计，往往比较复杂，为简化设计通常将重点放在测试用例的输入数据。
..........................
众多学者投入到软件测试的学习和研究中，目前已经形成了规范的科学体系。软件测试从一个依靠经验和基于代码的测试活动演变为一个依据一定的科学手段建立模型进行分析并可以通过科学方法进行研究的学科。
..............................
2.2 测试用例基本概念
测试用例（Testing case）的生成是软件测试的关键。测试用例是为验证被测程序而专门设计的一组数据。其包含根据被测程序设计的输入数据、被测程序执行的条件以及输入该组数据后被测程序执行的预期结果。由于在设置测试用例时要依据被测程序而设计，往往比较复杂，为简化设计通常将重点放在测试用例的输入数据。
由于在有限的时间或资源的情况下对被测程序进行穷举测试是行不通的，所以目前的软件测试都是不完全测试。为了利用有限的时间和资源尽可能多的发现软件的缺陷和错误，必须采用一些测试技术等手段。从不同的角度出发，软件测试技术被划分为不同的测试方法。从执行方式可以划分为人工测试和自动化测试[21]；从被测软件是否执行的角度，软件测试技术分为静态测试技术和动态测试技术[22]；从是否关心软件的内部逻辑及语法结构，软件测试技术为黑盒测试、白盒测试和灰盒测试。如图 2.1 为软件测试技术的不完全分类。
..........................
3.1 万有引力算法 ................................ 17
3.1.1 惯性质量................................ 17
3.1.2 引力 .................................... 18
第四章 基于 ITC-GSA 算法的多路径测试用例生成 ................................. 33
4.1 引言 .............................. 33
4.2 多路径测试用例生成 .................................. 33
4.3 适应度函数设计 ...................................... 36
第五章 基于 ITC-GSA 算法的组合测试用例生成 ..................................... 49
5.1 引言 .......................... 49
5.2 组合测试目的与相关定义 .............................. 49
第五章 基于 ITC-GSA 算法的组合测试用例生成
5.1 引言
目前，国内对于组合测试的研究还比较少。其中研究较多的是将遗传算法、粒子群算法引入到组合测试用例中，并对算法本身进行改进但是对引入后的适应度函数的改进较少。由于遗传算法和粒子群自身的缺点，在一定层度上会影响的组合测试用例的生成效率。本章在第三章 ITC-GSA 算法研究的基础上，提出了基于 ITC-GSA 算法的组合测试用例生成方法，同时根据组合测试的特点，设计了新的适应度函数计算方法，该方法基于覆盖强度和平均海明距离，能够有效的引导新的组合测试用例的生成。给出了基于 ITC-GSA 算法的组合测试用例生成的算法框架。通过实验与 GA、PSO、GSA 算法对比，验证所提算法及适应度函数应用在组合测试用例中是切实可行的并具有一定的优势。
........................
第六章 总结与展望
6.1 工作总结
目前，将智能搜索算法应用到测试用例生成中是软件测试研究的一个热点。通常是将遗传算法（GA）、粒子群算法（PSO）以及模拟退火算法（SA）引入到软件测试中，但这些算法都有其自身的缺陷。本文在对万有引力搜索算法（GSA）研究的基础上，对其进行改进提出了基于改进的 Tent 混沌万有引力搜索算法(ITC-GSA)，并将其运用到多路径测试用例生成和组合测试用例生成中。同时根据路径测试与组合测试各自的特点提出了新的适应度函数计算方法。本文主要研究内容及工作归纳如下：
（1）针对 GSA 算法的易陷入早熟收敛和局部最优、全局搜索能力较弱的缺点提出基于改进的 Tent 混沌万有引力搜索算法(ITC-GSA)。使用改进的 Tent 混沌映射来初始化种群;引入引力常数 G 的动态调整策略提高算法的收敛速度和收敛精度，设计成熟度指标判断种群成熟度并使用 Tent 混沌搜索有效抑制算法早熟收敛并帮助种群跳出局部最优。通过仿真实验表明改进的算法在收敛速度和寻优精度上都有极大的提升。
（2）将 ITC-GSA 算法应用到多路径测试用例生成中，针对多路径测试用例的特点，结合分支距离法和层接近度法，提出来了一种新的适应度计算方法，该方法根据新生成的测试用例覆盖的路径节点设置一个自适应权重。实验表明所提算法和设计的适应度函数在多路径测试用例的生成上具有一定的优势。
（2）将 ITC-GSA 算法应用到多路径测试用例生成中，针对多路径测试用例的特点，结合分支距离法和层接近度法，提出来了一种新的适应度计算方法，该方法根据新生成的测试用例覆盖的路径节点设置一个自适应权重。实验表明所提算法和设计的适应度函数在多路径测试用例的生成上具有一定的优势。
（3）将 ITC-GSA 算法应用到组合测试的测试用例生成中，在研究组合测试特点的基础上，提出结合覆盖强度和平均海明距离设计一种新的适应度函数计算方法，该方法将组合测试中已生成的测试用例集的影响考虑进来引导新的测试用例的生成。通过实验表明所提算法和设计的适应度函数相较于遗传算法、粒子群算法以及 GSA 算法在生成测试用例集的规模和时间上都有一定的优越性。
参考文献（略）
参考文献（略）