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

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

0.00 Avg rating0 Votes
Article ID: iaor20116238
Volume: 39
Issue: 2
Start Page Number: 238
End Page Number: 248
Publication Date: Feb 2012
Journal: Computers and Operations Research
Authors: ,
Keywords: greedy algorithms, metaheuristics, GRASP, closest string
Abstract:

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 CSP, outperforming all of them by achieving solutions of higher quality within a few seconds in most of the experimental cases.

Reviews

Required fields are marked *. Your email address will not be published.