CPSC 532D - Stochastic Search Algorithms (Spring 2005)

Course Outline (subject to minor adjustments)

Part 1: Foundations and Basics

Module 1: Introduction

• Combinatorial Problems (SAT, TSP, etc.)
• Computational Complexity (P vs. NP, etc.)
• Search Paradigms (systematic vs. local search, etc.)
• Stochastic Local Search (definition, general issues, etc.)

Module 2: "Simple" SLS Algorithms

• Iterative Improvement and Variants
• Simulated Annealing
• Tabu Search
• Dynamic Local Search, Guided Local Search

Module 3: Hybrid SLS Algorithms

• Iterated Local Search
• Variable Neighbourhood Search
• Greedy Randomised Adaptive Search
• Adaptive Iterated Construction Search

Module 4: Population-based SLS Algorithms

• Ant Colony Optimisation
• Evolutionary Computation (Genetic Algorithms, etc.)

Module 5: Generalised Local Search Machines

• Motivation and Basic GLSM Model
• Machine, Transition, and State Types
• Modelling SLS Algorithms Using GLSMs
• Extensions of the Basic GLSM Model

Module 6: Empirical Analysis of Stochastic Search Algorithms

• Las Vegas Algorithms (LVAs)
• Run-time Distributions (RTDs)
• RTD-based Analysis of LVA Behaviour
• Characterising and Improving LVA Behaviour
• Pitfalls of Inadequate Methodology

Module 7: Search Space Analysis

• Fundamental Search Space Properties
• Global Measures of Search Space Structure
• Solutions and Local Minima
• Plateau Structure

Part 2: Applications

Module 8: SAT and Constraint Satisfaction

Module 9: MaxSAT and MaxCSP

Module 10: The Travelling Salesperson Problem

Module 11: Scheduling Problems

Module 12: Other Combinatorial Problems

• Graph Colouring
• Quadratic Assignment
• Set Covering
• Combinatorial Auctions
• DNA Code Design

Additional Topics (time permitting)

• Randomised Systematic Search
• Hybrids Search Techniques (Systematic + Local Search, etc.)
• Dynamic Problems
• Interactice Search Approaches
• SLS vs. MCMC
• SLS vs. Numeric Optimisation