Stochastic local search : foundations and applications / Holger H. Hoos, Thomas Stutzle.

Format:

Book

Author/Creator:

Hoos, Holger H.

Contributor:

Stützle, Thomas.

Series:

The Morgan Kaufmann Series in Artificial Intelligence

Language:

English

Subjects (All):

Algorithms.

Combinatorial analysis.

Stochastic programming.

Physical Description:

1 online resource (677 p.)

Place of Publication:

San Francisco, CA : Morgan Kaufmann Publishers, c2005.

Language Note:

English

Summary:

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

Contents:

Front Cover; Stochastic Local Search: Foundations and Applications; Copyright Page; Contents; Prologue; Part I: Foundations; Chapter 1. Introduction; 1.1 Combinatorial Problems; 1.2 Two Prototypical Combinatorial Problems; 1.3 Computational Complexity; 1.4 Search Paradigms; 1.5 Stochastic Local Search; 1.6 Further Readings and Related Work; 1.7 Summary; Exercises; Chapter 2. SLS Methods; 2.1 Iterative Improvement (Revisited); 2.2 'Simple' SLS Methods; 2.3 Hybrid SLS Methods; 2.4 Population-Based SLS Methods; 2.5 Further Readings and Related Work; 2.6 Summary; Exercises

Chapter 3. Generalised Local Search Machines3.1 The Basic GLSM Model; 3.2 State, Transition and Machine Types; 3.3 Modelling SLS Methods Using GLSMs; 3.4 Extensions of the Basic GLSM Model; 3.5 Further Readings and Related Work; 3.6 Summary; Exercises; Chapter 4. Empirical Analysis of SLS Algorithms; 4.1 Las Vegas Algorithms; 4.2 Run-Time Distributions; 4.3 RTD-Based Analysis of LVA Behaviour; 4.4 Characterising and Improving LVA Behaviour; 4.5 Further Readings and Related Work; 4.6 Summary; Exercises; Chapter 5. Search Space Structure and SLS Performance

5.1 Fundamental Search Space Properties5.2 Search Landscapes and Local Minima; 5.3 Fitness-Distance Correlation; 5.4 Ruggedness; 5.5 Plateaus; 5.6 Barriers and Basins; 5.7 Further Readings and Related Work; 5.8 Summary; Part II: Applications; Chapter 6. Propositional Satisfiability and Constraint Satisfaction; 6.1 The Satisfiability Problem; 6.2 The GSAT Architecture; 6.3 The WalkSAT Architecture; 6.4 Dynamic Local Search Algorithms for SAT; 6.5 Constraint Satisfaction Problems; 6.6 SLS Algorithms for CSPs; 6.7 Further Readings and Related Work; 6.8 Summary; Exercises

Chapter 7. MAX-SAT and MAX-CSP7.1 The MAX-SAT Problem; 7.2 SLS Algorithms for MAX-SAT; 7.3 SLS Algorithms for MAX-CSP; 7.4 Further Readings and Related Work; 7.5 Summary; Exercises; Chapter 8. Travelling Salesman Problems; 8.1 TSP Applications and Benchmark Instances; 8.2 'Simple' SLS Algorithms for the TSP; 8.3 Iterated Local Search Algorithms for the TSP; 8.4 Population-Based SLS Algorithms for the TSP; 8.5 Further Readings and Related Work; 8.6 Summary; Exercises; Chapter 9. Scheduling Problems; 9.1 Models and General Considerations; 9.2 Single-Machine Scheduling; 9.3 Flow Shop Scheduling

9.4 Group Shop Problems9.5 Further Readings and Related Work; 9.6 Summary; Exercises; Chapter 10. Other Combinatorial Problems; 10.1 Graph Colouring; 10.2 The Quadratic Assignment Problem; 10.3 Set Covering; 10.4 Combinatorial Auctions; 10.5 DNA Code Design; 10.6 Further Readings and Related Work; 10.7 Summary; Exercises; Epilogue; Glossary; Bibliography; Index

Notes:

Description based upon print version of record.

Includes bibliographical references (p. 575-631) and index.

ISBN:

1-281-01505-9

9786611015053

0-08-049824-8

OCLC:

437202752