What can be done when a problem becomes too difficult to solve? Although many problems are known to be solvable with a reasonable amount of computational resources, even if the problem is known to be nondeterministic polynomial time (NP) hard , in other cases, problems become so difficult that no technique can solve the problem with reasonable effort.
Generally speaking, problem-solving techniques can be divided into three different groups: search algorithms that make use of heuristic functions for constructively solving either decision or optimization problems ; constraint processing algorithms that extend current solutions, guaranteeing that problem constraints are still met ; and stochastic local search (SLS) algorithms, which usually progress by perturbating a candidate solution that is chosen according to a given policy. This book is concerned with the third class of algorithms, from both a theoretical and practical point of view. It introduces stochastic local search algorithms as the choice when solving really hard problems.
The book begins by accurately describing the different types of problems, and existing techniques for solving them. The theoretical definitions are enlightening, with two of the most well-known domains, the propositional satisfiability problem (SAT) and the traveling salesman problem (TSP), covered in chapters 6 and 8, respectively.
In chapter 1, special emphasis is placed on the differences between branch-and-bound and single-agent search algorithms like A*. Many readers will find interesting the large number of analogies that can be established between both techniques throughout the first part (chapters 1 to 5). Indeed, chapter 2, being devoted to a description of the main SLS algorithms, starts with a discussion familiar to researchers in the field of single-agent search algorithms, namely, the relation between the cardinality of the neighborhood set N(s) (known in single-agent search algorithms as the branching factor) and the diameter of the underlying graph (known as maximum depth).
Similarities are also established with constraint-processing techniques. Chapter 6 briefly discusses the so-called “encode and solve as SAT” approach, as well as various local consistency techniques.
Chapter 4 faces an important question: how to compare the performance of different algorithms when taking into account that they might end up solving different instances, or solving other cases with different running times or solution costs. Most remarkably, the several statistical-based approaches suggested in the text are widely applicable to almost every problem-solving technique. This chapter is therefore a valuable scientific contribution, beyond the scope of SLS algorithms.
The first part of the book ends with chapter 5, which provides an extremely interesting discussion seeking to provide some advice about which SLS algorithm to use, and how to distinguish between hard and easy instances. First, solution number and density, as well as number and distribution of local minima, are considered. Clearly, these well-known features are not enough to characterize the behavior of SLS algorithms. Therefore, fitness-distance analysis (FDA) is introduced. It computes the correlation between the solution quality and the distance between solutions, in order to get an idea of how difficult it is to reach a solution in practice. Because all of these techniques do actually require the computation of various solutions (as many as possible), they are only used as a posteriori methods. Instead, the concept of search landscape is introduced immediately after, and ruggedness is defined without taking into account the number or density of solutions. The key idea consists of studying the variability of the cost function in the neighborhood of every state: the smoother the search landscape, the easier it is to walk through, making it more likely to find higher-quality solutions. Finally, plateaus (a familiar concept to researchers in single-agent search algorithms) are strictly defined, and various measures are suggested, leading to the presentation of barriers and basins. It should be noted that plateau connection graphs and basin partition trees, as defined here, have recently been developed by the first author, so they are noted as unpublished in the specialized bibliography. This observation should strengthen the scientific relevance of this chapter.
In the second part of the book, real applications to various domains are considered. For example, chapter 8 discusses the importance of data structures for efficiently implementing SLS algorithms for the TSP. Chapter 9 introduces SLS algorithms for solving scheduling problems, in contrast with the techniques discussed in Ghallab et al.’s book , for example.
Finally, this book is accessible to a very wide audience: beginners will find a large number of examples and exercises at the end of every chapter, classified according to their difficulty; experienced researchers in the area will find in-depth sections, providing far more detailed discussions that can be safely skipped by newcomers; and experts in the field will find this manual a valuable source of new ideas, with hundreds of appropriately classified bibliographical references.