Stochastic Local Search : Foundations & Applications (The Morgan Kaufmann Series in Artificial Intelligence)
Holger H. Hoos, Thomas Stutzle
Format: PDF / Kindle (mobi) / ePub
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 Stutzle 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.
will be used throughout the ﬁrst part of this book for illustrating algorithmic 1.2 Two Prototypical Combinatorial Problems 17 techniques and approaches. These are the Propositional Satisﬁability Problem (SAT), a prominent combinatorial decision problem which plays a central role in several areas of computer science, and the Travelling Salesman Problem (TSP), one of the most extensively studied combinatorial optimisation problems. Besides their prominence and well established role in
unspeciﬁed, and partial round trips for a TSP instance, which correspond to paths in the corresponding graph that visit a subset of the vertices and can be extended into Hamiltonian cycles by adding additional edges. The task of generating (complete) candidate solutions by iteratively extending partial candidate solutions can be formulated as a search problem in which typically the goal is to obtain a ‘good’ candidate solution, where for optimisation problems, the goodness corresponds to the
function and an evaluation function. To minimise potential confusion between the deﬁnition of the problem to be solved (which, in case of an optimisation problem, includes an objective function) and the deﬁnition of an SLS algorithm for solving this problem (which might make use of an evaluation function different from the problem’s objective function), we systematically distinguish between the two concepts in this book. Generally, through the use of an evaluation function whose global optima
(optimal) solution s∗ is reduced with probability greater than or equal to , where distance is measured in terms of a minimum length search trajectory of A from its current position to s∗ . To see why this condition implies that A is PAC, consider a situation where the distance between the current candidate solution and s∗ is equal to l. In that case, we can compute a lower bound on the probability of reaching s∗ in exactly l steps as l . Since the diameter ∆ of the given neighbourhood graph is
correlation coefﬁcient. When the nature of an observed performance correlation seems to be regular (e.g., a roughly linear trend in the scatter plot), a simple regression analysis can be used to model the corresponding relationship in the algorithms’ performance. To test whether the correlation between the performance of two algorithms is signiﬁcant, non-parametric tests like Spearman’s rank order test or Kendall’s tau test can be employed [Sheskin, 2000]. These tests determine whether there is a