A Compounded Genetic and Simulated Annealing Algorithm for the Closest String Problem

The closest string problem is an NP-hard problem, which arises in computational molecular biology and coding theory. Its task is to find a string that minimizes maximum Hamming distance to a given set of strings. In this paper, a compounded genetic and simulated annealing algorithm (CGSA) which combines the merits of genetic algorithms and simulated annealing is presented to solve CSP. An adapting two-point crossover operator and a heuristic gene mutation operator designed by us are used in CGSA. In addition, by analyzing the optimal solution's structural features some rules are designed to pretreat the data, which reduces the problem size. We report computational results which show that the CGSA is capable of finding good solutions in a reasonable amount of time.