Stochastic local search (SLS) algorithms are among the most prominent and successful techniques for solving computationally hard problems in many fields of computer science (specifically 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 satisfaction, planning, scheduling, bioinformatics, combinatorial auctions, and others.
In this course, 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 salesman 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.
This course is primarily an advanced algorithms course. It covers material from the intersection of algorithmics (the science of algorithm design and analysis), combinatorial problem solving (a core topic in artificial intelligence as well as operations research), and various application domains. Students will be exposed to and familiarised with established and cutting edge practices and methodologies in this rapidly evolving and increasingly important research area. The course comprises lectures, formal and informal discussions, various types of assignments, and a course project (groups of 2-3 students).
Students taking this course are expected to have a strong interest and solid background in algorithms and at least basic knowledge in AI. Specifically, prior knowledge of standard AI search problems, such as SAT and CSP, and of combinatorial problems from other domains, as well as some basic knowledge of search methods would be an advantage, but not an absolute prerequisite. Good implementation skills are required, in particular for programming assignments and the course project.
The course is targeted towards graduate students in Computer Science. Graduate students from other departments (e.g., ECE, Mathematics, or Commerce) or undergraduates may take the course if they satisfy the prerequisites, if space is available, and after consulting with the instructor.
This course has been developed by Holger Hoos in 2001/2002, based on material by Holger Hoos (UBC) and Thomas Stützle (TU Darmstadt).
Next offering:
Past offerings:If you have any questions regarding the course, please contact me (hoos@cs.ubc.ca).