Stochastic Search Algorithms
Holger H. Hoos and Thomas
Stützle
Stochastic search algorithms have been shown to outperform their
deterministic counterparts in a number of interesting application
domains. They are becoming increasingly important and popular for
solving computationally hard combinatorial problems from various
domains of AI and Operations Research, such as planning, scheduling,
constraint satisfaction, satisfiability, or combinatorial
auctions.
In this tutorial we will introduce stochastic search algorithms and
characterise them as instances of the more general class of Las Vegas
algorithms. We will cover local search algorithms, including
stochastic hill-climbing, simulated annealing, tabu search,
evolutionary algorithms, and ant colony optimization, as well as
randomised systematic search algorithms. For exemplifying these
algorithms, we will mainly use the Satisfiability Problem in
Propositional Logic (SAT) and the Travelling Salesperson Problem (TSP),
which both play a central role in the design, implementation, and
analysis of algorithmic ideas. We will also address the empirical
analysis of Las Vegas algorithms and present case studies
demonstrating the successful application of stochastic search
algorithms to various problem domains.
Prerequisite knowledge: The attendees should have an interest in
computationally hard combinatorial problems. Basic knowledge in
standard AI search problems as well as a basic knowledge of search
methods would be an advantage but is not a necessary prerequisite.
Holger H. Hoos is an
Assistant Professor at the Computer Science Department of the
University of British Columbia (Canada), where he is a co-founder of
the Bioinformatics,
Empirical & Theoretical Algorithmics Laboratory (BETA-Lab) and a
member of the Laboratory for
Computational Intelligence (LCI). He received his PhD from the
Computer
Science Department at TU Darmstadt (Germany). His research interests
include
empirical algorithmics, artificial intelligence, bioinformatics,
and computer music.
Thomas
Stützle is an Assistant Professor at the Computer Science
Department of Darmstadt University of Technology, where he is local
coordinator of the Metaheuristics Network. He
received his PhD from the Computer Science Department at TU Darmstadt
(Germany). His research interests include combinatorial optimization,
multi-objective optimization, search space analysis, empirical
analysis of algorithms, design of algorithms.