Abstract
Scatter search and its generalized form called path relinking are evolutionary methods that have recently been shown to yield promising outcomes for solving combinatorial and nonlinear optimization problems. Based on formulations originally proposed in the 1960s for combining decision rules and problem constraints, these methods use strategies for combining solution vectors that have proved effective for scheduling, routing, financial product design, neural network training, optimizing simulation and a variety of other problem areas. These approaches can be implemented in multiple ways, and offer numerous alternatives for exploiting their basic ideas. We identify a template for scatter search and path relinking methods that provides a convenient and “user friendly” basis for their implementation. The overall design can be summarized by a small number of key steps, leading to versions of scatter search and path relinking that are fully specified upon providing a handful of subroutines. Illustrative forms of these subroutines are described that make it possible to create methods for a wide range of optimization problems.
This research was supported in part by the Air Force Office of Scientific Research Grant #F49620-97-1-0271.
Preview
Unable to display preview. Download preview PDF.
References
Consiglio, A. and S.A. Zenios (1996). “Designing Portfolios of Financial Products via Integrated Simulation and Optimization Models,” Report 96-05, Department of Public and Business Administration, University of Cyprus, Nicosia, CYPRUS, to appear in Operations Research. [http://zeus.cc.ucy.ac.cy/ucy/pba/zenios/public.htm]]
Consiglio, A. and S.A. Zenios (1997). “a Model for Designing Callable Bonds and its Solution Using Tabu Search.” Journal of Economic Dynamics and Control 21, 1445–1470. [http://zeus.cc.ucy.ac.cy/ucy/pba/zenios/public.html]
Crowston, W.B., F. Glover, G.L.Thompson and J.D. Trawick (1963). Probabilistic and Parametric Learning Combinations of Local Job Shop Scheduling Rules,” ONR Research Memorandum No. 117, GSIA, Carnegie Mellon University, Pittsburgh, PA
Cung, V-D., T. Mautor, P. Michelon, A. Tavares (1996). “Scatter Search for the Quadratic Assignment Problem”, Laboratoire PRISM-CNRS URA 1525. [http://www.prism.uvsq.fr/public/vdc/CONFS/ieee icec97.ps.Z]
Davis, L., ed. (1991). Handbook of Genetic Algorithms, Van Nostrand Reinhold.
Fisher, H. and G.L. Thompson (1963). “Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules,” Industrial Scheduling, J.F. Muth and G.L. Thompson, eds., Prentice-Hall. 225–251.
Fleurent, C., F. Glover, P. Michelon and Z. Valli (1996). “A Scatter Search pproach for Unconstrained Continuous Optimization,” Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, 643–648.
Freville, A. and G. Plateau (1986). “Heuristics and Reduction Methods for Multiple Constraint 0-1 Linear Programming Problems,” European Journal of Operational Research, 24,206–215.
Freville, A. and G. Plateau (1993). “An Exact Search for the Solution of the Surrogate Dual of the 0-1 Bidimensional Knapsack Problem,” European Journal of Operational Research, 68,413–421.
Glover, F. (1963). “Parametric Combinations of Local Job Shop Rules,” Chapter IV, ONR Research Memorandum no. 117, GSIA, Carnegie Mellon University, Pittsburgh, PA.
Glover, F. (1965). “A Multiphase Dual Algorithm for the Zero-One Integer Programming Problem,” Operations Research, Vol 13, No 6, 879.
Glover, F. (1968). “Surrogate Constraints,” Operations Research, 16, 741–749.
Glover, F. (1975). “Surrogate Constraint Duality in Mathematical Programming,” Operations Research, 23, 434–451.
Glover, F. (1977). “Heuristics for Integer Programming Using Surrogate Constraints,” Decision Sciences, Vol 8, No 1, 156–166.
Glover, F. (1992). “Ejection Chains, Reference Structures and Alternating Path Methods for Traveling Salesman Problems,” University of Colorado. Shortened version published in Discrete Applied Mathematics, 1996, 65, 223–253. [http://spot.colorado.edu/-glover (under Publications)]
Glover, F. (1994a). “Genetic Algorithms and Scatter Search: Unsuspected Potentials,” Statistics and Computing, 4, 131–140. [http://spot.colorado.edu/-glover (under Publications)]
Glover, F. (1994b). “Tabu Search for Nonlinear and Parametric Optimization (with Links to Genetic Algorithms),” Discrete Applied Mathematics, 49, 231–255. [http://spot.colorado.edu/~glover (under Publications)]
Glover, F. (1995). “Scatter Search and Star-Paths: Beyond the Genetic Metaphor,” OR Spectrum, 17, 125–137. [http://spot.colorado.edu/~glover (under Publications)]
Glover, F., J. P. Kelly and M. Laguna (1996). “New Advances and Applications of Combining Simulation and Optimization,” Proceedings of the 1996 Winter Simulation Conference, J. M. Charnes, D. J. Morrice, D. T. Brunner, and J. J. Swain (Eds.), 144–152. [http://spot.colorado.edu/~glover (under OptQuest heading)]
Glover, F. and M. Laguna (1997). Tabu Search, Kluwer Academic Publishers. [http://spot.colorado.edu/~glover (under Tabu Search heading)]
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Reading, Massachusetts: Addison-Wesley.
Greenberg, H. J. and Pierskalla, W.P. (1970). “Surrogate Mathematical Programs,” Operations Research, 18, 924–939.
Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI.
Karwan, M.H. and R.L. Rardin (1976). “Surrogate Dual Multiplier Search Procedures in Integer Programming,” School of Industrial Systems Engineering, Report Series No. 7-77-13, Georgia Institute of Technology.
Karwan, M.H. and R.L. Rardin (1979). “Some Relationships Between Lagrangean and Surrogate Duality in Integer Programming,” Mathematical Programming, 17, 230–334.
Kelly, J., B. Rangaswamy and J. Xu (1996). “A Scatter Search-Based Learning Algorithm for Neural Network Training,” Journal of Heuristics, Vol. 2, pp. 129–146.
Laguna, M. and R. Marti (1997). “GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization,” Research Report, University of Colorado [http://www.bus.colorado.edu/Faculty/Laguna/Papers/crossmin.htm]]
Laguna, M. (1997). “Optimizing Complex Systems with OptQuest,” Research Report, University of Colorado, [http://www.bus.colorado.edu/Faculty/Laguna/Papers]
Laguna, M., R. Martí and V. Campos (1997). “Tabu Search with Path Relinking for the Linear Ordering Problem,” Research Report, University of Colorado. [http://www.bus.colorado.edu/Faculty/Laguna/Papers/lop.htmll
Muhlenbein, H. (1997). “The Equation for the Response to Selection and its Use for Prediction,” to appear in Evolutionary Computation. [http://set.gmd.de/AS/ga/ga.htm]]
Rana, S. and D. Whitley (1997). “Bit Representations with a Twist,” Proc. 7th International Conference on Genetic Algorithms, T. Baeck ed. pp: 188–196, Morgan Kaufman. [http://www.cs.colostate.edu/~whitley/Pubs.htm]]
Rego, C. (1996). “Relaxed Tours and Path Ejections for the Traveling Salesman Problems,” to appear in the European Journal of Operational Research. [http://www.uportu.pt/~crego]
Rego, C. and C. Roucairol (1996). “A Parallel Tabu Search Algorithm Using Ejection Chains for the Vehicle Routing Problem,” in Meta-Heuristics: Theory & Applications, 661–675, I.H. Osman and J.P. Kelly, (eds.), Kluwer Academic Publishers. [http://www.uportu.pt/~crego]
Reeves, C.R. (1997). “Genetic Algorithms for the Operations Researcher,” to appear in INFORMS Journal on Computing (with commentaries and rejoinder).
Rochat, Y. and É. D. Taillard (1995). “Probabilistic diversification and intensification in local search for vehicle routing”. Journal of Heuristics 1, 147–167. [http://www.idsia.ch/~eric]
Taillard, É. D. (1996). “A heuristic column generation method for the heterogeneous VRP”, Publication CRT-96-03, Centre de recherche sur les transports, Université de Montréal. To appear in RAIRO-OR. [http://www.idsia.ch/~eric]
Whitley, D. and J. Kauth, (1988). “GENITOR: A Different Genetic Algorithm,” Proceedings of the 1988 Rocky Mountain Conference on Artificial Intelligence.
Whitley, D. (1989). The GENITOR Algorithm and Selective Pressure: Why Rank Based Allocation of Reproductive Trials is Best, Morgan Kaufmann, J. D. Schaffer, ed., pp. 116–121.
Yamada, T. and C. Reeves (1997). “Permutation Flowshop Scheduling by Genetic Local Search,” 2nd IEE/IEEE Int. Conf. on Genetic Algorithms in Engineering Systems (GALESIA '97), pp. 232–238, Glasglow, UK.
Yamada, T. and R. Nakano (1996). “Scheduling by Genetic Local Search with Multi-Step Crossover,” 4th International Conference on Parallel Problem Solving from Nature, 960–969.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Glover, F. (1998). A template for scatter search and path relinking. In: Hao, JK., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (eds) Artificial Evolution. AE 1997. Lecture Notes in Computer Science, vol 1363. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0026589
Download citation
DOI: https://doi.org/10.1007/BFb0026589
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64169-8
Online ISBN: 978-3-540-69698-8
eBook Packages: Springer Book Archive