CPSC 532D - Stochastic Search Algorithms (Spring 2002)

[General Info] · [Course Outline] · [Course Projects] · [Grading] · [Assignments] · [Resources]

General / Administrative Information

Course number / title: CPSC 532D (203): Topics in Artificial Intelligence - Stochastic Search Algorithms
Catalogue number: 25855

Time and Location: (changed!): Tue, 15:30-16:50 in CICSR/CS 202; and Thu 15:30-16:50 in CICSR/CS 204
Next Class: 02/02/12, Thu, 15:30 in CICSR/CS 202

Instructor: Holger Hoos

[Current official information on graduate courses in 2001/02 Term 2 can be found here]

Why Take This Course?

If you always wanted to learn about state-of-the-art approaches to combinatorial problem solving, including Simulated Annealing, Genetic Algorithms, Tabu Search, and Ant Colony Optimisation, this course is for you!

If you always wondered how hard problems are solved in practice, this course will introduce you thoroughly to at least one very popular and successful general approach.

And if you want to learn (more) about one of the hottest topics in AI, Operations Research, and Empirical Algorithmics research, you've found the right place!

The course will introduce many basic stochastic search methods and their most relevant variants, point out and discuss connections and differences between them, tell you implementation tricks and details which are hardly ever explained but essential to obtain good performance, and show you how these algorithms can be applied to many hard combinatorial problems from various domains, including AI, Operations Research, and Bioinformatics! The course will introduce you to the foundations of stochastic search and many of its very successful applications. It will provide you with a good balance of abstract and theoretical contents as well as with hands-on-experience (including implementation).

To date, designing stochastic search algorithms and applying them successfully to hard combinatorial problems is as much an art or a craft as it is a science. I will introduce you to both aspects of this exciting research area, and share many of my secrets with you ;-) There is no single book that offers the material covered by course (I am currently writing it, and will share drafts with you), and in many ways we will go beyond what you can easily find in the research literature.

Interested? Check out the in information in the following sections ...

Course Description & Prequisites

Preliminary Course Outline

Course Projects

General Information

Students are expected to select and complete a course project according to the following timetable:

02/04 students submit short project proposal
03/01 students submit short progress report
03/29 students submit final report

Fourth week of April: project presentations

Since we intend to combine the final reports into a proceedings volume for the mini-workshop, they need to be formatted uniformly. Please follow the layout and formatting of this sample text as closely as possible. We recommend to use LaTeX for preparing the final document (in which case you can use the source of the sample text as a template for your report). Final reports should be submitted as PostScript or PDF files via e-mail to hoos@cs.ubc.ca.


Final grades will be determined from the following components:


01/29 - due 02/05 Reading assignment: P. Mills and E.P.K.Tsang. Guided local search applied to the satisfiability (SAT) problem. (see resources section below)
02/14 - due 02/28 Assignment 1 (covers Modules 1-4)
04/12 - due 04/22 Assignment 2 (covers Modules 5-7)


Materials and Handouts (except assignments):


Links / Webpages:

More resources will be listed soon.

last update 02/04/12, hh