Stochastic Local Search: Foundations & Applications
Regular price
32.750 KD
inc. VAT
Couldn't load pickup availability
Table of contents
- Cover
- Copyright Pagevi
- Contentsxi
- Prologue1
- Part I: Foundations11
- Chapter 1. Introduction13
- 1.1 Combinatorial Problems13
- 1.2 Two Prototypical Combinatorial Problems16
- 1.3 Computational Complexity23
- 1.4 Search Paradigms31
- 1.5 Stochastic Local Search37
- 1.6 Further Readings and Related Work54
- 1.7 Summary55
- Exercises56
- Chapter 2. SLS Methods61
- 2.1 Iterative Improvement (Revisited)61
- 2.2 'Simple' SLS Methods71
- 2.3 Hybrid SLS Methods85
- 2.4 Population-Based SLS Methods95
- 2.5 Further Readings and Related Work105
- 2.6 Summary108
- Exercises111
- Chapter 3. Generalised Local Search Machines113
- 3.1 The Basic GLSM Model113
- 3.2 State, Transition and Machine Types122
- 3.3 Modelling SLS Methods Using GLSMs131
- 3.4 Extensions of the Basic GLSM Model138
- 3.5 Further Readings and Related Work142
- 3.6 Summary144
- Exercises145
- Chapter 4. Empirical Analysis of SLS Algorithms149
- 4.1 Las Vegas Algorithms149
- 4.2 Run-Time Distributions158
- 4.3 RTD-Based Analysis of LVA Behaviour171
- 4.4 Characterising and Improving LVA Behaviour184
- 4.5 Further Readings and Related Work198
- 4.6 Summary200
- Exercises201
- Chapter 5. Search Space Structure and SLS Performance203
- 5.1 Fundamental Search Space Properties203
- 5.2 Search Landscapes and Local Minima209
- 5.3 Fitness-Distance Correlation220
- 5.4 Ruggedness226
- 5.5 Plateaus235
- 5.6 Barriers and Basins243
- 5.7 Further Readings and Related Work249
- 5.8 Summary250
- Part II: Applications255
- Chapter 6. Propositional Satisfiability and Constraint Satisfaction257
- 6.1 The Satisfiability Problem257
- 6.2 The GSAT Architecture267
- 6.3 The WalkSAT Architecture273
- 6.4 Dynamic Local Search Algorithms for SAT284
- 6.5 Constraint Satisfaction Problems292
- 6.6 SLS Algorithms for CSPs299
- 6.7 Further Readings and Related Work306
- 6.8 Summary308
- Exercises310
- Chapter 7. MAX-SAT and MAX-CSP313
- 7.1 The MAX-SAT Problem313
- 7.2 SLS Algorithms for MAX-SAT321
- 7.3 SLS Algorithms for MAX-CSP340
- 7.4 Further Readings and Related Work350
- 7.5 Summary352
- Exercises354
- Chapter 8. Travelling Salesman Problems357
- 8.1 TSP Applications and Benchmark Instances357
- 8.2 'Simple' SLS Algorithms for the TSP367
- 8.3 Iterated Local Search Algorithms for the TSP384
- 8.4 Population-Based SLS Algorithms for the TSP399
- 8.5 Further Readings and Related Work410
- 8.6 Summary413
- Exercises414
- Chapter 9. Scheduling Problems417
- 9.1 Models and General Considerations417
- 9.2 Single-Machine Scheduling426
- 9.3 Flow Shop Scheduling438
- 9.4 Group Shop Problems449
- 9.5 Further Readings and Related Work460
- 9.6 Summary463
- Exercises464
- Chapter 10. Other Combinatorial Problems467
- 10.1 Graph Colouring468
- 10.2 The Quadratic Assignment Problem477
- 10.3 Set Covering488
- 10.4 Combinatorial Auctions498
- 10.5 DNA Code Design507
- 10.6 Further Readings and Related Work517
- 10.7 Summary520
- Exercises523
- Epilogue527
- Glossary537
- Bibliography575
- Index633
Stochastic local search (SLS) algorithms are among the most prominent and successful techniques for solving computationally difficult problems in many areas of computer science and operations research, including propositional satisfiability, constraint satisfaction, routing, and scheduling. SLS algorithms have also become increasingly popular for solving challenging combinatorial problems in many application areas, such as e-commerce and bioinformatics.
Hoos and Stützle offer the first systematic and unified treatment of SLS algorithms. In this groundbreaking new book, they examine the general concepts and specific instances of SLS algorithms and carefully consider their development, analysis and application. The discussion focuses on the most successful SLS methods and explores their underlying principles, properties, and features. This book gives hands-on experience with some of the most widely used search techniques, and provides readers with the necessary understanding and skills to use this powerful tool.
*Provides the first unified view of the field.
*Offers an extensive review of state-of-the-art stochastic local search algorithms and their applications.
*Presents and applies an advanced empirical methodology for analyzing the behavior of SLS algorithms.
*A companion website offers lecture slides as well as source code and Java applets for exploring and demonstrating SLS algorithms.
Hoos and Stützle offer the first systematic and unified treatment of SLS algorithms. In this groundbreaking new book, they examine the general concepts and specific instances of SLS algorithms and carefully consider their development, analysis and application. The discussion focuses on the most successful SLS methods and explores their underlying principles, properties, and features. This book gives hands-on experience with some of the most widely used search techniques, and provides readers with the necessary understanding and skills to use this powerful tool.
*Provides the first unified view of the field.
*Offers an extensive review of state-of-the-art stochastic local search algorithms and their applications.
*Presents and applies an advanced empirical methodology for analyzing the behavior of SLS algorithms.
*A companion website offers lecture slides as well as source code and Java applets for exploring and demonstrating SLS algorithms.