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.

Ferone, D., Festa, P., Resende, M. (2016). Hybridizations of GRASP with path relinking for the far from most string problem. INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 23(3), 481-506 [10.1111/itor.12167].

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

Ferone, D;
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.
Articolo in rivista - Articolo scientifico
Combinatorial optimization; Consensus problems; Hybrid metaheuristics; String problems;
Combinatorial optimization; Consensus problems; Hybrid metaheuristics; String problems; Business and International Management; Computer Science Applications1707 Computer Vision and Pattern Recognition; Strategy and Management1409 Tourism, Leisure and Hospitality Management; Management Science and Operations Research; Management of Technology and Innovation
English
2016
23
3
481
506
none
Ferone, D., Festa, P., Resende, M. (2016). Hybridizations of GRASP with path relinking for the far from most string problem. INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 23(3), 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/10281/219757
Citazioni
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 12
Social impact