Resources for Teaching Stochastic Local Search

• Paper: Teaching Stochastic Local Search, in Proceedings of the 18th International FLAIRS Conference (FLAIRS-2005), Clearwater Beach, Florida, May 15-17, 2005, AAAI Press.
• Code described in paper above
• Simulated annealing demonstration applets:
  • (Clustered) Traveling Salesman Problem
  • Class Scheduling Problem (see paper for description)
• Readings:
• Stochastic Local Search:
  • Russell, S. & Norvig, P.. Artificial Intelligence: a modern approach, section 4.3, pp. 110-115 (through "Simulated annealing search").
  • Hoos, H. H., and Stützle, T. 2005. Stochastic Local Search: foundations and applications. San Francisco: Morgan Kaufmann. (an excellent textbook for an advanced undergraduate or graduate course on stochastic local search)
• Simulated Annealing:
  • Kirkpatrick, S.; Gelatt, C.; and Vecchi, M. 1983. Optimization by simulated annealing. Science 220:671–680.
  • Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; and Flannery, B. P. 1992. Numerical Recipes in C: the art of scientific computing - 2nd Ed. Cambridge: Cambridge University Press, section 10.9, pp. 444 - 451.
• Suggested Syllabus
  • Preparatory reading: Russell and Norvig reading listed above
  • Class 1: Define problem, terminology, cover and collectively implement simple hill climbing (through "Hill Descent" in Teaching Stochastic Local Search)
  • Class 2: Observe local minima, add random uphill steps, add simulated annealing step, play with demo applets above (remainder of Teaching Stochastic Local Search)
  • Homework: Assign one or more challenge problems (see "Challenge Problems" of Teaching Stochastic Local Search)
  • Optional Laboratories: Give a simple, engaging combinatorial optimization problem, and have students (1) formalize the problem (clearly stating assumptions, constraints, etc.), (2) implement the associated annealing State, and (3) apply the stochastic local search method of their choice.  Have students justify their choices of optimization measures, discussing advantages and disadvantages to their problem formalizations.  Also, given time, have students demonstrate their software.  Here are two suggested challenge problems:
    • Forming teams: Forming project teams is a difficult task for faculty.  While some choose to form teams randomly, others seek to optimize various subjective/objective measures.  Write software that will optimize course project teams according to objective measures of your choice (e.g. maximizing students working with those they prefer, balancing group sizes, balancing abilities, etc.).  Justify your choice of measures, discussing advantages and disadvantages to your problem formalization. 
    • Ordering pizza: Pizza is an important food group of computer science departments everywhere.  Write software that will optimize pizza ordering according to objective measures of your choice (e.g. maximizing diners getting preferred toppings, minimizing waste, etc.).  Justify your choice of measures, discussing advantages and disadvantages to your problem formalization.

Note: These software resources are provided under the GNU General Public License (GNU GPL). 
Please responsibly cite the author's contribution when using these resources.
Although feedback/suggestions are much appreciated, this material will be updated infrequently as time permits.

Last updated 2 May 2005
Todd Neller