Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Stochastic local search : foundations and applications
Hoos H., Stützle T., Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004. 658 pp. Type: Book (9781558608726)
Date Reviewed: Mar 28 2005

This book clearly defines and describes the multitude of stochastic local search (SLS) methods, and their similarities and differences, and analyzes the techniques so that researchers, students, and engineers can better tailor these methods to practical applications, while solving various hard combinatorial problems.

The SLS methods outlined in the book (defined in chapter 2) are divided into three categories: simple local searches, hybrid local searches, and population-based methods. Specifically, these methods include the following algorithms: iterative improvement (II), randomized iterative improvement (RII), variable neighborhood descent (VND), variable depth search (VDS), simulated annealing (SA), tabu search (TS), dynamic local search (DLS), iterated local search (ILS), greedy randomized adaptive search procedure (GRASP), adaptive iterated construction search (AICS), ant colony optimization (ACO), and memetic algorithms (MA). The variety of methods is quite expansive; perhaps an extra category should have been included to further divide the simple methods into local and global searches, thus differentiating the iterated improvement methods (typically local) from those like the simulated annealing approach (generally global).

The authors illustrate the methods by choosing popular problems familiar to any reader, whether she or he is an educator or computer engineer. For example, the traveling salesperson problem (TSP) is used to elucidate the II, ACO, AICS, RII, DLS, and ILS methods. Similarly, the propositional satisfiability problem (SAT), which is the first known nonpolynomial time (NP) complete problem, is used to elucidate the II, RII, DLS, MA, GRASP, and TS algorithms.

Pseudocode algorithms, figures, and proofs accompany each of the SLS methods. This enhances the reader’s understanding of the procedure, and enables the reader to compare the iterative steps and performances along the way. For each search method, an algorithmic analysis is presented. Afterward, the authors introduce other interesting relationships and concepts. For example, they create an alternative approach to expound on constructive searches by adding “backtracking or recursive mechanisms.” This yields a complete systematic search that clearly impacts the optimization of the problem, requiring exponential time. The authors use this as a motivation to incorporate other heuristics, such as A* or branch-and-bound pruning, so that the resultant search requires a more tractable time to run.

The book is divided into two major parts. Part 1 (five chapters), “Foundations,” introduces the reader to two prototype combinatorial problems, the above-mentioned TSP and SAT problems. The authors chose these problems because of their prominence in the scientific literature, and the ease of problem conceptualization. Part 2 (five chapters), “Applications,” considers classical problems, and applies them to other related problems; there are also independent problems considered, such as scheduling problems, graph coloring, and deoxyribonucleic acid (DNA) code design. For all of these problems, various SLS algorithms are applied and analyzed. Each of the ten chapters in the book closes with two subsections, dedicated, respectively, to “Further Reading and Related Works” and “Summary/Exercises.” The book concludes with an epilogue, glossary, bibliography, and index.

This book can be used either as a textbook for advanced undergraduates, or as an introduction to advanced techniques for graduate students. It can also be considered an encyclopedia of local search techniques. The book is easy to read, the mathematics are easy to follow, and the coverage is extensive. We recommend this book to computer scientists, engineers, and mathematicians alike.

Reviewers:  R. GoldbergMinette Carl Review #: CR131049 (0602-0136)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
Stochastic Programming (G.1.6 ... )
Graph And Tree Search Strategies (I.2.8 ... )
Simulated Annealing (G.1.6 ... )
Combinatorics (G.2.1 )
Optimization (G.1.6 )
Would you recommend this review?
Other reviews under "Stochastic Programming": Date
An efficient Monte Carlo method for optimal control problems with uncertainty
Cao Y., Hussaini M., Zang T. Computational Optimization and Applications 26(3): 219-230, 2003. Type: Article
Apr 9 2004
Stochastic local search: foundations and applications
Hoos H., Stützle T., Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004.  658, Type: Book (9781558608726), Reviews: (2 of 2)
Oct 2 2006
The cross entropy method: a unified approach to combinatorial optimization, Monte-Carlo simulation (Information Science and Statistics)
Rubinstein R., Kroese D., Springer-Verlag New York, Inc., Secaucus, NJ, 2004. Type: Book (9780387212401)
Nov 23 2004

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2023 ThinkLoud®
Terms of Use
| Privacy Policy