Covering Array Generation Ant Colony Alogrithm:Exploration,Mining And Applacation

Software testing is an essential quality assurance aspect in software engineering.As a kind of important software testing approach,combinatorial testing provides an effective way for detecting failures caused by the interactions of input parameters or system configurations.Covering array plays an important role in combinatorial testing.It systematically samples the configuration or input parameter space and ony the seleted test cases will be tested,hence it reduces the cost of testing.There have been many researches on how to generate as small as possible covering array;these methods can be roughly divided into three categories:mathematical methods,greedy algorithms and evolutionary search algorithms,these three methods have different characteristics and advantages.As there are no algorithms can generate minimum size for any covering arrays,covering array generatation problem still be a hot research topic in combinatorial testing.As an important evolutionary algorithm,ant colony algorithm can effectively solve various combinatorial optimization problems.At present,many studies show that ant colony algorithm can solve the covering array generation problem,variable strength covering array generation problem and prioritized interaction test suit generation problem,but these works havn't deeply investgated the performance of covering array generation ant colony algorithm.In order to analyze the performance of covering array generation ant colony algorithm,explore its ultimate ability on covering array generation,and research on the practical application of the alogrithm,this article carried out the following researches:(1)This article implements three variants of one-test-at-a-time covering array generation alogrithms based on ant system,ant colony system and min-max ant system,and then design a series of experiments to find out which variant algorithm is more suitable for solving the covering array generation problem;(2)Because of the performance of ant colony algorithm depends on the parameter configuration,and the size of parameter configuration combination space is very large,this article provides a fast and effective parameter configuration optimization method to find out the optimal algorithm parameter configuration;(3)Our research adjusts the structure of the solution and implements a new covering array generation ant colony algorithm which can evolve an array at a time.In order to explain the performance of our new algorithm,this article designs a group of experiments to compare the difference between our new method and the best so far result;(4)Our work supplies two case studies based on the latest research results of adaptive combinatorial testing:Linux Shell command testing and MicroSoft test Word 2010 font effects testing.These two case studies show how to using covering array generationa ant colony algorithm in the real combinatorial testing environment.Our research explores the ultimate ability of covering array generation ant colony algorithm from four aspects:algorithm parameter configuration optimization,algorithm variants comparison,solution structure adjustment and practical case study.The experimental results show that ant colony algorithm is an effective,potential and practical method for solving covering array generation problem.