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.

Includes supplementary material: sn.pub/extras

Autorentext

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.)

Klappentext
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 from the 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.

Inhalt

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. …