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.

Hybridizations of GRASP with path relinking for the far from most string problem / Ferone, Daniele; Festa, Paola; Resende, Mauricio G. C.. - In: INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH. - ISSN 0969-6016. - 23:3(2016), pp. 481-506. [10.1111/itor.12167]

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

FERONE, DANIELE;FESTA, PAOLA;
2016

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.
2016
Hybridizations of GRASP with path relinking for the far from most string problem / Ferone, Daniele; Festa, Paola; Resende, Mauricio G. C.. - In: INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH. - ISSN 0969-6016. - 23:3(2016), pp. 481-506. [10.1111/itor.12167]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/662144
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 11
social impact