A Simulated Annealing Algorithm to Construct Covering Perfect Hash Families

Abstract EN

Covering perfect hash families (CPHFs) are combinatorial designs that represent certain covering arrays in a compact way.

In previous works, CPHFs have been constructed using backtracking, tabu search, and greedy algorithms.

Backtracking is convenient for small CPHFs, greedy algorithms are appropriate for large CPHFs, and metaheuristic algorithms provide a balance between execution time and quality of solution for small and medium-size CPHFs.

This work explores the construction of CPHFs by means of a simulated annealing algorithm.

The neighborhood function of this algorithm is composed of three perturbation operators which together provide exploration and exploitation capabilities to the algorithm.

As main computational results we have the generation of 64 CPHFs whose derived covering arrays improve the best-known ones.

In addition, we use the simulated annealing algorithm to construct quasi-CPHFs from which quasi covering arrays are derived that are then completed and postoptimized; in this case the number of new covering arrays is 183.

Together, the 247 new covering arrays improved the upper bound of 683 covering array numbers.