覆盖表生成的粒子群算法:参数优化和自适应算法

Particle Swarm Optimization for Covering Array Generation:Parameter Optimization and Adaptive Algorithm

组合测试是一种能有效检测由参数间相互作用所引发错误的软件测试方法,覆盖表的生成是该研究领域的一个重要问题.目前,很多方法已被应用于覆盖表生成,基于演化搜索的粒子群算法尽管能得到较优的解,但其性能容易受到配置参数的影响.本文首先使用试验设计的方法,对不同覆盖表生成的算法参数进行优化,系统分析了参数对算法性能的影响.同时,考虑到对不同的覆盖表,最优的算法参数往往不同,因此进一步提出了一种适用于覆盖表生成的自适应粒子群算法.实验结果表明,在一定的参数取值范围内粒子群算法都能获得较好的结果,且不存在一组对任意覆盖表都能有最优性能的算法参数.通过参数调优,能使粒子群算法获得比已有结果规模更小的覆盖表,同时,与经过参数调优后的算法相比,自适应粒子群算法在大部分情况下有更好的性能.

Combinatorial testing is an effective software testing method which can detect the failures triggered by various factors and their interactions. Covering array generation is one of the key issues in this field. In recent years, many methods have been applied for covering array generation. Particle swarm optimization （PSO）, one of the evolutionary search based methods, can achieve near smallest covering arrays, but its performance is significantly impacted by the parameters. In this paper, we firstly optimize four parameters by design of experiment method, to systemically analyze the influences of parameters on the performance of PSO. Secondly, taking into account that the optimal parameters are often different when generating different covering arrays, we propose a new adaptive PSO algorithm to further improve the performance of PSO. Our experiment shows that, PSO can work well under a group of configurations. Through parameter optimization, PSO can generate smaller covering arrays than the existing results, and the adaptive PSO can obtain better results.