CPSC 532D - Stochastic Search Algorithms (Spring 2003)

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

Latest News:

03/04/24 - Mini-Workshop tomorrow, 9:00-17:00 in FSC 1613.

General / Administrative Information

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

New Time and Location: Tue 11-13 and Fri 13-14 in CICSR/CS 163

Instructor: Holger Hoos

[Current official information on graduate courses in 2002/03 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 from many domains, including AI, Bioinformatics, and Electronic Commerce, 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

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

02/03 students submit short project proposal (a sample project proposal from last year can be found here)
03/03 students submit short progress report
03/31 students submit final report (a sample final project report from last year can be found here)

04/25, 9:00-17:30: project presentations (Mini-Workshop), FSC 1613.

Preparation and Submission of Final Reports

Since we intend to combine the final reports into a proceedings volume for the mini-workshop, they need to be formatted uniformly. Please use LaTeX for preparing your final report and use this sample text as a template (PDF of the sample text available here). source of the sample text as a template for your report). Final reports have to be submitted as PDF files via e-mail to hoos@cs.ubc.ca by 03/03/31, 23:59 PST.

Preparation and Format of Workshop Talks

Each paper will be assigned a 30min slot, 5-10 minutes of which are intended for discussion. An overhead projector as well as an LCD projector will be available in the workshop room (FSC 1613). Presenters who want to use the LCD projector need to provide their own laptop or contact Holger about putting their presentation on his laptop (in HTML, PS, or PDF format, no PowerPoint support). The workshop schedule will be posted shortly.


Final grades will be determined from the following components:

Class Schedule

Class 1, 03/01/09, Thu:
Course Overview, Formalities (all information can be found on this webpage)

Class 2, 03/01/14, Tue:
Module 1. Discussion facilitator: Holger Hoos.
Assigned reading:

Class 3, 03/01/17, Fri:
Module 1 (continued). Discussion facilitator: Holger Hoos.
Assigned reading:

Class 4, 03/01/21, Tue:
Module 2 (Iterative Improvement, Simulated Annealing). Discussion facilitators: Mirela / Diana.
Assigned reading:

Class 5, 03/01/24, Fri:
Module 2 (Tabu Search, Dynamic Local Search). Discussion facilitator: Ladan.
Assigned reading:

Class 6, 03/01/28, Tue:
Module 3 (Iterated Local Search, GRASP). Discussion facilitators: Markus / Kelvin.
Assigned reading:

Class 7, 03/01/31, Fri:
Module 3/4 (AICS, ACO). Discussion facilitator: Bobby.
Assigned reading:

Class 8, 03/02/04, Tue:
Module 4 (ACO, EA). Discussion facilitators: Baharak / Sanja.
Assigned reading:

Note: There is no class on 03/02/07, Fri.

Class 9, 03/02/11, Tue:
Module 5 (Generalised Local Search Machines). Discussion facilitators: Max / Iryna.
Assigned reading:

Class 10, 03/02/14, Fri:
Module 6 (Empirical Analysis). Discussion facilitator: Jacek.
Assigned reading:

Note: There are no classes during Reading Week.

Class 11, 03/02/25, Tue:
Module 6 (Empirical Analysis). Discussion facilitators: Fred / James S.
Assigned reading:

Class 12, 03/02/28, Fri:
Module 7 (Search Space Analysis). Lecture by HH (no discussion / reading).

Class 13, 03/03/04, Tue:
Project presentations (10+5min per group). No reading.

Class 14, 03/03/07, Fri:
Module 8 (SAT). Discussion facilitator: Jonathan.
Assigned reading:

Class 15, 03/03/11, Tue:
Module 8 (SAT continued, CSP). Discussion facilitators: James C / Mirela.
Assigned reading:

Class 16, 03/03/14, Fri:
Module 9 (MaxSAT). Discussion facilitator: Bobby.
Assigned reading:

Class 17, 03/03/18, Tue:
Module 9 (MaxCSP) / Module 10 (TSP). Discussion facilitators: James S / Jacek.
Assigned reading: [Note: Since we used the second half of this class to discuss organisational issues (final project reports, workshop), we'll start Module 10 on Friday.]

Class 18, 03/03/21, Fri:
Module 10 (TSP). Discussion facilitator: Jacek.
Assigned reading: Additional reading (optional, not covered in class):

Class 19, 03/03/25, Tue:
Module 10 (continued), Module 11 (Scheduling - Basics). Discussion facilitators: Diana, Iryna.
Assigned reading:

Class 20, 03/03/28, Fri:
Module 11 (Scheduling - Neighbourhoods, Single-Machine Problems). Discussion facilitator: James C.
Assigned reading:

Note: Class cancelled on 03/04/01, Tue (additional class will be held on 03/04/15, Tue).

Class 21, 03/04/04, Fri:
Module 11 (Scheduling - Parallel-Machine and Multistage Problems) Discussion facilitator: Baharak.
Assigned reading:

Class 22, 03/04/08, Tue:
Module 12 (QAP, Combinatorial Auctions) Discussion facilitator: Fred, Kelvin.
Assigned reading:

Class 23, 03/04/15, Tue:
Module 13 (Randomised Systematic Search). Lecture by HH.
Suggested reading:


Assignments are to be completed by each student individually and have to be handed in before class on their due day either electronically via e-mail (in form of a PDF file), or as a hardcopy at the beginning of class.

02/04 - due 02/14 Assignment 1 (covers Modules 1-4)
03/10 - due 03/18 Assignment 2 (covers Modules 5-7)
04/18 - due 05/01 Assignment 3 (optional) (integrates knowledge from the entire course)
Required reading: Holte, R.C. Combinatorial Auctions, Knapsack Problems, and Hill-climbing Search.
Proc. AI'2001, Lecture Notes in Artificial Intelligence 2056, pp. 57-66, Springer Verlag, 2001.


Materials and Handouts (except assignments):


Links / Webpages:

last update 03/04/15, hh