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.