| On 2004-11-29 at 10:00:00 (Brussels Time) |
Abstract
Stochastic local search (SLS) algorithms are among the most prominent and successful techniques for solving computationally hard problems in many areas of Artificial Intelligence and Operations Research. To date, SLS algorithms are becoming increasingly important and popular for solving hard combinatorial problems in various domains of theoretical and practical interest, such as propositional satisfiability, constraint optimisation, scheduling, bioinformatics, combinatorial auctions, and many others. This tutorial offers a systematic, unified treatise of SLS and a wide coverage of SLS algorithms combined with a presentation and discussion of selected SLS applications to AI problems. More specifically, we aim to give the attendees access to detailed knowledge on the most prominent and successful SLS techniques; to facilitate an understanding of the relationships, the characteristic similarities and differences between existing techniques; to introduce and discuss basic and advanced aspects of the empirical evaluation of SLS algorithms; an explanation of their successes and failures through techniques for the search space analysis; and to give hands-on knowledge on the application of some of the most widely used search techniques to a variety of combinatorial problems.
Keywords
Stochastic local search, combinatorial optimization, metaheuristics
