Memetic Algorithm for Constructing Covering Arrays of Variable Strength Based on Global- Best Harmony Search and Simulated Annealing

摘要

Covering Arrays (CA) are mathematical objects widely used in the design of experiments in several areas of knowledge and of most recent application in hardware and software testing. CA construction is a complex task that entails a high run time and high computational load. To date, research has been carried out for constructing optimal CAs using exact methods, algebraic methods, Greedy methods, and metaheuristic-based methods. These latter, including among them Simulated Annealing and Tabu Search, have reported the best results in the literature. Their effectiveness is largely due to the use of local optimization techniques with different neighborhood schemes. Given the excellent results of Global-best Harmony Search (GHS) algorithm in various optimization problems and given that it has not been explored in CA construction, this paper presents a memetic algorithm (GHSSA) using GHS for global search, SA for local search and two neighborhood schemes for the construction of uniform and mixed CAs of different strengths. GHSSA achieved competitive results on comparison with the state of the art and in experimentation did not require the use of supercomputers.