An important branch of hybrid metaheuristics concerns the hybridization with branch & bound derivatives. In this chapter we present examples for two different types of hybridization. The first one concerns the use of branch & bound features within construction-based metaheuristics in order to increase their efficiancy. The second example deals with the use of a metaheuristic, in our case a memetic algorithm, in order to increase the efficiancy of branch & bound, respectively branch & bound derivatives such as beam search. The quality of the resulting hybrid techniques is demonstrated by means of the application to classical string problems: the longest common subsequence problem and the shortest common supersequence problem.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
A. Aho, J. Hopcroft, and J. Ullman. Data structures and algorithms. Addison-Wesley, Reading, MA, 1983.
S. Al-Shihabi. Backtracking ant system for the traveling salesman problem. In M. Dorigo, M. Birattari, C. Blum, L. M. Gambardella, F. Mondada, and T. Stützle, editors, Proceedings of ANTS 2004 – 4th International Workshop on Ant Colony Optimization and Swarm Intelligence, volume 3172 of Lecture Notes in Computer Science, pages 318–325. Springer-Verlag, Berlin, 2004.
M. J. Blesa and C. Blum. Ant colony optimization for the maximum edge-disjoint paths problem. In G. R. Raidl et al., editors, Applications of Evolutionary Computing, Proceedings of EvoWorkshops 2004, volume 3005 of Lecture Notes in Computer Science, pages 160–169. Springer-Verlag, Berlin, 2004.
C. Blum. Beam-ACO–hybridizing ant colony optimization with beam search: an application to open shop scheduling. Computers and Operations Research, 32:1565–1591, 2005.
C. Blum, J. Bautista, and J. Pereira. Beam-ACO applied to assembly line balancing. In M. Dorigo, L. M. Gambardella, A. Martinoli, R. Poli, and T. Stützle, editors, Proceedings of ANTS 2006 – Fifth International Workshop on Swarm Intelligence and Ant Algorithms, volume 2463 of Lecture Notes in Computer Science, pages 14–27. Springer-Verlag, Berlin, Germany, 2006.
C. Blum, C. Cotta, A. J. Fernández, and J. E. Gallardo. A probabilistic beam search algorithm for the shortest common supersequence problem. In C. Cotta et al., editor, Proceedings of EvoCOP 2007 – Seventh European Conference on Evolutionary Computation in Combinatorial Optimisation, volume 4446 of Lecture Notes in Computer Science, pages 36–47. Springer-Verlag, Berlin, Germany, 2007.
C. Blum and M. Dorigo. The hyper-cube framework for ant colony optimization. IEEE Transactions on Systems, Man, and Cybernetics – Part B, 34(2):1161–1172, 2004.
J. Branke, M. Middendorf, and F. Schneider. Improved heuristics and a genetic algorithm for finding short supersequences. OR-Spektrum, 20:39–45, 1998.
S. Casey and J. Thompson. GRASPing the examination scheduling problem. In E. K. Burke and P. De Causmaecker, editors, Proceedings of PATAT 2002 – 4th International Conference on Practice and Theory of Automated Timetabling, volume 2740 of Lecture Notes in Computer Science, pages 232–246. Springer-Verlag, Berlin, 2003.
C. Cotta. Protein structure prediction using evolutionary algorithms hybridized with backtracking. In J. Mira and J. R. Álvarez, editors, Proceedings of the 7th International Work-Conference on Artificial and Natural Neural Networks (IWANN 2003), volume 2687 of Lecture Notes in Computer Science, pages 321–328. Springer-Verlag, Berlin, 2003.
C. Cotta. Memetic algorithms with partial lamarckism for the shortest common supersequence problem. In J. Mira and J. R. Álvarez, editors, Artificial Intelligence and Knowledge Engineering Applications: a Bioinspired Approach, number 3562 in Lecture Notes in Computer Science, pages 84–91, Berlin Heidelberg, 2005. Springer-Verlag.
M. Dorigo and T. Stuetzle. Ant Colony Optimization. MIT Press, 2004.
T. A. Feo and M. G. C. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133, 1995.
D. E. Foulser, M. Li, and Q. Yang. Theory and algorithms for plan merging. Artificial Intelligence, 57(2-3):143–181, 1992.
C. B. Fraser. Subsequences and supersequences of strings. PhD thesis, University of Glasgow, 1995.
J. E. Gallardo, C. Cotta, and A. J. Fernández. On the hybridization of memetic algorithms with branch-and-bound techniques. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 37(1):77–83, 2007.
D. Gusfield. Algorithms on Strings, Trees, and Sequences. Computer Science and Computational Biology. Cambridge University Press, Cambridge, 1997.
M. T. Hallet. An integrated complexity analysis of problems from computational biology. PhD thesis, University of Victoria, 1996.
W. E. Hart, N. Krasnogor, and J. E. Smith. Recent Advances in Memetic Algorithms. Springer-Verlag, Berlin Heidelberg, 2005.
J. N. Hooker. Unifying local and exhaustive search. In L. Villaseñor and A. I. Martinez, editors, Proceedings of ENC 2005 – Sixth Mexican International Conference on Computer Science, pages 237–243. IEEE press, 2005.
C. Houck, J. A. Joines, M. G. Kay, and J. R. Wilson. Empirical investigation of the benefits of partial lamarckianism. Evolutionary Computation, 5(1):31–60, 1997.
K. Huang, C. Yang, and K. Tseng. Fast algorithms for finding the common subsequences of multiple sequences. In Proceedings of the International Computer Symposium, pages 1006–1011. IEEE press, 2004.
N. Krasnogor and J. E. Smith. A tutorial for competent memetic algorithms: model, taxonomy, and design issues. IEEE Transactions on Evolutionary Computation, 9(5):474–488, 2005.
G. B. Lamont, S. M. Brown, and G. H. Gates Jr. Evolutionary algorithms combined with deterministic search. In V. W. Porto, N. Saravanan, D. E. Waagen, and A. E. Eiben, editors, Proceedings of Evolutionary Programming VII, 7th International Conference, volume 1447 of Lecture Notes in Computer Science, pages 517–526. Springer-Verlag, Berlin, 1998.
E. Lawler and D. Wood. Branch and bound methods: A survey. Operations Research, 4(4):669–719, 1966.
D. Maier. The complexity of some problems on subsequences and supersequences. Journal of the ACM, 25:322–336, 1978.
V. Maniezzo. Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem. INFORMS Journal on Computing, 11(4):358–369, 1999.
V. Maniezzo and A. Carbonaro. An ANTS heuristic for the frequency assignment problem. Future Generation Computer Systems, 16:927–935, 2000.
V. Maniezzo and M. Milandri. An ant-based framework for very strongly constrained problems. In M. Dorigo, G. Di Caro, and M. Sampels, editors, Proceedings of ANTS 2002: 3rd International Workshop on Ant Algorithms, volume 2463 of Lecture Notes in Computer Science, pages 222–227. Springer-Verlag, Berlin, 2002.
M. Middendorf. More on the complexity of common superstring and supersequence problems. Theoretical Computer Science, 125:205–228, 1994.
P. Moscato and C. Cotta. A gentle introduction to memetic algorithms. In Handbook of Metaheuristics, pages 105–144. Kluwer Academic Press, Boston, Massachusetts, USA, 2003.
E. Nowicki and C. Smutnicki. A fast taboo search algorithm for the job-shop problem. Management Science, 42(2):797–813, 1996.
P. S. Ow and T. E. Morton. Filtered beam search in scheduling. International Journal of Production Research, 26:297–307, 1988.
J. Puchinger and G. R. Raidl. Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification. In J. Mira and J. R. Álvarez, editors, Artificial Intelligence and Knowledge Engineering Applications: a Bioinspired Approach, number 3562 in Lecture Notes in Computer Science, pages 41–53, Berlin Heidelberg, 2005. Springer-Verlag.
S. Rahmann. The shortest common supersequence problem in a microarray production setting. Bioinformatics, 19(Suppl. 2):ii156–ii161, 2003.
S. J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 2003.
J. S. Sim and K. Park. The consensus string problem for a metric is NP-complete. Journal of Discrete Algorithms, 1(1):111–117, 2003.
T. Smith and M. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147(1):195–197, 1981.
V. G. Timkovsky. Complexity of common subsequence and supersequence problems and related problems. Cybernetics, 25:565–580, 1990.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Blum, C., Cotta, C., Fernández, A.J., Gallardo, J.E., Mastrolilli, M. (2008). Hybridizations of Metaheuristics With Branch & Bound Derivates. In: Blum, C., Aguilera, M.J.B., Roli, A., Sampels, M. (eds) Hybrid Metaheuristics. Studies in Computational Intelligence, vol 114. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78295-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-78295-7_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78294-0
Online ISBN: 978-3-540-78295-7
eBook Packages: EngineeringEngineering (R0)