覆盖表生成的遗传算法配置参数优化

覆盖表生成是组合测试的关键问题,很多数学方法、贪心算法以及演化搜索方法等被应用于生成各种覆盖表.针对演化搜索方法的性能受到方法本身配置参数影响很大这一实际问题,文中以二维覆盖表生成为实例,系统地对典型的演化搜索方法——遗传算法的种群规模、进化代数、交叉概率、变异概率以及遗传算法的变种算法等因素进行探索,设计了pair-wise法、Base choice法和爬山法3条实验路线探索遗传算法的这些配置参数及其相互作用对算法生成二维覆盖表效果的影响,并回答两个问题:对于特定二维覆盖表生成问题,是否存在遗传算法的最优参数配置；对于一般的二维覆盖表生成问题,是否存在通用的遗传算法最优参数配置.

The Optimization of Configurable Genetic Algorithm for Covering Arrays Generation

Covering array generation is one of the key issues in combinatorial testing.Many mathematical methods,greedy algorithms and evolutionary search methods have been applied in this field.Since the performance of evolutionary search methods is significantly impacted by their configurable parameters,we take genetic algorithm,one of the typical evolutionary search methods,as an example to discuss the different influences of its five configurable parameters(population size,evolution generation,crossover probability,mutation probability,variants of the algorithm) on the performance of 2-way covering array generation.Meanwhile we design three classes of experiments to systemically analyze the influences of each of the configurable parameters and the interactions among them.Our contributions are to answer the following questions: whether there exists an optimal configuration of genetic algorithm for a particular 2-way covering array generation and whether there exists a common optimal configuration for all 2-way covering arrays generation.