×

zbMATH — the first resource for mathematics

Hybridizations of GRASP with path relinking for the far from most string problem. (English) Zbl 1342.90161
Summary: 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.

MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aiex, Probability distribution of solution time in grasp: an experimental investigation, Journal of Heuristics 8 pp 343– (2002) · Zbl 1012.68795 · doi:10.1023/A:1015061802659
[2] Blum, Proceedings of the 14th European Conference on Evolutionary Computation in Combinatorial Optimisation (EvoCOP2014), Lecture Notes in Computer Science pp 1– (2014)
[3] Canuto, Local search with perturbations for the prize-collecting Steiner tree problem in graphs, Networks 38 pp 50– (2001) · Zbl 1014.90078 · doi:10.1002/net.1023
[4] Coffin, Statistical analysis of computational tests of algorithms and heuristics, INFORMS Journal on Computing 12 (1) pp 24– (2000) · Zbl 1034.90020 · doi:10.1287/ijoc.12.1.24.11899
[5] Leone, Solving a bus driver scheduling problem with randomized multistart heuristics, International Transactions in Operational Research 18 (6) pp 707– (2011) · Zbl 1267.90058 · doi:10.1111/j.1475-3995.2011.00827.x
[6] Faria, Transmission network design by a greedy randomized adaptive path relinking approach, IEEE Transactions on Power Systems 20 (1) pp 43– (2005) · doi:10.1109/TPWRS.2004.835627
[7] Feo, A probabilistic heuristic for a computationally difficult set covering problem, Operations Research Letters 8 pp 67– (1989) · Zbl 0675.90073 · doi:10.1016/0167-6377(89)90002-3
[8] Feo, Greedy randomized adaptive search procedures, Journal of Global Optimization 6 pp 109– (1995) · Zbl 0822.90110 · doi:10.1007/BF01096763
[9] Ferone, Proceedings of 8th International Workshop on Hybrid Metaheuristics, Lecture Notes in Computer Science, Volume 7919 pp 174– (2013)
[10] Festa, On some optimization problems in molecular biology, Mathematical Bioscience 207 (2) pp 219– (2007) · Zbl 1117.92026 · doi:10.1016/j.mbs.2006.11.012
[11] Festa, GRASP with path-relinking for the weighted MAXSAT problem, ACM Journal of Experimental Algorithmics 11 pp 1– (2006) · Zbl 1140.68403
[12] Festa, Randomized heuristics for the MAX-CUT problem, Optimization Methods and Software 7 pp 1033– (2002) · Zbl 1032.90073 · doi:10.1080/1055678021000090033
[13] Festa, Essays and Surveys on Metaheuristics pp 325– (2002) · doi:10.1007/978-1-4615-1507-4_15
[14] Festa, An annotated bibliography of GRASP-Part I: algorithms, International Transactions in Operational Research 16 (1) pp 1– (2009a) · Zbl 1153.90553 · doi:10.1111/j.1475-3995.2009.00663.x
[15] Festa, An annotated bibliography of GRASP-Part II: applications, International Transactions in Operational Research 16 (2) pp 131– (2009b) · Zbl 1168.90582 · doi:10.1111/j.1475-3995.2009.00664.x
[16] Festa, Hybrid Metaheuristics-Studies in Computational Intelligence, Vol. 434 pp 135– (2013)
[17] Frances, On covering problems of codes, Theory of Computing Systems 30 (2) pp 113– (1997) · Zbl 0868.94056 · doi:10.1007/BF02679443
[18] Glover, Interfaces in Computer Science and Operations Research pp 1– (1996)
[19] Glover, Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research pp 1– (2000) · doi:10.1007/978-1-4615-4567-5_1
[20] Glover, Tabu Search (1997) · doi:10.1007/978-1-4615-6089-0
[21] Glover, Fundamentals of scatter search and path relinking, Control and Cybernetics 39 pp 653– (2000) · Zbl 0983.90077
[22] Gramm , J. Hüffner , F. Niedermeier , R. 2002 Closest strings, primer design, and motif search Sixth Annual International Conference on Computational Molecular Biology, RECOMB 2002, Washington, DC 74 75
[23] Laguna, GRASP and path relinking for 2-layer straight line crossing minimization, INFORMS Joutnal on Computing 11 pp 44– (1999) · Zbl 1092.90544 · doi:10.1287/ijoc.11.1.44
[24] Lanctot, Distinguishing string selection problems, Information and Computation 185 (1) pp 41– (2003) · Zbl 1069.68116 · doi:10.1016/S0890-5401(03)00057-9
[25] Li , M. Ma , B. Wang , L. 1999 Finding similar regions in many strings ACM Symposium on Theory of Computing (STOC’99), Atlanta, GA 473 482
[26] Macario, Gene Probes for Bacteria (1990)
[27] Meneses, Optimization techniques for string selection and comparison problems in genomics, IEEE Engineering in Medicine and Biology Magazine 24 (3) pp 81– (2005) · doi:10.1109/MEMB.2005.1436464
[28] Morán-Mirabal, Randomized heuristics for the family traveling salesperson problem, International Transactions in Operational Research 21 (1) pp 41– (2014) · Zbl 1291.90206 · doi:10.1111/itor.12026
[29] Mousavi, An improved heuristic for the far from most strings problem, Journal of Heuristics 18 pp 239– (2012) · Zbl 06700345 · doi:10.1007/s10732-011-9177-z
[30] Resende, GRASP and path relinking for the max-min diversity problem, Computers and Operations Research 37 pp 498– (2010) · Zbl 1173.90521 · doi:10.1016/j.cor.2008.05.011
[31] Resende, A hybrid heuristic for the p-median problem, Journal of Heuristics 10 pp 59– (2004) · Zbl 1069.68600 · doi:10.1023/B:HEUR.0000019986.96257.50
[32] Ribeiro, Path-relinking intensification methods for stochastic local search algorithms, Journal of Heuristics 18 pp 193– (2012) · Zbl 06700343 · doi:10.1007/s10732-011-9167-1
[33] Ribeiro, Efficient parallel cooperative implementations of GRASP heuristics, Parallel Computing 33 pp 21– (2007) · doi:10.1016/j.parco.2006.11.007
[34] Ribeiro, Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms, Journal of Global Optimization 54 pp 405– (2012) · Zbl 1259.90115 · doi:10.1007/s10898-011-9769-z
[35] Romero, Analysis and design of peer-assisted video-on-demand services, International Transactions in Operational Research 21 (4) pp 559– (2014) · Zbl 1308.90027 · doi:10.1111/itor.12086
[36] Sim , J.S. Park , K. 1999 The consensus string problem for a metric is N P -complete Proceedings of the Annual Australiasian Workshop on Combinatorial Algorithms (AWOCA), Curtin University of Technology, Perth, Australia 107 113
[37] Wilcoxon, Individual comparisons by ranking methods, Biometrics Bulletin 1 (6) pp 80– (1945) · doi:10.2307/3001968
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.