随着信息技术在社会生产应用中的快速发展,计算机软件在信息系统中的作用日益重要,也变得复杂且庞大。在一些关键应用领域中如何保证软件的高可靠性已成为一个严峻课题。软件测试是保障软件质量和可靠性的重要手段,而测试用例生成是软件测试的核心所在。传统方法中,手动生成测试用例对于软件测试人员而言是一个极其复杂和繁琐的体力劳动,不仅成本高且容易出错。自动化测试技术通过测试用例的自动化生成并驱动程序执行,有效地保证了测试效率和效果并控制了测试成本。基于搜索的测试生成技术是近年来新兴的软件测试技术,通过将测试用例生成转化为一个搜索过程,已取得重大研究进展并在软件生产实践中成功实用。进化测试是一种重要测试用例自动生成技术,用于结构性测试方法时仍面临很多问题,在面向节点的测试准则下对非结构化程序进行测试就是其中之一,程序中任意跳转语句的引入(如goro),程序的控制流呈现非结构化形式。任意跳转语句的使用使程序的控制流变得复杂和不明确,尤其在循环体内部出现时,循环的边界难以确定,数据依赖和控制依赖分析变得更加困难。由于进化搜索的目标函数构造依赖于数据和控制依赖分析,于是非结构化控制流带来传统进化测试的失效或效率低下。因此必须针对此类应用程序设计合理的目标函数,为进化搜索提供利于搜索进展的导向。数据依赖是一类重要的程序依赖,测试人员通过程序中变量的定义和使用情况来分析数据间的相互依存关系,数据流分析是结构性测试和程序切片的基础。一定意义上基于数据流的测试其实就是路径测试。与控制依赖类似,在选定路径中由于标志变量的使用导致数据依赖的缺失同样影响进化测试的效率,此外标志变量特有的程序特性使进化搜索失去导向。因此进化测试的目标函数应充分考虑数据依赖信息,并通过程序易测性转换改变不良的程序特征从而引导进化搜索。已有的循环体中标志变量移除方法不能有效地处理诸如多分支赋值、break语句和半临界分支等情况,而需要改进。工业实践中,多目标优化技术被广泛地应用于解决含有多目标和多约束的优化问题。覆盖和测试代价等通常作为衡量一个测试用例集的优劣程度,因此测试数据生成需要考虑多方面因素,于是多目标优化方法得以应用于基于搜索的结构性测试。以进化测试为代表,基于搜索的测试用例自动生成方法取得不错的进展,但该方法的效率受限于大的搜索空间和特殊的程序结构,此外基于单条路径的测试生成其效果不佳。测试用例集生成的多目标优化一方面保证了用例集的优化,使之具备较高的程序覆盖同时限制了用例个数;另一方面复杂程序结构不会带来不必要的进化搜索,而仅依赖于程序执行,于是测试自动化得以实现。多目标进化算法中,多样性保持直接影响最终Pareto前沿的质量,传统方法多采用基于距离的概念。平均覆盖密度描述了某用例集T提供的覆盖信息,其值越小表示T提供的覆盖越大,亦能体现T关于程序覆盖的多样性。覆盖和用例个数的比值描述了精英强度,在进行繁殖选择时,具备较高强度的个体拥有更强的繁殖能力。此外,不同于传统进化算法,针对用例集的交叉和变异算子进行特别设计。