A GRASP algorithm for the Closest String Problem using a probability-based heuristic

Publication year: 2012
Source: Computers & Operations Research, Volume 39, Issue 2, February 2012, Pages 238-248

Sayyed Rasoul, Mousavi , Navid, Nasr Esfahani

The Closest String Problem (CSP) is the problem of finding a string whose Hamming distance from the members of a given set of strings of the same length is minimal. It has applications, among others, in bioinformatics and in coding theory. Several approximation and (meta)heuristic algorithms have been proposed for the problem to achieve ‘good’ but not necessarily optimal solutions within a reasonable time. In this paper, a new algorithm for the problem is proposed, based on a Greedy Randomized Adaptive Search Procedure (GRASP) and a novel probabilistic heuristic function. The algorithm is compared with three recently proposed algorithms for…