Scatter Search

by Laguna, Manuel; Marti, Rafael

• ISBN13: 9781402073762
• ISBN10: 1402073763
• Format: Hardcover
• Copyright: 2003-02-01
• Publisher: Kluwer Academic Pub

Summary

The evolutionary approach called scatter search originated from strategies for creating composite decision rules and surrogate constraints. Recent studies demonstrate the practical advantages of this approach for solving a diverse array of optimization problems from both classical and real world settings. Scatter search contrasts with other evolutionary procedures, such as genetic algorithms, by providing unifying principles for joining solutions based on generalized path constructions in Euclidean space and by utilizing strategic designs where other approaches resort to randomization. The book's goal is to provide the basic principles and fundamental ideas that will allow the readers to create successful applications of scatter search. The book includes the C source code of the methods introduced in each chapter.From the Foreword: 'Scatter Search represents a "missing link" in the literature of evolutionary methods... 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. Yet this theme is an integral part of the scatter search methodology proposed a decade earlier, and the form and scope of such heuristic strategies embedded in scatter search continue to set it apart. Although there are points in common between scatter search and other evolutionary approaches, principally as a result of changes that have brought other approaches closer to scatter search in recent years, there remain differences that have an important impact on practical outcomes. Reflecting this impact, a hallmark of the present book is its focus on practical problem solving. Laguna and Martí give the reader the tools to create scatter search implementations for problems from a wide range of settings. Although theoretical problems (such as abstract problems in graph theory) are included, beyond a doubt the practical realm has a predominant role in this book....' Fred Glover, University of Colorado

Table of Contents

Foreword	xi
Preface	xv
Acknowledgments	xvii
1. INTRODUCTION	1	(22)
1. Historical Background	4	(7)
1.1. Original Proposal-1977	4	(2)
1.2. Scatter / Tabu Search Hybrid-1990	6	(2)
1.3. Scatter Search Template-1998	8	(3)
2. Basic Design	11	(5)
2.1. Summary of Notation	14	(10)
3. C Code Conventions	16	(7)
2. TUTORIAL: Unconstrained Nonlinear Optimization	23	(26)
1. Diversification Generation Method	24	(4)
1.1. Computer Code	26	(2)
2. Improvement Method	28	(3)
2.1. Computer Code	29	(2)
3. Reference Set Update Method	31	(6)
3.1. Computer Code	33	(4)
4 Subset Generation Method	37	(2)
4.1. Computer Code	38	(1)
5. Combination Method	39	(2)
5.1. Computer Code	40	(1)
6. Overall Procedure	41	(5)
6.1. Computer Code	44	(6)
7. Summary of C Functions	46	(3)
3. TUTORIAL: 0-1 Knapsack Problems	49	(20)
1. Diversification Generation Method	50	(5)
1.1. Computer Code	52	(3)
2. Improvement Method	55	(4)
2.1. Computer Code	57	(2)
3. Reference Set Update Method	59	(3)
3.1. Computer Code	61	(2)
4. Subset Generation Method	62	(1)
5. Combination Method	63	(2)
5.1. Computer Code	64	(1)
6. Overall Procedure	65	(2)
6.1. Computer Code	66	(5)
7. Summary of C Functions	67	(2)
4. TUTORIAL: Linear Ordering Problem	69	(20)
1. The Linear Ordering Problem	69	(2)
2. Diversification Generation Method	71	(5)
2.1. Computer Code	74	(2)
3. Improvement Method	76	(6)
3.1. Computer Code	79	(4)
4. Reference Set Update Method	82	(1)
5. Combination Method	83	(3)
5.1. Computer Code	85	(5)
6. Summary of C Functions	86	(3)
5. ADVANCED SCATTER SEARCH DESIGNS	89	(34)
1. Reference Set	90	(17)
1.1. Dynamic Updating	91	(2)
1.2. Rebuilding and Multi-Tier Update	93	(9)
1.2.1. Rebuilding	94	(1)
1.2.2. 2-Tier Update	95	(4)
1.2.3. 3-Tier Update	99	(3)
1.3. Solution Duplication and Diversity Control	102	(10)
1.3.1. Minimum Diversity Test	103	(2)
1.3.2. Hashing	105	(26)
2. Subset Generation	107	(5)
3. Specialized Combination Methods	112	(6)
3.1. Variable Number of Solutions	114	(2)
3.2. Binary Variables	116	(2)
4. Diversification Generation	118	(5)
4.1. Experimental Design	118	(2)
4.2. GRASP Constructions	120	(10)
6. USE OF MEMORY IN SCATTER SEARCH	123	(18)
1. Tabu Search	124	(4)
2. Explicit Memory	128	(2)
3. Attributive Memory	130	(11)
3.1. Diversification	131	(4)
3.1.1. Computer Code	133	(2)
3.2. Intensification	135	(3)
3.2.1. Computer Code	136	(10)
3.3. Reference Set	138	(4)
7. CONNECTIONS WITH OTHER POPULATION-BASED APPROACHES	141	(44)
1. Genetic Algorithms	142	(18)
1.1. SS and GA Comparison	146	(14)
1.1.1. Improvement Method	149	(1)
1.1.2. Combination Method	150	(4)
1.1.3. Computational Testing	154	(6)
2. Path Relinking	160	(20)
2.1. Simultaneous Relinking	166	(1)
2.2. Dealing with Infeasibility	167	(1)
2.3. Extrapolated Relinking	168	(2)
2.4. Multiple Guiding Solutions	170	(2)
2.5. Constructive Neighborhoods	172	(1)
2.6. Vocabulary Building	173	(4)
2.7. Computer Code	177	(8)
3. Intensification and Diversification	180	(5)
8. SCATTER SEARCH APPLICATIONS	185	(34)
1. Neural Network Training	185	(4)
1.1. Computer Code	187	(15)
2. Multi-Objective Bus Routing	189	(2)
3. Arc Crossing Minimization in Graphs	191	(2)
4. Maximum Clique	193	(2)
5. Graph Coloring	195	(2)
6. Periodic Vehicle Loading	197	(1)
7. Capacitated Multicommodity Network Design	198	(3)
8. Job-Shop ScheduLing	201	(1)
9. Capacitated Chinese Postman Problem	202	(4)
9.1. Testing Population Designs	204	(4)
10. Vehicle Routing	206	(2)
11. Binary Mixed Integer Programming	208	(4)
11.1. Pivot Based Search with Branch and Bound	208	(2)
11.2. Generate Diverse Solutions	210	(17)
12. Iterated Re-start Procedures	212	(3)
13. Parallelization for the P-Median	215	(2)
14. OptQuest Application	217	(2)
9. COMMERCIAL SCATTER SEARCH IMPLEMENTATION	219	(36)
1. General OCL Design	223	(2)
2. Constraints and Requirements	225	(2)
3. OCL Functionality	227	(12)
3.1. Defining Constraints and Requirements	232	(3)
3.2. Boundary Search Strategy	235	(21)
4. Computational Experiments	239	(6)
5. Conclusions	245	(1)
6. Appendix	246	(9)
10. EXPERIENCES AND FUTURE DIRECTIONS	255	(22)
1. Experiences and Findings	256	(10)
1.1. Diversification Generation	256	(2)
1.2. Improvement Method	258	(2)
1.3. Reference Set Update Method	260	(3)
1.4. Subset Generation Method	263	(1)
1.5. Combination Method	264	(2)
2. Multi-Objective Scatter Search	266	(5)
2.1. Independent Sampling Technique	269	(1)
2.2. Criterion Selection Technique	269	(1)
2.3. Aggregation Selection Technique	270	(1)
2.4. Pareto Sampling	270	(1)
3. Maximum Diversity Problem	271	(3)
4. Implications for Future Developments	274	(3)
REFERENCES	277	(8)
INDEX	285