Combinatorial Test Generation Using Improved Harmony Search Algorithm

Combinatorial testing method can ensure the capability of error detection and use the smaller test case sets. to detect the software faults from the interaction between the complex factors in the system The construction of the test case sets is a NP complete problem. The existing methods are based on the greedy or heuristic algorithm to generate a combinatorial test case, and through the improvement of these algorithms to improve the test case generation efficiently and reduce the size of test case sets effectively. In practice, a software system is usually composed of many complex factors, which are combined with each other. In order to use a few test cases to test the interaction between the various parameters of the system, the researchers put forward the variable strength t-way combinatorial testing method. As a scientific and effective testing method, the variable strength t-way combinatorial testing method has become one of the key issues in the field of combinatorial testing. In this paper, we review and sum up the existing techniques for the generation of combinatorial test case, and make a further research on the generation between the constraint of the parameters and the variable intensity of it. Thus, we propose two algorithms, which are based on the Harmony Search Algorithm(HSA) to generate combinatorial test cases. Specific contributions can be summarized as the following three aspects:(1)Propose the Multi-HM Competitive Harmony Search Algorithm(MHCHS) to generate the combinatorial test cases by improving the generation of the initial Harmony Memory(HM) based on the HSA. A new solution generated by the standard HSA directly affected by the initial HM. We use the multiple small-scale HM instead of a large-scale HM to update the HM independently, and be inspired from the idea that populations in the nature achieve the common development by cooperation and competition to each other, the new better generated solution should be used to update multiple small-scale HM.In this way to improve the quality of the solution in the HM and to enhance the searching ability of MHCHS. Finally, analyze the generated size of combinatorial test cases influenced by the initial value of the parameters in the algorithm in detail.(2)Propose the Catastrophe Strategy Bat-Harmony Search Algorithm(CSBHS) to generate the combinatorial test cases by adjusting the parameters HMCR and PAR adaptively based on the HSA, then put forward the catastrophe strategy in CSBHS to prevent the algorithm falling into the local. Similarly, analyze the generated size of combinatorial test cases influenced by the initial value of the parameters in the algorithm in detail and make a fully analysis on the influence of the catastrophe strategy in the CSBHS.(3)The best parameter values will be brought into the MHCHS and CSBHS to verify the other examples of combinatorial testing, then take the generated size of combinatorial test cases influenced by the two improved algorithm into consideration seriously.Experiments show that the two improved harmony search algorithm in different system configurations need to select suitable initial values of the parameters to help optimal solution generation. Comparing MHCHS and CSBHS strategies with the standard HSA, the former can generate smaller test case sets in dealing with the problem of variable interaction strength and constraint of the parameters than the later. In addition, the introduction of catastrophe strategy in the CSBHS can improve the final test case size effectively.