软件回归测试是软件质量保障的重要步骤,但软件回归测试耗时巨大,频繁运行软件回归测试过程可能会严重影响软件开发进度。测试用例优先排序是软件回归测试中的一种重要优化技术,能够有效提升软件回归测试的效率。相比于另外两种优化技术——测试用例选择与测试用例集最小化,测试用例优先排序由于不约减测试用例,所以更有可能发现软件隐藏的故障。软件测试用例优先排序目标是寻找一个最优的测试用例执行顺序,搜索空间为测试用例集的全排列,为NP完全问题,求解难度较大。同时,随着现代软件工业界对测试用例优先排序效率与结果要求的提升,多目标测试用例优先排序技术被引入用以提升优先排序过程效果,这又进一步加大了问题求解难度。因此,基于搜索软件工程的技术常被用于解决相关问题,其中基于搜索技术的单/多目标测试用例优先排序技术是本文研究的主要对象。主要研究工作以及特色包括:1.基于CPU+GPU的异构并行的测试用例优先排序优化研究随着工业软件规模与软件测试用例规模的不断增加,对软件测试用例优先排序问题提出了新的挑战,对算法效率提出了更高的要求。本文利用元启发式搜索算法的潜在并行性,提出了面向测试用例优先排序的CPU+GPU的异构并行优化技术,借助图形处理器(GPU)辅助CPU进行并行计算,以较低的成本实现基于多核多线程并行的优先排序算法优化策略。本文重点研究了 CPU+GPU异构模式下的多目标测试用例优先排序并行化技术。具体研究角度有:(1)该部分首先针对算法中耗时较大的适应度函数计算进行优化并行研究,实现了适应度函数GPU并行优化算法。(2)针对不同并行粒度对于交叉操作的影响,研究了 GPU并行模式下最优的交叉操作策略。(3)考虑异构模式下内存与显存数据传输的成本,针对算法迭代中不同的并行策略以及对应并行加速效果开展讨论,得到了不同规模程序下的最优并行策略。针对以上三个角度的研究,最终实现了在CPU+GPU异构模式下多目标测试用例优先排序的最优加速策略。2.融合上位基因理论的进化算法优化研究基于遗传算法的进化计算算法是根据达尔文“进化论”以及现代“基因理论”所产生的模拟生物进化过程的一类算法,其理论基础是生物基因学。但目前的进化计算实现过程中,并没有涉及现代基因理论的研究成果。然而,结合测试用例优先排序问题背景和算法理论知识,可以有效提升算法效率。上位基因理论反映了进化过程中基因位之间的相互依赖关系。在测试用例优先排序问题当中,本文通过融合上位基因理论,定义了上位基因段的概念。通过挖掘测试用例之间的相互依赖关系,优化元启发式搜索算法的操作。具体研究步骤为:(1)根据上位基因段的指导,分别优化了单点交叉和顺序交叉两种操作,提出在进化过程中生成新个体需要有所改变,同时改变结果不能过大的特点。(2)实验通过与现有最优交叉操作比较,以及在单/多目标优化测试用例优先排序问题中与传统交叉操作结果进行了验证。通过以上两个研究步骤,最终实验表明基于上位基因段优化后的进化算法可以提升测试用例优先排序算法运行效率。3.面向自适应搜索的测试用例优先排序优化研究在多目标测试用例优先排序领域中,存在众多种类的多目标优化算法,且各具特点。在不同的测试场景中,由于被测程序特点不同,测试目标根据软件工程需求不断变化,没有一个通用的框架能够适应各个不同的测试情况,因此很难针对特定场景选择最优的搜索算法。基于超启发式策略的自适应算法框架能够根据各个算法与被测程序之间的反馈信息,动态调整所使用的元启发式算法,适应不同测试场景。具体研究策略为:(1)本文通过研究各种不同类型的多目标元启发式算法,构建了底层算法库,实现了算法无缝切换。(2)研究了多目标问题中的动态评价指标,能够根据算法反馈信息,动态评价算法执行优劣,实现了超启发层自适应调整策略。(3)设计并实现基于超启发式策略的自适应算法框架,为多目标测试用例优先排序问题建立了一套通用算法框架。最终通过实验证明,针对不同被测程序,动态自适应框架能够根据被测程序特点,选择合适的算法以达到较好的执行结果。通过以上三个方面的研究,本文针对测试用例优先排序问题,在硬件层面,采用了先进的异构并行计算提升效率使得基于搜索技术的测试用例优先排序在工业领域的应用成为可能;在理论层面,从搜索算法的理论基础出发,融合基因理论中的上位基因概念,针对测试用例优先排序问题的特征,进一步优化算法。最后,针对众多搜索算法选择问题,提出了面向测试用例优先排序的超启发式搜索算法框架,实现了基于搜索算法的通用测试用例优先排序框架,有效改进了多目标测试用例优先排序的算法效率。