Tutorial Description

In this tutorial we will introduce stochastic search algorithms covering local search as well as randomised systematic search algorithms and characterise them as instances of the more general class of Las Vegas algorithms. In particular, we will discuss stochastic local search algorithms and randomised complete search algorithms for the satisfiability problem in propositional logic (SAT) and the Travelling Salesperson Problem (TSP). SAT is not only a prominent problem in AI as well as complexity theory, it also a conceptually very simple problem which facilitates the design, implementation, analysis, and evaluation of stochastic search methods. TSP is one of the most prominent combinatorial optimisation problem and plays an important role in developing and testing new algorithmic ideas. Other application areas, such as planning, scheduling, and resource allocation using market-based mechanisms will be also addressed.

Many stochastic search methods are based on a common theme, in that they do not use randomisation in a completely blind way but rather utilise ``intelligent'' heuristics to guide the search. We will introduce the most important guiding mechanisms for local search algorithms (often called metaheuristics) which have been developed in the interface between Artificial Intelligence and Operations Research. We will cover algorithms such as Tabu Search, Simulated Annealing, Iterated Local Search, Genetic Algorithms, and Ant Colony Optimization. Illustrations of applications of all the presented methods will be used to elucidate the principles of these stochastic search methods. It is our intention to provide ``hands-on'' knowledge, rather than just to present abstract computational recipes.

Another important issue we address is the empirical analysis of stochastic search algorithms. We point out pitfalls arising from the use of improper empirical methods and presents a systematic empirical methodology based on measuring run-time distributions. This methodology is very useful for analysing, characterising, and comparing algorithmic performance and has been used by the presenters with considerable success to characterise and improve the behaviour of stochastic search algorithms in different problem domains.

Stochastic search methods are placed in the intersection of Artificial Intelligence, Operations Research, Computer Science, and Statistics and are therefore interesting not only for AI but actually for a much wider audience. The tutorial addresses researchers from different areas of AI, Operations Research, and Computer Science, such as constraint satisfaction and satisfiability, theorem proving, planning and scheduling, learning, robotics, natural language processing, E-commerce, and many others where stochastic search methods are used to solve computationally hard combinatorial problems.

This half-day tutorial is co-organised and co-ordinated with the ECAI-2000 Workshop "Empirical Methods in AI" (co-chaired by the presenters) and the ECAI-2000 Tutorial "Empirical Methods for Computer Science" (by Paul Cohen, Ian Gent, and Toby Walsh). The workshop and the two tutorials will complement each other and together will offer a comprehensive coverage of many important issues in stochastic search and the empirical analysis of AI algorithms and systems.

Date & Time

Presenters / Contact Information

Holger H. Hoos currently works as a Postdoctoral Fellow at the University of British Columbia (Canada). His Ph.D. thesis on stochastic local search algorithms for computationally hard AI problems (SAT, CSP, etc.), finished in 1998 at TU Darmstadt (Germany), received the "Best Dissertation Award 1999" of the German Informatics Society (Gesellschaft für Informatik) and has recently be published as a book. He has been working on the design and the empirical analysis of algorithms for combinatorial problems in AI since 1994. His research has been published in several journals and at major conferences in AI and OR. He is furthermore involved in the development and research in Computer Music and has published papers at various computer music conferences. Holger Hoos has been teaching and designing courses in Artifical Intelligence, Computer Music, and Theoretical Computer Science at TU Darmstadt and the University of British Columbia. He has been involved in the organisation of symposia and conferences and has been a reviewer for various Journals and Conferences. He is co-organiser of the AAAI-2000 workshop "Leveraging Probability and Uncertainty in Computation", the ECAI-2000 workshop "Empirical Methods in Artificial Intelligence", and the ECAI-2000 workshop "Local Search for Planning & Scheduling".

Thomas Stützle is working as a Marie Curie Fellow at the "Institut de Recherches Interdisciplinaires et de Developpements en Intelligence Artificielle" (IRIDIA) of the Universite Libre de Bruxelles and is also affiliated with the Intellectics Group at TU Darmstadt. He received his M.Sc. in industrial engineering and managment science at the University of Karlsruhe and a Ph.D. from the Computer Science Department of Darmstadt University of Technology on the topic "Local Search Algorithms for Combinatorial Problems - Analysis, Improvements, and New Applications." He has also been a postgraduate fellow at the Statistics and Operations Research department of "Universidad Complutense de Madrid." He has published in several journals and conferences on stochastic search methods for computationally hard problems from Artificial Intelligence and Operations Research. He has reviewed articles for eight different journals and several conferences and he is co-editor of a special issue of the Future Generation Computer Science journal on "Ant Colony Optimization." Additionally, he will be the local co-ordinator at TU Darmstadt of the new Research Training Network called "Metaheuristics Network" (funded by the European Commission), which focuses on the study of metaheuristics for hard combinatorial optimization problems. At Darmstadt University of Technology he has taught a practical course on local search algorithms and supervised several M.Sc. thesis on the subject. He is also the co-organiser of the ECAI-2000 workshop "Empirical Methods in Artificial Intelligence".