T-Way Combinatorial Testing Strategy Using a Refined Evolutionary Heuristic

In complex testing scenarios of large-scale information systems, communication networks, and the Internet of Things, exhaustive testing is always prohibitively expensive and time-consuming. T-way combinatorial testing has emerged as a cost-effective solution. To address the problem of generating test suites for t-way combinatorial testing, a Logical Combination Index Table (LCIT) is proposed. Utilizing the LCIT, the t-way combinatorial coverage model (t-wCCM) is constructed to guide the test case generation process. Multi-start Construction Procedure (MsCP) algorithm is employed to generate an initial solution set, and then local optimization is performed using a low-complexity Balanced Local Search (BLS) algorithm. Further, Evolutionary Path Relinking combined with the BLS (EvPR + BLS) algorithm is proposed to accelerate the convergence process. Experiments show that the proposed Refined Evolutionary Heuristic (REH) algorithm performs best on 50% of the classic test instances, and performs superior to the average on 66% of the test instances, with a relative improvement in the maximum computation time of approximately 33.33%.