Solving the Identifying Code Problem by a Genetic Algorithm

Identifying code is a concept in information theory and can be applied to problems of fault detection and location detection. In this paper, by assigning cost to every code word, we propose an optimization problem to find an identifying code with minimum cost and formulate the problem by an integer program. We generalize the results to the robust identifying code problem, which is proposed for poor environments. A tailored genetic algorithm is provided to solve the problem, and the experimental result shows that it is competitive for large-scale problems