Abstract
Scatter Search and its generalized form Path Relinking, are evolutionary methods that have been successfully applied to hard optimization problems. Unlike genetic algorithms, they operate on a small set of solutions and employ diversification strategies of the form proposed in Tabu Search, which give precedence to strategic learning based on adaptive memory, with limited recourse to randomization. The fundamental concepts and principles were first proposed in the 1970s as an extension of formulations, dating back to the 1960s, for combining decision rules and problem constraints. (The constraint combination approaches, known as surrogate constraint methods, now independently provide an important class of relaxation strategies for global optimization.) The Scatter Search framework is flexible, allowing the development of alternative implementations with varying degrees of sophistication. Path Relinking, on the other hand, was first proposed in the context of the Tabu Search metaheuristics, but it has been also applied with a variety of other methods. This chapter’s goal is to provide a grounding in the essential ideas of Scatter Search and Path Relinking, together with pseudo-codes of simple versions of these methods, that will enable readers to create successful applications of their own.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Campos, V., Glover, F., Laguna, M. and Martí, R. (2001), “An Experimental Evaluation of a Scatter Search for the Linear Ordering Problem” Journal of Global Optimization 21, 397–414
Glover F. (1994). “Tabu Search for Nonlinear and Parametric Optimization (with Links to Genetic Algorithms),” Discrete Applied Mathematics, vol. 49, 231–255.
Glover, F. (1997). “A Template for Scatter Search and Path Relinking,” in Lecture Notes in Computer Science, 1363, J.K. Hao, E. Lutton, E. Ronald, M. Schoenauer, D. Snyers (Eds.), 1–53. (Expanded version available on request.)
Glover F. (1999). “Scatter Search and Path Relinking,” In: D Corne, M Dorigo and F Glover (eds.) New Ideas in Optimisation, Wiley.
Glover, F. and M. Laguna (1997) Tabu Search, Kluwer Academic Publishers, Boston.
Glover, F., M. Laguna and R. Martí (2000), “Fundamentals of Scatter Search and Path Re-linking” Control and Cybernetics, 29 (3), 653–684
Glover, F., M. Laguna and R. Martí (2002). “Scatter Search,” to appear in Theory and Applications of Evolutionary Computation: Recent Trends, A. Ghosh and S. Tsutsui (Eds.) Springer-Verlag.
Greistorfer, P. and Voss, S. (2001), “Controlled Pool Maintenance in Combinatorial Optimization” Conference on Adaptive Memory and Evolution: Tabu Search and Scatter Search, University of Mississippi.
Laguna, M. (2000) “Scatter Search,” to appear in Handbook of Applied Optimization, P. M. Pardalos and M. G. C. Resende (Eds.), Oxford Academic Press.
Laguna, M. and R. Martí (1999). “GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization,” INFORMS Journal on Computing, Vol. 11, No. 1, pp. 44–52.
Laguna, M. and R. Martí (2000a). “Experimental Testing of Advanced Scatter Search Designs for Global Optimization of Multi-modal Functions,” Working paper, University of Colorado.
Laguna, M. and R. Martí (2000b). “The OptQuest Callable Library,” Optimization Software Class Libraries, S. Voss and D. L. Woodruff (Eds.), Kluwer, Boston. pp. 193–218
Laguna, M. and Martí, R. (2003), Scatter Search. Methodology and Implementations in C, Kluwer Academic Publishers, 312 pp.
Laguna, M., R. Martí and V. Campos (1999). “Intensification and Diversification with Elite Tabu Search Solutions for the Linear Ordering Problem,” Computers and Operations Research, Vol. 26, pp. 1217–1230.
Piñana, E., Plana, I., Campos, V. and Martí, R. (2001). “GRASP and Path relinking for the matrix bandwidth minimization”, European Journal of Operational Research, forthcoming.
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Glover, F., Laguna, M., Martí, R. (2004). Scatter Search and Path Relinking: Foundations and Advanced Designs. In: New Optimization Techniques in Engineering. Studies in Fuzziness and Soft Computing, vol 141. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39930-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-39930-8_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-05767-0
Online ISBN: 978-3-540-39930-8
eBook Packages: Springer Book Archive