Scatter Search
Methodology and Implementations in C
Published on 28. February 2003
Book
Paperback/Softback
XVII, 291 pages
978-1-4020-7376-2 (ISBN)
Description
The book
Scatter Search
by Manuel Laguna and Rafael Martí represents a long-awaited "missing link" in the literature of evolutionary methods. Scatter Search (SS)-together with its generalized form called Path Relinking-constitutes the only evolutionary approach that embraces a collection of principles from Tabu Search (TS), an approach popularly regarded to be divorced from evolutionary procedures. The TS perspective, which is responsible for introducing adaptive memory strategies into the metaheuristic literature (at purposeful level beyond simple inheritance mechanisms), may at first seem to be at odds with population-based approaches. Yet this perspective equips SS with a remarkably effective foundation for solving a wide range of practical problems. The successes documented by
Scatter Search
come not so much from the adoption of adaptive memory in the range of ways proposed in Tabu Search (except where, as often happens, SS is advantageously coupled with TS), but fromthe use of strategic ideas initially proposed for exploiting adaptive memory, which blend harmoniously with the structure of Scatter Search. From a historical perspective, the dedicated use of heuristic strategies both to guide the process of combining solutions and to enhance the quality of offspring has been heralded as a key innovation in evolutionary methods, giving rise to what are sometimes called "hybrid" (or "memetic") evolutionary procedures. The underlying processes have been introduced into the mainstream of evolutionary methods (such as genetic algorithms, for example) by a series of gradual steps beginning in the late 1980s.
Reviews / Votes
From the reviews:
"The book Scatter Search by Manuel Laguna and Rafael Marti . provides an excellent introduction to this advanced optimization methodology. . Different from most other books in this field, this book comes along with a rich variety of illustrative examples for various optimization problems . . This significantly helps to gain an in-depth understanding of the methodology and enables readers to develop state-of-the-art implementations on their own. . With this book, the authors have created an excellent reference both for researchers and practitioners." (Stephan Scheuerer, OR-News, Issue 23, March, 2005)
More details
Series
Edition
Softcover reprint of the original 1st ed. 2003
Language
English
Place of publication
New York
United States
Target group
Professional and scholarly
Research
Illustrations
20 s/w Abbildungen
XVII, 291 p. 20 illus.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 17 mm
Weight
476 gr
ISBN-13
978-1-4020-7376-2 (9781402073762)
DOI
10.1007/978-1-4615-0337-8
Schweitzer Classification
Other editions
Additional editions
Book
10/2012
Springer
€160.49
Shipment within 7-9 days
Persons
Abraham Duarte is an Associate Professor in the Computer Science Department at the Rey Juan Carlos University(Madrid, Spain). He received his doctoral degree in Computer Sciences from the Rey Juan Carlos University. His research is devoted to the development of models and solution methods based on meta-heuristics for combinatorial optimization problems. He has published more than 50 papers in SCI-JCR prestigious scientific journals such us European Journal of Operational Research, INFORMS Journal on Computing, Computational Optimization and Applications, or Computers & Operations Research. Dr. Duarte has also published 11 papers in non-indexed journals, 20 book chapters and more than 70 papers in conference proceedings. He has been the principal investigator on 5 competitive research projects with a total budget of 200000 euros (aprox.), he has been the advisor of 5 doctoral theses, and he is co-inventor of a US patent (US 20100138373 A1). Dr Duarte is reviewer of the Journal of Heuristic, Journal of Mathematical Modeling and Algorithms, INFORMS Journal on Computing, Applied Soft Computing, European Journal of Operational Research and Soft Computing. He is also member of the program committee of the conferences MAEB, HIS, ISDA, SOCO or MHIPL.
Manuel Laguna is the MediaOne Professor of Management Science and Director of Global Initiatives at the Leeds School of Business of the University of Colorado Boulder. He started his academic career at the University of Colorado in 1990, after receiving master's (1987) and doctoral (1990) degrees in Operations Research and Industrial Engineering from the University of Texas at Austin.He has done extensive research in the interface between computer science, artificial intelligence and operations research, resulting in over one hundred publications, including four books. He has received research funding from private industry and government agencies such as the National Science Foundation, the Office of Naval Research and the Environmental Protection Agency. He is co-founder of OptTek Systems, a Boulder-based software and consulting company that provides optimization solutions. He is the editor-in-chief of the Journal of Heuristics and has been Division Chair, Senior Associate Dean and Interim Dean at the Leeds School of Business.
Rafael Martí is Professor of Statistics and Operations Research at the University of Valencia, Spain. He received a doctoral degree in Mathematics from the University of Valencia in 1994. He has done extensive research in metaheuristics for hard optimization problems.Dr Martí has about 200 publications, half of them in indexed journals (JCR), including EJOR, Informs JoC, IIE Transactions, JOGO, C&OR, and Discrete and Applied Maths. He is the co-author of Scatter Search (Kluwer 2003) and The Linear Ordering Problem (Springer 2011) monographs, and has secured an American patent. Prof. Martí is currently Area Editor in the Journal of Heuristics,Associate Editor in the Math. Prog. Computation, and the Int. Journal of Metaheuristics. He is Senior Research Associate of OptTek Systems (USA), and has given about 50 invited and plenary talks. Dr. Martí has been invited Professor at the University of Colorado (USA), University of Molde (Norway), University of Graz (Austria), and University of Bretagne-Sud (France.)
Content
1. Introduction.- 1. Historical Background.- 2. Basic Design.- 3. C Code Conventions.- 2. Tutorial:Unconstrained Nonlinear Optimization.- 1. Diversification Generation Method.- 2. Improvement Method.- 3. Reference Set Update Method.- 4. Subset Generation Method.- 5. Combination Method.- 6. Overall Procedure.- 7. Summary of C Functions.- 3. Tutorial:0-1 Knapsack Problems.- 1. Diversification Generation Method.- 2. Improvement Method.- 3. Reference Set Update Method.- 4. Subset Generation Method.- 5. Combination Method.- 6. Overall Procedure.- 7. Summary of C Functions.- 4. Tutorial:Linear Ordering Problem.- 1. The Linear Ordering Problem.- 2. Diversification Generation Method.- 3. Improvement Method.- 4. Reference Set Update Method.- 5. Combination Method.- 6. Summary of C Functions.- 5. Advanced Scatter Search Designs.- 1. Reference Set.- 2. Subset Generation.- 3. Specialized Combination Methods.- 4. Diversification Generation.- 6. Use of Memory in Scatter Search.- 1. Tabu Search.- 2.Explicit Memory.- 3. Attributive Memory.- 7. Connections with Other Population-Based Approaches.- 1. Genetic Algorithms.- 2. Path Relinking.- 3. Intensification and Diversification.- 8. Scatter Search Applications.- 1. Neural Network Training.- 2. Multi-Objective Bus Routing.- 3. Arc Crossing Minimization in Graphs.- 4. Maximum Clique.- 5. Graph Coloring.- 6. Periodic Vehicle Loading.- 7. Capacitated Multicommodity Network Design.- 8. Job-Shop Scheduling.- 9. Capacitated Chinese Postman Problem.- 10. Vehicle Routing.- 11. Binary Mixed Integer Programming.- 12. Iterated Re-start Procedures.- 13. Parallelization for the P-Median.- 14. OptQuest Application.- 9. Commercial Scatter Search Implementation.- 1. General OCL Design.- 2. Constraints and Requirements.- 3. OCL Functionality.- 4. Computational Experiments.- 5. Conclusions.- 6. Appendix.- 10. Experiences and Future Directions.- 1. Experiences and Findings.- 2. Multi-Objective Scatter Search.- 3. Maximum Diversity Problem.- 4. Implications for Future Developments.- References.