Minimum Covering Array Generation Using Success-History and Linear Population Size Reduction based Adaptive Differential Evolution Algorithm

Exhaustive testing of software systems with a large number of input parameters and combinations between them often causes the problem of combinatorial explosion. Combinatorial t-way testing is a technique that generates an array of test cases to maximize combinations covering of between input parameters. Generating a minimum covering array is an optimization problem that many strategies based on metaheuristic algorithms such as teaching and learning based optimization, particle swarm optimization, and genetic and cuckoo search algorithms have been used for solving it. Although these strategies have produced smaller covering arrays, complete minimization has not yet been performed. In this paper, we propose a new strategy based on the success-history and linear population size reduction based adaptive differential evolution algorithm (so-called LSHADE), which is one of winners of IEEE CEC competitions, to generate minimum covering array. The results of Friedman mean rank show that the LSHADE strategy has the first rank in terms of generating the covering array with the lowest size and the lowest average number of algorithmic calls, compared to mathematics based strategies such as TConfig, greedy strategies such as IPOG, Jenny and PICT and meta-heuristics such as GS, TLBO, HC-BAT, PSTG, WOA , BAPSO and GSTG. While, in terms of the average number of fitness function evaluations and the average runtime, this strategy has the first rank after the GS strategy. Moreover, the convergence diagrams confirm the high convergence speed of this strategy compared to the other meta-heuristic strategies.