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: | Resende Mauricio G C, Festa Paola, Ferone Daniele |
Keywords: | biology, heuristics |
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.