A Tolerance-Based Memetic Algorithm for Constrained Covering Array Generation
Sponsor
Grant No. 62162046, Grant No. 2021GG0155, Grant No. 2019ZD15, Grant No. 2019GG372
Published In
Memetic Computing
Document Type
Citation
Publication Date
8-29-2023
Abstract
The research focus in the field of combinatorial testing has shifted from unconstrained covering array generation (CAG) to constrained covering array generation (CCAG). Most heuristic search algorithms exclude all invalid solutions from the search space so that all intermediate and final solutions satisfy the constraints. However, some values of intermediate solutions that are sometimes invalid may help in finding the optimal solution. Therefore, such solutions may need to be "tolerated" in the generation process. This paper proposes a tolerance-based memetic algorithm named QSMA that employs quantum particle swarm optimization (QPSO) as a global searching operator and improved simulated annealing as a local searching operator to balance exploration and exploitation synergistically. Meanwhile, QSMA incorporates a stochastic ranking strategy to address the challenge of setting the penalty coefficient. Besides, a specific penalty function is proposed to deal with constraints, and design guidelines for penalty functions are suggested. In the experiment, the impacts of parameter settings on the performance of QSMA are investigated. Extensive experimental results show that the QSMA algorithm outperforms other methods and tools for both CAG and CCAG problems.
Rights
Copyright Spring Nature 2023
Locate the Document
DOI
10.1007/s12293-023-00392-1
Persistent Identifier
https://archives.pdx.edu/ds/psu/40876
Publisher
Springer Nature
Citation Details
Guo, X., Song, X., Zhou, J., & Wang, F. (2023). A tolerance-based memetic algorithm for constrained covering array generation. Memetic Computing, 15(3), 319–340.