Hybridizations of GRASP with path relinking for the far from most string problem

Hybridizations of GRASP with path relinking for the far from most string problem

0.00 Avg rating0 Votes
Article ID: iaor201682
Volume: 23
Issue: 3
Start Page Number: 481
End Page Number: 506
Publication Date: May 2016
Journal: International Transactions in Operational Research
Authors: , ,
Keywords: biology, heuristics
Abstract:

Among the sequence selection and comparison problems, the far from most string problem (FFMSP) is one of the computationally hardest with applications in several fields, including molecular biology where one is interested in creating diagnostic probes for bacterial infections or in discovering potential drug targets. In this paper, we describe several heuristics that hybridize GRASP with different path‐relinking strategies, such as forward, backward, mixed, greedy randomized adaptive forward, and evolutionary path relinking. Experiments on a large set of both real‐world and randomly generated test instances indicate that these hybrid heuristics are both effective and efficient. In particular, the hybrid GRASP with evolutionary path relinking finds slightly better quality solutions compared to the other variants when running for the same number of iterations, while the hybrid with backward path relinking finds better quality solution within a fixed running time.

Reviews

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